Python and Ruby – Fibonacci Numbers and Trial Division

I haven’t posted anything on here for a while, and thought I might do something. Recently, I picked up a book called Visual Quickstart Guide to Ruby. It’s a nice book which feeds bits of Ruby in bite-sized chunks. But that’s not what this post is for. One bit of the book mentioned Fibonacci numbers, and I thought perhaps I should write a program to generate the nth fibonacci number in Ruby, having already created one in Python long ago.

I also thought it might be interesting to see how efficient the two languages are in computing them. Then decided to go a little further, to compare how quickly they can do trial divisions (a way to test whether a number is a prime number.

Fibonacci code for Python:

from time import time
import sys

def fibonacci(n):
	if (n == 0) | (n == 1):
		return n
	else:
		return fibonacci(n - 1) + fibonacci(n - 2)

if __name__ == "__main__":
	arg = int(sys.argv[1])
	tstart = time()
	print fibonacci(arg)
	tend = time()
	print "Time elapsed: {0}".format(tend - tstart)

Fibonacci code for Ruby:

def fibonacci(n)
	if n == 0 || n == 1
		return n
	else
		return fibonacci(n - 1) + fibonacci(n - 2)
	end
end

if __FILE__ == $0
	arg = ARGV[0].to_i
	tstart = Time.now
	puts fibonacci(arg)
	tend = Time.now
	puts "Time elapsed: #{tend - tstart}"
end

Trial division with Python:

from time import time
import math
import sys

def isitprime(target):
	if target < 2:
		return False

	for i in range(2, int(math.sqrt(target))):
		if target % i == 0:
			return False

	return True

if __name__ == "__main__":
	number = int(sys.argv[1])
	tstart = time()
	if isitprime(number) == True:
		print "{0} is a prime number.".format(number)
	else:
		print "{0} is not a prime number.".format(number)
	tend = time()
	print "Time elapsed: {0}".format(tend - tstart)

Trial division with Ruby:

def isitprime(target)
	if target < 2
		return false
	end
	2.upto(Math.sqrt(target).to_i) do |i|
		if target % i == 0
			return false
		end
	end
	return true
end

if __FILE__ == $0
	number = ARGV[0].to_i
	tstart = Time.now
	if isitprime(number) == true
		puts "#{number} is a prime number."
	else
		puts "#{number} is not a prime number."
	end
	tend = Time.now
	puts "Time elapsed: #{tend - tstart}"
end

The results:

Calculating the 20th fibonacci number.
Python = 0.005s
Ruby = 0.003s

Calculating the 40th fibonacci number.
Python = 69.726s
Ruby = 32.458s

So clearly, the Ruby implementation was faster… twice as fast as the Python implementation for larger iterations.

Check whether 1000000000039 is a prime number (it is).
Python = 0.297s
Ruby = 0.473s

Check whether 9000000000059 is a prime number (again, it is).
Python = 0.895s
Ruby = 1.425s

So for trial divisions, Ruby was approximately 60% slower than Python.

It’s quite curious, because both types of computations are intensive integer calculations, yet the performance trends differ between the two tasks. I should note however, that I intentionally used identical algorithms and styles between the two languages. Perhaps they are more idiomatic and efficient implementations for each language, which might produce very different results.

Advertisement