closed-form-fibonacci.rb

##— http://github.com/raganwald/homoiconic/tree/master/2008-12-17/another_fibonacci.md
# Fibonacci has a closed form? That shit is probably pretty fast…
# The only problem is that ruby can't handle exponenting floats by modestly large values: Fib[10000] => Infinity
Fib = lambda do |n| 
  sqrt5 = Math.sqrt(5)
  phi   = (1+sqrt5)/2
  (f    = (phi**n-(-1/phi)**n)/sqrt5).infinite? ? f : f.floor
end
  
A000045 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]
seq = A000045.to_enum(:each_with_index).inject([["Fib:", "Sloane:"]]) do |array, (fi, i)|
  array << [Fib[i], fi]
end.map {|f1, f2| f1.to_s.ljust(9) + "== #{f2}"}
puts seq

=begin
 The comparable mathematica (6) code:
  sqrt5 = Sqrt[5];
  phi = (1 + Sqrt[5])/2;
  fib[n_] := (phi^n - (-1/phi)^n)/sqrt5;
 fails at `N[fib[1000000000]]` vs Fib[1474] for ruby 1.{8.7,9.1}.
=end