#! perl -slw
use strict;
use 5.010;
use Time::HiRes qw[ time ];
use constant {
    GR => 1.6180339887498948482,
    ROOT5 => sqrt( 5 ),
};

sub fibCalc {
    int( GR ** $_[0] / ROOT5 + 0.5 );
}

sub fibIter {
    my $n = shift;
    return $n if $n < 2;
    my( $f1, $f2, $fib ) = ( 1, 0, 0 );
    for ( 2 .. $n ) {
        $fib = $f1 + $f2;
        ( $f1, $f2 ) = ( $fib, $f1 );
    }
    return $fib;
}

sub fibMem {
    state %cache;
    my $n = shift;
    return $n if $n < 2;
    return ( $cache{ $n - 2 } //= fibMem( $n - 2 ) )
         + ( $cache{ $n - 1 } //= fibMem( $n - 1 ) );
}

sub fibRec {
   my ($n) = @_;
   return 0 if $n == 0;
   return 1 if $n == 1;
   return fibRec($n-2) + fibRec($n-1);
}

printf "%2d : rec:%8d mem: %8d iter:%8d calc:%8d\n",
    $_, fibRec( $_ ), fibMem( $_ ), fibIter( $_ ), fibCalc( $_ )
    for 1 .. 30;

my $start = time;
my $total = 0;
$total += fibRec( $_ ) for 1 .. $ARGV[0];
printf "recursive:  Got %d; took %f seconds\n", $total, time() - $start;

$start = time;
$total = 0;
$total += fibMem( $_ ) for 1 .. $ARGV[0];
printf "memoized:   Got %d; took %f seconds\n", $total, time() - $start;

$start = time;
$total = 0;
$total += fibIter( $_ ) for 1 .. $ARGV[0];
printf "iterative:  Got %d; took %f seconds\n", $total, time() - $start;

$start = time;
$total = 0;
$total += fibCalc( $_ ) for 1 .. $ARGV[0];
printf "calculate:  Got %d; took %f seconds\n", $total, time() - $start;

__END__
C:\test>885839 35
 1 : rec:       1 mem:        1 iter:       1 calc:       1
 2 : rec:       1 mem:        1 iter:       1 calc:       1
 3 : rec:       2 mem:        2 iter:       2 calc:       2
 4 : rec:       3 mem:        3 iter:       3 calc:       3
 5 : rec:       5 mem:        5 iter:       5 calc:       5
 6 : rec:       8 mem:        8 iter:       8 calc:       8
 7 : rec:      13 mem:       13 iter:      13 calc:      13
 8 : rec:      21 mem:       21 iter:      21 calc:      21
 9 : rec:      34 mem:       34 iter:      34 calc:      34
10 : rec:      55 mem:       55 iter:      55 calc:      55
11 : rec:      89 mem:       89 iter:      89 calc:      89
12 : rec:     144 mem:      144 iter:     144 calc:     144
13 : rec:     233 mem:      233 iter:     233 calc:     233
14 : rec:     377 mem:      377 iter:     377 calc:     377
15 : rec:     610 mem:      610 iter:     610 calc:     610
16 : rec:     987 mem:      987 iter:     987 calc:     987
17 : rec:    1597 mem:     1597 iter:    1597 calc:    1597
18 : rec:    2584 mem:     2584 iter:    2584 calc:    2584
19 : rec:    4181 mem:     4181 iter:    4181 calc:    4181
20 : rec:    6765 mem:     6765 iter:    6765 calc:    6765
21 : rec:   10946 mem:    10946 iter:   10946 calc:   10946
22 : rec:   17711 mem:    17711 iter:   17711 calc:   17711
23 : rec:   28657 mem:    28657 iter:   28657 calc:   28657
24 : rec:   46368 mem:    46368 iter:   46368 calc:   46368
25 : rec:   75025 mem:    75025 iter:   75025 calc:   75025
26 : rec:  121393 mem:   121393 iter:  121393 calc:  121393
27 : rec:  196418 mem:   196418 iter:  196418 calc:  196418
28 : rec:  317811 mem:   317811 iter:  317811 calc:  317811
29 : rec:  514229 mem:   514229 iter:  514229 calc:  514229
30 : rec:  832040 mem:   832040 iter:  832040 calc:  832040
recursive:  Got 24157816; took 49.278000 seconds
memoized:   Got 24157816; took  0.000115 seconds
iterative:  Got 24157816; took  0.000416 seconds
calculate:  Got 24157816; took  0.000073 seconds