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

3 thoughts on “Benchmarking the non-iterative, closed-form solution for Fibonacci numbers”

  1. I thought maybe giving Math::BigInt less to do would help, and it does:
    use Math::BigInt;
    print fibonacci( shift ) . "\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))
    }

    But it’s not a satisfying speedup at all. I get under 15% improvement out of this. That division is what’s really slow, and evidently despite Math::BigInt::FastCalc having “some XS”, it just doesn’t go terribly fast… which seems like no surprise considering that it uses a decimal-based representation internally. I assume that’s why it’s so slow.

    (Why does it use such a bad representation? Who knows. My guess is that the original BigInt was more of a demo of what you can do with the then-new features in Perl 5… in which case it would have been chosen for ease of implementation in pure Perl implementation rather than whatever would be optimal for use in anger. If that’s how it came to be, then nobody ever revisited the resulting design choices.)

    Just plugging use Math::GMP ':constant' into your code as a replacement for the use bigint line, OTOH, speeds it up by multiple orders of magnitude. It should be about 3× faster than the Python version, in fact.

Comments are closed.