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.