Fibonacci implementations in Ruby

README.md

Fibonacci in Ruby

Here's a benchmark for four Ruby implementations of a method to calculation the n^th Fibonacci number. The implementations:

1. fib_recursive - A memoized recursive version
2. fib_iterative - An iterative version
3. fib_phi - A version using Binet's formula via an implementation of the arithmetic of ℚ(φ)
4. fib_matrix - A version using Matrix exponentiation

While fib_phi is slower than fib_matrix, you can see that it has the same rate of growth.

fib_bench.rb

# Implementation of Binet's formula
require_relative "fib_phi"

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

  a, b = 0, 1

  2.upto(n) do |i|
    a, b = b, a + b
  end

  b
end

# In time: O(n)
# In memory: O(n)
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

require "benchmark"

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

N = ARGV.fetch(0) { 30000 }.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_phi") do
    ITERATIONS.times { fib_phi(N) }
  end

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

fib_phi.rb

# Binet's formula
require_relative "phi_rational"

# Binet's formula:
# F(N) = (phi^N - (1 - phi)^N)/(2*phi - 1)
def fib_phi(n)
  ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i
end

if __FILE__ == $PROGRAM_NAME
  if ARGV.empty?
    puts "Missing required argument <N>"
    puts ""
    puts "Usage:"
    puts "  ruby #{$PROGRAM_NAME} <N>     # Calculate the Nth Fibonacci number"
    exit 1
  end

  n = ARGV[0].to_i

  puts fib_phi(n)
end

phi_rational.rb

# Helper method for creating phi-rational numbers.
def PhiRational(a, b = 0)
  case a
  when PhiRational
    a
  else
    PhiRational.new(a, b)
  end
end

class PhiRational
  attr_reader :a, :b

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

  # (a + b*p) + (c + d*p) = (a + c) + (b + d)*p
  def +(other)
    other = PhiRational(other)

    PhiRational(a + other.a, b + other.b)
  end

  def -(other)
    self + PhiRational(other).inverse
  end

  # -(a + b*p) = -a + -b*p
  def inverse
    PhiRational(-a, -b)
  end

  # |a + b*p| = a^2 + a*b - b^2
  def norm
    Rational(a*a + a*b - b*b)
  end

  # (a + b*p) * (c + d*p) = (a*c + b*d) + (a*d + b*c + b*d)*p
  def *(other)
    other = PhiRational(other)

    c = other.a
    d = other.b

    PhiRational(a*c + b*d, a*d + b*c + b*d)
  end

  def /(other)
    self * PhiRational(other).reciprocal
  end

  # 1/(a + b*p) == (a + b)/(a^2 - a*b + b^2) - (b*p)/(a^2 - a*b + b^2)
  def reciprocal
    PhiRational((a + b)/self.norm, -b/self.norm)
  end

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

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

    while n.nonzero?
      if n.odd?
        result *= base
        n -= 1
      end

      base *= base
      n /= 2
    end

    result
  end

  def to_s
    "(#{a}) + (#{b})p"
  end
  alias_method :inspect, :to_s
end