Skip to content

Instantly share code, notes, and snippets.

@leifericf
Last active August 29, 2015 14:02
Show Gist options
  • Save leifericf/40c543a5237a6fce587c to your computer and use it in GitHub Desktop.
Save leifericf/40c543a5237a6fce587c to your computer and use it in GitHub Desktop.
Binet's Formula and Fibonacci Numbers
#!/usr/bin/env ruby
=begin
Ref. Python implementation from this answer on StackOverflow:
http://stackoverflow.com/a/7843192/195964
=end
include Math
=begin
Phi, as defined by Binet's formula:
http://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet
=end
PHI = ( 1 + 5 ** 0.5 ) / 2
=begin
Yields first n Fibonacci numbers.
Only yields correct result for n < 70, due to floating-point rounding errors.
=end
def fib( n )
( ( PHI ** n - ( 1 - PHI ) ** n ) / 5 ** 0.5 ).round
end
=begin
Rounding eliminates error introduced by modification to Binet's formula.
Does not verify that number given actually is a Fibonacci number.
Can be used to find Fibonacci number closest to a given number.
=end
def fib_inverse( n )
n < 2 ? n : ( log( n * 5 ** 0.5 ) / log( PHI ) ).round
end
(1..10).each do |n|
puts "#{n}: #{fib(n)} - #{fib_inverse(n)}"
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment