DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

# Fibonacci Numbers In Ruby

02.22.2007
| 4255 views |
```        From: http://www.ruby-forum.com/topic/67217
Author: C Erler

http://www.swox.com/gmp/manual/Fibonacci-Numbers-Algorithm.html

```
```
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
#fibs = (5..10).map { |i| i.fib }
#fibs = (1..100000).map { |i| i.fib }
#puts fibs.size
#puts fibs.last
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]

#-----------------------------------------------------------------------

# Author: Shin-ichiro HARA

class QR3

def inspect
"{#{@a},#{@b}}"
end
alias to_s inspect

def initialize(a, b)
@a, @b = a, b
end

def *(r)
u = (@a + @b)*(r.a + r.b)
v = (@a - @b)*(r.a - r.b)
QR3.new((u + v)>>1, @b*r.b + ((u - v)>>1))
end

def **(n)
if n == 0
QR3.new(1, 0)
elsif n > 0
z = x = self
n -= 1
while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)
x *= x
end
z
end
end
end

def fib_qr3(n)
(QR3.new(0, 1)**n).b
end

n = 1000

start_time = Time.now
fib_qr3(n)
p Time.now - start_time

```
```
Benchmarking various fib implementations:
```
```
#!/opt/local/bin/ruby1.9

# Update Ruby via MacPorts:
# port info ruby19
# sudo port install ruby19
# http://www.macports.org/install.php
# http://trac.macports.org/wiki/InstallingMacPorts

require 'benchmark'

# From: http://www.ruby-forum.com/topic/67217
# Author: C Erler

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

#puts "Doesn't work !" unless (1..10).map { |i| i.fib } == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

#--------------------------

# Author: Shin-ichiro HARA

class QR3

def inspect
"{#{@a},#{@b}}"
end
alias to_s inspect

def initialize(a, b)
@a, @b = a, b
end

def *(r)
u = (@a + @b)*(r.a + r.b)
v = (@a - @b)*(r.a - r.b)
QR3.new((u + v)>>1, @b*r.b + ((u - v)>>1))
end

def **(n)
if n == 0
QR3.new(1, 0)
elsif n > 0
z = x = self
n -= 1
while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)
x *= x
end
z
end
end
end

def fib_qr3(n)
(QR3.new(0, 1)**n).b
end

#--------------------------

# See:
# - Tailin' Ruby, http://judofyr.net/posts/tailin-ruby.html & http://github.com/judofyr/recursive/tree/master
# - Re: Ruby and recursion (Ackermann benchmark), http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/145593

class Class
# Found in [ruby-talk:145593]
def tailcall_optimize(*methods)
methods.each do |meth|
org = instance_method(meth)
define_method(meth) do |*args|
throw(:recurse, args)
else
result = catch(:done) do
loop do
args = catch(:recurse) do
end
end
end
result
end
end
end
end
end

class Fib
def acc(i, n, result)
if i == -1
result
else
acc(i - 1, n + result, n)
end
end

def fib(i)
acc(i, 1, 0)
end
end

class RescueFib < Fib
RunAgain = Class.new(Exception)

def acc(i, n, result)
if i == -1
result
else
raise RunAgain
end
rescue RunAgain
i, n, result = i - 1, n + result, n
retry
end
end

class CatchFib < Fib
tailcall_optimize :acc
end

class RedoFib < Fib
define_method(:acc) do |i, n, result|
if i == -1
result
else
i, n, result = i - 1, n + result, n
redo
end
end
end

class IterativeFib < Fib
def acc(i, n, result)
until i == -1
i, n, result = i - 1, n + result, n
end
result
end
end

#--------------------------

# Fibonacci numbers with Ruby 1.9 Fibers
# http://www.davidflanagan.com/2007/08/fibonacci-numbers-with-ruby-19-fibers.html

class Generator
def initialize &block
@f = Fiber.new &block
end

def next?
@f.alive?
end

def next(*args)
@f.resume(*args)
end
end

fib2 = Generator.new do
x, y = 0, 1
loop do
Fiber.yield y
x,y = y,x+y
end
end

#--------------------------

# Re: Fast Fibonacci method
# http://www.ruby-forum.com/topic/67327

class Integer
def fib_tail_recursive a=1, b=0, p=1, q=0
if modulo(2).zero?
if zero?
b
else
p_p = p*p
div(2).fib_tail_recursive a, b, p_p + 2*p*q, p_p + q*q
end
else
(self - 1).fib_tail_recursive p*(a + b) + a*q, a*p + b*q, p, q
end
end

def fib_iterative
n, a, b, p, q = self, 1, 0, 1, 0
while n.nonzero?
a, b = p*(a + b) + a*q, a*p + b*q if n.modulo(2).nonzero?
p_p = p*p
n, p, q = n.div(2), p_p + 2*p*q, p_p + q*q
end
b
end
end

#------------------------------------------------------

num = 1_000_000
num = 10
num = 0
num = 1
num = 200_000
num = 100_000

ret1 = nil
ret2 = nil
ret3 = nil
ret4 = nil
ret5 = nil
ret6 = nil
ret7 = nil

Benchmark.bm(50) do |t|

t.report("#{num}.fib: ") do
ret1 = num.fib
end

t.report("fib_qr3(#{num}): ") do
ret2 = fib_qr3(num)
end

t.report("RedoFib.new.fib(#{num-1}): ") do
ret3 = RedoFib.new.fib(num-1)
end

t.report("IterativeFib.new.fib(#{num-1}): ") do
ret4 = IterativeFib.new.fib(num-1)
end

t.report("Fibers #{num}: fib2.next: ") do
(num).times { ret5 = fib2.next }
end

t.report("#{num}.fib_tail_recursive: ") do
ret6 = num.fib_tail_recursive
end

t.report("#{num}.fib_iterative: ") do
ret7 = num.fib_iterative
end

end

puts

if ret1 == ret2 && ret2 == ret3 && ret3 == ret4 && ret4 == ret5 && ret5 == ret6 && ret6 == ret7 then
puts "Succeeded: numbers are equal!"
end

puts

```
```
```
"Starting from scratch" is seductive but disease ridden