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.

  1. Any idea why it is so much slower in Perl?

  2. Can SPVM provide some improvement?

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>