## Quick Fibonacci calculations are nothing new

by bigpresh on Jan.07, 2009, under Perl, Programming, Uncategorized

Just read this post by Ben Newman (found via Reddit).

Now, the use of C++ templates to calculate the value at compile time rather than runtime is midly clever and amusing (if also impractical and convoluted) but the fact that it can calculate a Fibonacci number quickly is nothing new; it’s solely down to remembering the values you’ve already calculated, and not calculating them again needlessly.

If you’re not familiar with Fibonacci numbers, `f(n)` is equal to `f(n-1) + f(n-2)`, i.e. the sum of the last two numbers in the sequence. An easy way to calculate them is with a recursive function, e.g.:

sub fib { my $n = shift; return 0 if ($n == 0); return 1 if ($n == 1); return fib($n-1) + fib($n-2); }

That will be very slow for higher values of $n, however, as it needlessly makes lots of calls to fib() to calculate values it has already calculated.

For instance, to calculate fib(10), it will call fib(9) – which in turn will call fib(8)… etc.

Remembering the values you’ve already calculated makes things far, far quicker.

For an example, here’s the previous way of doing it, compared to a version which remembers the values it has already calculated:

#!/usr/bin/perl use strict; use Benchmark; timethese(1, { 'fib1' => sub { for my $x (0..40) { print "$x => " . fib1($x) . "\n"; } }, 'fib2' => sub { for my $x (0..40) { print "$x => " . fib2($x) . "\n"; } }, }); sub fib1 { my $n = shift; return 0 if ($n == 0); return 1 if ($n == 1); return fib1($n-1) + fib1($n-2); } my %cache; sub fib2 { my $n = shift; return 0 if ($n == 0); return 1 if ($n == 1); return $cache{$n} if $cache{$n}; return $cache{$n} = fib2($n-1) + fib2($n-2); }

Both methods return exactly the same results, but the time taken changes drastically:

fib1: 1959 wallclock secs (1912.99 usr + 2.85 sys = 1915.84 CPU) fib2: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)

Finally, we needn’t implement the code to remember previous calculations ourselves; the Memoize CPAN module can take care of all of that for us:

#!/usr/bin/perl use strict; use Memoize; my $n = $ARGV[0] or die "Usage: $0 number"; print "Fibonacci number $n is " . fib($n); memoize('fib'); sub fib { my $n = shift; return 0 if ($n == 0); return 1 if ($n == 1); return fib($n-1) + fib($n-2); }

Notice the `memoize('fib')`? That’s all that is needed to tell Memoize to remember the results of that sub, and, if called again with the same input, simply return the previous result.

The timing?

[davidp@supernova:~/dev/scripts/perl]$ time ./fibonacci-memoize.pl 70 Fibonacci number 70 is 190392490709135 real 0m0.060s user 0m0.052s sys 0m0.008s

0.06 seconds to calculate the 70th number in the Fibonacci sequence. Not bad.

January 8th, 2009 on 7:59 am

Just studied c++ and still burying my head just to learn the crop. Wheeww, I think I need to freshen my mind to continue understanding this c++ thing, its concepts and everything. Mathematical related…ewee…really need some fresh air.lol. But I love the whole idea.