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.

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.