my @fib4_cache;
sub fib4 {
my $n = shift;
return $fib4_cache[$n] //= do {
$n < 2 ? $n : fib4($n-1) + fib4($n-2)
};
}
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4
fib1 88.7/s -- -100% -100% -100%
fib2 219835/s 247838% -- -89% -91%
fib3 2073455/s 2338415% 843% -- -19%
fib4 2551114/s 2877136% 1060% 23% --
####
cmpthese(-1, {
fib1 => q{ fib1 20 },
fib2 => q{ fib2 20 },
fib3 => q{ fib3 20 },
fib4 => q{ fib4 20 },
});
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4
fib1 87.4/s -- -100% -100% -100%
fib2 223254/s 255377% -- -89% -91%
fib3 2071504/s 2370384% 828% -- -20%
fib4 2579867/s 2952119% 1056% 25% --
##
##
my @fib5_cache;
sub fib5 {
my $n = shift;
return $fib5_cache[ $n ] //= do {
$n < 2 ? $n
: ( $fib5_cache[ $n-1 ] //= fib5($n-1) )
+ ( $fib5_cache[ $n-2 ] //= fib5($n-2) ) ## corrected; thanks to moriitz
};
}
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4 fib5
fib1 89.0/s -- -100% -100% -100% -100%
fib2 218452/s 245352% -- -89% -91% -91%
fib3 2022174/s 2272005% 826% -- -18% -20%
fib4 2478824/s 2785096% 1035% 23% -- -2%
fib5 2537045/s 2850512% 1061% 25% 2% --