fibs.rb

class Fib
  def fib(n)
    return n if n <= 1
    fib(n-1) + fib(n-2)  
  end
end

class FibMemo
  attr_accessor :fibs

  def initialize
    @fibs = []
  end

  def fib(n)
    if n <= 1
      return n
    elsif fibs[n]
      return fibs[n]
    else
      fibs[n] = fib(n-2) + fib(n-1)
    end
    return fibs[n]
  end
end

class FibIter
  def fib(n)
    return n if n <= 1
    x, y = 0, 1
    n.times do
      x, y = y, x+y
    end
    x
  end
end

class FibIterMemo < FibIter
  def initialize
    @fibs = []
  end

  def fib(n)
    if @fibs[n]
      return @fibs[n]
    else
      @fibs[n] = super
    end
  end
end

class FibConst
  def fib(n)
    ((phi ** n - psi ** n) / (phi - psi)).round
  end

private
  def phi
    @phi ||= (1 + Math.sqrt(5)) / 2.0
  end

  def psi
    @psi ||= (1 - Math.sqrt(5)) / 2.0
  end
end


n = 32
puts "recursive %d" % Fib.new.fib(n)
puts "memoize   %d" % FibMemo.new.fib(n)
puts "iterate   %d" % FibIter.new.fib(n)
puts "itermemo  %d" % FibIterMemo.new.fib(n)
puts "const     %d" % FibConst.new.fib(n)

puts "%%% SINGLE RUN"
require 'benchmark'
t = 1_000
[8, 16, 32, 64, 128].each do |n|
  Benchmark.bm do |x|
    x.report("#{n} recursive") { 1000.times { Fib.new.fib(n) }} if n < 30
    x.report("#{n} memoize  ") { 1000.times { FibMemo.new.fib(n) }}
    x.report("#{n} iterate  ") { 1000.times { FibIter.new.fib(n) }}
    x.report("#{n} itermemo ") { 1000.times { FibIterMemo.new.fib(n) }}
    x.report("#{n} const    ") { 1000.times { FibConst.new.fib(n) }}
  end
end

puts "%%% REUSED"
require 'benchmark'
t = 10_000
[8, 16, 32, 64, 128].each do |n|
  Benchmark.bm do |x|
    x.report("#{n} recursive") { f = Fib.new;         1000.times { f.fib(n) }} if n < 30
    x.report("#{n} memoize  ") { f = FibMemo.new;     1000.times { f.fib(n) }}
    x.report("#{n} iterate  ") { f = FibIter.new;     1000.times { f.fib(n) }}
    x.report("#{n} itermemo ") { f = FibIterMemo.new; 1000.times { f.fib(n) }}
    x.report("#{n} const    ") { f = FibConst.new;    1000.times { f.fib(n) }}
  end
end