Fast Fibonacci method

Ruby
1

The fastest pure-Ruby Fibonacci method I have been able to come up with
is a
copy of the GMP algorithm described at
http://www.swox.com/gmp/manual/Fibonacci-Numbers-Algorithm.html

Is there a Ruby implementation that gets better time results for the
millionth Fibonacci number (timing code included at bottom) ?

class Integer
FibonacciCache = Hash.new do |hash, key|
subkey = key.div(2)
case key.modulo(4)
when 1
hash[key] = (2hash[subkey] + hash[subkey - 1])(2*hash[subkey]

hash[subkey - 1]) + 2
when 3
hash[key] = (2hash[subkey] + hash[subkey - 1])(2*hash[subkey]

hash[subkey - 1]) - 2
else
hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
end
end
FibonacciCache[0] = 0
FibonacciCache[1] = 1

def fib
return FibonacciCache[self]
end

def fib_uncached
return FibonacciCache.dup[self]
end
end

start_time = Time.now
1_000_000.fib
p Time.now - start_time
puts “Doesn’t work !” unless (1…10).map { |i| i.fib } == [1, 1, 2, 3,
5, 8,
13, 21, 34, 55]

2

A slightly faster method :

class Integer
FibonacciCache = Hash.new do |hash, key|
if hash.has_key?(key - 1) and hash.has_key?(key - 2)
hash[key] = hash[key - 1] + hash[key - 2]
elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
hash[key] = hash[key + 2] - hash[key + 1]
else
subkey = key.div(2)
case key.modulo(4)
when 1
hash[key] = (2hash[subkey] + hash[subkey -
1])(2hash[subkey] -
hash[subkey - 1]) + 2
when 3
hash[key] = (2hash[subkey] + hash[subkey -
1])(2hash[subkey] -
hash[subkey - 1]) - 2
else
hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
end
end
end
FibonacciCache[0] = 0
FibonacciCache[1] = 1

def fib
return FibonacciCache[self]
end

def fib_uncached
return FibonacciCache.dup[self]
end
end

start_time = Time.now
1_000_000.fib
p Time.now - start_time
puts “Doesn’t work !” unless (1…10).map { |i| i.fib } == [1, 1, 2, 3,
5, 8,
13, 21, 34, 55]

3

Other suggesgtions (untested, i.e. unmeasured)

  • use shift operator instead of *2 and /2

  • put your 4 alternatives (i.e. key % 4) as lambdas into another hash
    and then do
    algo[key % 4][subkey]

Kind regards

robert

4

On 27/05/06, Robert K. [email protected] wrote:

robert

Thanks for your suggestions. I tried both, but could only get the same
speed.