Some time ago at work my colleagues and I were discussing the performance of various programming languages (Python, C++, C#, VBA, JavaScript, Java, VB.Net, Ruby) and which one was the fastest. I therefore started writing recursive Fibonacci methods for each language and timing their execution (anything to get out of doing real work!). This then led to looking into faster methods of generating the Fibonacci sequence. Below are three different method for generating the sequence; recursive (slow), matrix (fast), and pure maths (super fast). Though I have yet to come across a need to generate a Fibonacci number in one of my applications, I thought I would share this as it may be of interest to some of you out there.

PYTHON Recursive (slow)

import time

def fibonacci(n):
    if n < 2:
     return n
    else:
     return fibonacci(n-1) + fibonacci(n-2)

start = time.clock()
for i in range(36):
    print "n=%d => %d" % (i, fibonacci(i))
end = time.clock()
print "Time elapsed = ", end - start, "seconds"

Results: Time elapsed =  14.2846501707 seconds

Matrix (fast) Note: This requires the python-numpy module (Ubuntu users can apt-get install python-numpy)

import time
import numpy

fibonacci_matrix = numpy.matrix([[1,1],[1,0]])
def fibonacci(n):
    return (fibonacci_matrix**(n-1)) [0,0]

start = time.clock()
for i in range(36):
    print "n=%d => %d" % (i, fibonacci(i))
end = time.clock()
print "Time elapsed = ", end - start, "seconds"

Results: Time elapsed =  0.0408389234748 seconds

Pure Maths (super fast)

import time
from math import sqrt

def fibonacci(n):
    root5 = sqrt(5)
    phi = 0.5 + root5/2
    return int(0.5 + phi**n/root5)

start = time.clock()
for i in range(36):
    print "n=%d => %d" % (i, fibonacci(i))
end = time.clock()
print "Time elapsed = ", end - start, "seconds"

Results: Time elapsed =  0.00034817521541 seconds

RUBY Recursive

def fibonacci(n)
    if n < 2
        n
    else
        fibonacci(n-1) + fibonacci(n-2)
    end
end

start_time = Time.now
36.times do |i|
    puts "n=#{i} => #{fibonacci(i)}"
end
end_time = Time.now
puts "Time elapsed = #{end_time - start_time} seconds"

Matrix

require 'matrix'

FIBONACCI_MATRIX = Matrix[[1,1],[1,0]]
def fibonacci(n)
 (FIBONACCI_MATRIX**(n-1)) [0,0]
end

start_time = Time.now
36.times do |j|
 puts "n=#{j} => #{fibonacci(j)}"
end
end_time = Time.now
puts "Time elapsed = #{end_time - start_time} seconds"

Pure Maths

def fibonacci(n)
 root5 = Math.sqrt(5)
 phi = 0.5 + root5/2
 Integer(0.5 + phi**n/root5)
end

start_time = Time.now
36.times do |j|
 puts "n=#{j} => #{fibonacci(j)}"
end
end_time = Time.now
puts "Time elapsed = #{end_time - start_time} seconds"

#########################################

For anyone who wishes to run some language benchmarks themselves (if you are really bored!!), here is the recursive sequence for other languages.

PHP

function fibonacci($n) {
    if ($n < 2) {
        return $n;
    }
    else {
        return fibonacci($n - 1) + fibonacci($n - 2);
    }
}

$start_time = microtime(true);
for ($i = 0; $i < 36; $i++) {
    $fib = fibonacci($i);
    print "n=$i =>; $fibn";
}

$end_time = microtime(true);
$diff_seconds  = $end_time - $start_time;
print "Time elapsed = $diff_seconds seconds";

VBA

Private Function Fibonacci(ByVal n As Integer) As Long
    If n < 2 Then
        Fibonacci = n
    Else
        Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
    End If
End Function

Sub Main()
    Dim StartTime As Date
    Dim EndTime As Date

    StartTime = Time
    For Index = 0 To 35
        Debug.Print "n=" & Index & " => " & Fibonacci(Index)
    Next
    EndTime = Time

    Debug.Print "Time elapsed = " & (EndTime - StartTime) * 86400
End Sub

C#

static int Fibonacci(int n)
    {
        if (n < 2)
        {
            return n;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

    static void Main(string[] args)
    {
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int i = 0; i < 36; i++)
        {
            Console.WriteLine("n={0} => {1}", i, Fibonacci(i));
        }
        stopwatch.Stop();
        TimeSpan excecutionTime = stopwatch.Elapsed;
        Console.WriteLine("Time elapsed = {0:00}.{1:00} Seconds",
                excecutionTime.Seconds, excecutionTime.Milliseconds / 10);
        Console.ReadLine();
    }

JAVA

public static void main(String[] args) {
 long start = System.currentTimeMillis( );
 for (int i = 0; i < 36; i++)
        {
      System.out.println("n=" + i + " => " + Fibonacci(i));
        }
 long end = System.currentTimeMillis( );
 double deltaT = end-start;
 System.out.println("Time elapsed = " + deltaT/1000 + " seconds.");
 try {
  System.in.read( );
 } catch (IOException e) {
  e.printStackTrace();
 }
}

public static int Fibonacci(int n) {
        if (n < 2)
        {
            return n;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
}

Enjoy!