Fibonacci!

fib_bench.rb

require "benchmark"

# Basic iterative version
def fib_iterative(n)
  return 0 if n == 0
  return 1 if n == 1

  fibs = [0,1]

  2.upto(n) do |i|
    old_fib  = fibs[1]
    new_fib  = fibs[1] + fibs[0]

    fibs  = [old_fib, new_fib]
  end

  fibs[1]
end

# Recursive solution (with cache)
def fib_recursive(n, cache = {})
  return 0 if n == 0
  return 1 if n == 1
  return cache[n] if cache.key?(n)

  cache[n] = fib_recursive(n - 1, cache) + fib_recursive(n - 2, cache)

  cache[n]
end

# Matrix solution
require "matrix"

FIB_MATRIX = Matrix[[1,1],[1,0]]
def fib_matrix(n)
  (FIB_MATRIX**(n-1))[0,0]
end

# Binet's formula
require_relative "phi_rational"

def fib_phi(n)
  ((PhiRational.new(0,1)**n - PhiRational.new(1,-1)**n)/PhiRational.new(-1, 2)).a.to_i
end

# Note: if the input is too large, the recursive solution will
#       recurse too much and crash

N = ARGV.fetch(0) { 7500 }.to_i

ITERATIONS = 50

puts ""
puts "Benchmarking fib(#{N})..."
puts ""

Benchmark.bmbm do |x|
  x.report("fib_iterative") do
    ITERATIONS.times { fib_iterative(N) }
  end

  x.report("fib_recursive") do
    ITERATIONS.times { fib_recursive(N) }
  end

  x.report("fib_phi") do
    ITERATIONS.times { fib_phi(N) }
  end

  x.report("fib_matrix") do
    ITERATIONS.times { fib_matrix(N) }
  end
end

phi_rational.rb

class PhiRational
  attr_reader :a, :b

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

  def +(other)
    PhiRational.new self.a + other.a,
                    self.b + other.b
  end

  def -(other)
    self + other.inverse
  end

  def inverse
    PhiRational.new -a, -b
  end

  def det
    Rational(a*a + a*b - b*b)
  end

  def *(other)
    c = other.a
    d = other.b

    PhiRational.new a*c + b*d,
                    a*d + b*c + b*d
  end

  def /(other)
    self * other.reciprocal
  end

  def reciprocal
    PhiRational.new Rational(a + b, self.det),
                    Rational(-b,    self.det)
  end

  def ==(other)
    self.a == other.a && self.b == other.b
  end

  def to_s
    "(%s) + (%s)p" % [a,b]
  end

  def **(n)
    base   = PhiRational.new(a,b)
    result = PhiRational.new(1,0)

    while n.nonzero?
      if n[0].nonzero?
        result *= base
        n -= 1
      end

      base *= base
      n /= 2
    end

    result
  end
end