fibonacci_2pX_Ydigit.pl

#! /usr/bin/perl
###############################################################################
#  $0 <exp> <digit>                                                           #
#    gets the last <digit> digit from the <2^exp>th fibonacci number          #
#    maximal exp    = 97   default exp    = 53                                #
#    maximal digits =  9   default digits =  6                                #
###############################################################################
use warnings;
use strict;

##### GET and CHECKING PARAMETERS

sub useage()
{
  warn "$0 exp digit\n"
     . "Fibonacci( 2 ^ 'exp' ) -nek kiszamolja az utolso 'digit' szamjegyet.\n"
     . "  exp   - egesz szam, 2 kitevojet jelzi (def 53) [max 97]\n"
     . "  digit - egesz szam, utolso szamjegyek szamat jelzi (def 6) [max 9]\n\n";
}

my $max_exp = 97;
my $max_digit = 9;
my $warn;

my ($exp, $digit) = @ARGV;

if (!$exp || $exp =~ /\D/) {
  $warn = 1;
  $exp = 53;
}

if ($exp > $max_exp)
{
  $warn = 1;
  $exp = $max_exp;
}

$digit = 6 if (!$digit || $digit =~ /\D/);

if ($digit > $max_digit)
{
  $warn = 1;
  $digit = $max_digit;
}

my $mod = 10 ** $digit;

useage() if $warn;

##### ALGORITHM by http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

sub mx2_mod_mul($$)
{
  my ($a,$b) = @_;
  return [
    [($a->[0]->[0] * $b->[0]->[0]  +  $a->[0]->[1] * $b->[1]->[0]) % $mod,
     ($a->[0]->[0] * $b->[0]->[1]  +  $a->[0]->[1] * $b->[1]->[1]) % $mod],
    [($a->[1]->[0] * $b->[0]->[0]  +  $a->[1]->[1] * $b->[1]->[0]) % $mod,
     ($a->[1]->[0] * $b->[0]->[1]  +  $a->[1]->[1] * $b->[1]->[1]) % $mod]
  ];
}

sub mx2_mod_pow($$);
sub mx2_mod_pow($$)
{
  my ($a,$p) = @_;
  return $a if ($p == 1);
  return mx2_mod_mul($a, mx2_mod_pow($a,($p-1))) if ($p % 2);

  my $b = mx2_mod_pow($a, int($p/2));
  return mx2_mod_mul ($b,$b);
}

sub get($)
{
  return $_[0]->[0]->[1];
}

##### RUN THE CODE

my $m = [[1,1],[1,0]];
my $c = mx2_mod_pow($m, 2**$exp);
print "(F.2^$exp).digit($digit) = " . get($c) . "\n";