# Fast Fibonacci method

**URL:** <https://www.ruby-forum.com/t/fast-fibonacci-method/61772>\
**Category:** Ruby\
**Created:** [May 27, 2006, 1:15am UTC](https://www.ruby-forum.com/t/fast-fibonacci-method/61772 "2006-05-27T01:15:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [May 27, 2006, 1:15am UTC](https://www.ruby-forum.com/t/fast-fibonacci-method/61772/1 "2006-05-27T01:15:18Z")

</div>

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](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] = (2_hash[subkey] + hash[subkey - 1])_(2\*hash[subkey]

## hash[subkey - 1]) + 2 when 3 hash[key] = (2_hash[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]

---

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [May 27, 2006, 1:40am UTC](https://www.ruby-forum.com/t/fast-fibonacci-method/61772/2 "2006-05-27T01:40:28Z")

</div>

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] = (2_hash[subkey] + hash[subkey -  
1])_(2_hash[subkey] -  
hash[subkey - 1]) + 2  
when 3  
hash[key] = (2_hash[subkey] + hash[subkey -  
1])_(2_hash[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]

---

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [May 27, 2006, 11:37am UTC](https://www.ruby-forum.com/t/fast-fibonacci-method/61772/3 "2006-05-27T11:37:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [May 28, 2006, 5:53pm UTC](https://www.ruby-forum.com/t/fast-fibonacci-method/61772/4 "2006-05-28T17:53:21Z")

</div>

On 27/05/06, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> robert

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