Benchmarking the non-iterative, closed-form solution for Fibonacci numbers

Paul Hankin came up with a formula to calculate a Fibonacci numbers without recursively (or iteratively) generating prior ones. Don’t get too excited: his non-iterative, closed-form solution in O(n²). That means it’s slow when n is big. I was curious how well this would do in Perl. It’s very fast in Python and dog slow in Perl.

🐇 🐇 🐇 🐇 🐇

Paul’s Python solution moves a bunch of bits around:

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

print fib(1000);

It's pretty speedy:

$ python --version
Python 2.7.14
$ time python fibo.py
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real	0m0.063s
user	0m0.028s
sys	0m0.030s

Doing the same thing in Perl requires bigint pretty quickly. Notice those bit shifts get big quickly:

use bigint;

print fibonacci( 1000 ) . "\n";

sub fibonacci {
    my $n = shift;
    (4 << $n*(3+$n)) / ((4 << 2*$n) - (2 << $n) - 1) 
        & ((2 << $n) - 1)
    }

The Perl version of the same thing takes much, much longer:

$ perl -v

This is perl 5, version 28, subversion 0 (v5.28.0) built for darwin-2level

$ time perl fibo.pl
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real	1m3.619s
user	1m3.227s
sys	0m0.134s

That's really slow compared to the Python version but it's much faster than a pure recursive solution.

The iterative Perl solution takes twice as long as the non-iterative, closed-form Python solution:

use bigint;

my @cache = ( 1, 1 );

foreach ( 2 .. 1000 ) {
	$cache[$_] = $cache[$_-1] + $cache[$_-2];
	}

print "$cache[-1]\n";

This speed is a bit

$ time perl test.pl
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real	0m0.102s
user	0m0.091s
sys	0m0.010s

The caching, recursive version is a little slower (the non-caching version might finish next year if I don't interrupt it). Perl v5.28 adds the ability to initialize named hashes and arrays as state variables:

use v5.28;
use bigint;

print fibonacci( 1000 ) . "\n";

sub fibonacci {
	state @cache = qw(1 1);
	my $n = shift;
	return $cache[$n] if $n < @cache;
	return $cache[$n] = fibonacci( $n-1 ) + fibonacci( $n-2 );
	}

The imprecision from the scientific notation isn't good:

$ time perl test.pl
7.03303677114228e+208

real	0m0.139s
user	0m0.120s
sys	0m0.016s

So, Perl can get close to the same speed by giving up some memory but it can't use Paul's cleverness to do it.

---

Aristotle adds some techniques in the comments so I went back to try all of these programs again but on macOS Mojave with v5.28. The numbers so far are basically the same. He suggests this code at first, which is a lot of nested structure:

use Math::BigInt;
print fibonacci( 1000 ) . "\n";
sub fibonacci {
	my $n = shift;
	(
	Math::BigInt->from_bin('100'.('0'x($n*(3+$n))))
		/
	Math::BigInt->from_bin(('1'x$n).'01'.('1'x$n))
	)
		&
	Math::BigInt->from_bin('1'.('1'x$n))
	}

The results show a bit more than the 15% speedup he mentions but that's unsatisfactory:

$ time perl test.pl
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real	0m56.627s
user	0m55.252s
sys	0m0.360s

He then suggests this simple adjustment:

use Math::GMP ':constant';
print fibonacci( 1000 ) . "\n";

sub fibonacci {
    my $n = shift;
    (4 << $n*(3+$n)) / ((4 << 2*$n) - (2 << $n) - 1)
        & ((2 << $n) - 1)
    }

Now this is really fast, but not that much faster than the Python version (maybe a reduction of about half). That's still :

$ time perl test.pl
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real	0m0.056s
user	0m0.024s
sys	0m0.018s