perl-scripts/Math/modular_fibonacci_mpz.pl at master · trizen/perl-scripts · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/perl

# Daniel "Trizen" Șuteu
# Date: 22 June 2017
# https://github.com/trizen

# An efficient algorithm for computing large Fibonacci numbers, modulo some n.

# Algorithm from:
#   https://codeforces.com/blog/entry/14516

use 5.020;
use strict;
use warnings;

use Math::GMPz qw();
use experimental qw(signatures);

sub fibmod($n, $mod, $cache={}) {

    $n <= 1 && return $n;

    sub ($n) {

        $n <= 1 && return do {
            state $one = Math::GMPz::Rmpz_init_set_ui(1)
        };

        if (exists($cache->{$n})) {
            return $cache->{$n};
        }

        my $k = $n >> 1;

        $cache->{$n} = (
                        $n % 2 == 0
                        ? (__SUB__->($k) * __SUB__->($k)     + __SUB__->($k - 1) * __SUB__->($k - 1)) % $mod
                        : (__SUB__->($k) * __SUB__->($k + 1) + __SUB__->($k - 1) * __SUB__->($k)    ) % $mod
                       );
    }->($n - 1);
}

say fibmod(329468, 10**10, {});     # 352786941