#!/usr/bin/perl

use strict;
use warnings;
use Benchmark qw(cmpthese);

sub fibStep {
    my $n = shift;
    return [$n->[1], $n->[0] + $n->[1]];
}

sub fibPair {
    my ($n, $fs, $fp) = @_;
    return [0,1] if ($n == 0);
    return $fs->($fp->($n-1,$fs,$fp))
}

sub fastFib {
    my $n = shift;
    my $fs = \&fibStep;
    my $fp = \&fibPair;
    my $fib_num = $fp->($n,$fs,$fp);
    return $fib_num->[0];
}

my %cache;

sub fib{
    my $n = shift;
    unless (exists $cache{$n}){
    if($n < 2){
        $cache{$n} = 1;
    }else{   
        $cache{$n} = fib($n-1) + fib($n-2);
    }
    }
    return $cache{$n};
}

my $number = 50;
my $count = 10000000;

my $fibcache = \&fib;
my $fibfast = \&fib;

cmpthese($count, {
        'Cache' => $fibcache->($number),
        'Fast' => $fibfast->($number)
    });