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!
