# Perl program to calculate Fib(n) using O(log n) matrix multiplications

@FIBMATRIX = (1,1,1,0);
$FM = \@FIBMATRIX;

# multiply two 2x2 matrices
# function is passed two pointers to arrays, also returns pointer
sub mmult 
{  
    my ($A,$B) = @_;  # lexicalize variables
    my $a = $$A[0]*$$B[0] + $$A[1]*$$B[2];     #can also use $A->[0], etc
    my $b = $$A[0]*$$B[1] + $$A[1]*$$B[3];
    my $c = $$A[2]*$$B[0] + $$A[3]*$$B[2];
    my $d = $$A[2]*$$B[1] + $$A[3]*$$B[3];
    my @m = ($a,$b,$c,$d);
    \@m;
}  #mmult

# pass matrix pointer followed by n  
sub mexpt
{
    my ($M,$n) = @_;
    my @id=(1,0,0,1);  # identity matrix
    if ($n<1) { return \@id; }
    if ($n==1) { return $M; }
    my $M2 = mexpt($M,$n/2);
    my $result = mmult($M2,$M2);
    if ($n%2==1) { $result = mmult($result,$M); }
    $result
}  #mexpt


#print @{mmult($FM,$FM)};

#print @{mexpt($FM,10)};

sub fib
{
    my $n= $_[0];
    my $matrix = mexpt($FM,$n-1);
    $matrix->[0];
}

print fib(8), "\n";   # 21
print fib(9), "\n";   # 34
print fib(10), "\n";  # 55
print fib(100), "\n";  # only approximation, perl has no built-in big ints
