fibs.rb

fibs.rb

# ruby fibs

require 'benchmark'

# === stupid ===
def recursive_fib(n)
  n <= 1 ? n : recursive_fib(n-1) + recursive_fib(n-2);
end

puts Benchmark.measure { recursive_fib(35) }
# 1.140000   0.000000   1.140000 (  1.146576)

# === good ===
def linear_fib(n)
  (2..n-1).each_with_object([1, 1]) { |i, arr| arr << arr[-1] + arr[-2] }.last
end

puts Benchmark.measure { linear_fib(200_000) }
# 0.760000   0.460000   1.220000 (  1.222171)

# === gooder ===
def linear_cached_fib(n)
  cache = [1, 1]
  (2..n-1).each do |i|
    a = cache[0] + cache[1]
    cache = [cache[1], a]
  end
  cache
end

puts Benchmark.measure { linear_cached_fib(200_000) }
# 0.630000   0.430000   1.060000 (  1.059694)

# === stupid good ===
def fast_double_fib(n)
  if n == 0
    return 0, 1
  else
    a, b = fast_double_fib(n / 2)
    c = a * (b * 2 - a)
    d = a * a + b * b
    d = a * a + b * b
    if n % 2 == 0
      return c, d
    else
      return d, c + d
    end
  end
end

puts Benchmark.measure { fast_double_fib(10_000_000) }
# 1.870000   0.010000   1.880000 (  1.887631)