Binet's Fibbonacci formula in ruby

binet.md

Binet's Fibbonacci formula

Fibonacci algorithms come up frequently in coding interviews and programming excercises.

I'll compare two techniques for generating fibonacci numbers in ruby

• Dynamic programming
• Binet's formula

Algorithms

Find the N th Fibonacci number

Dynamic Programming

n = 298
state = [1,1]; n.times  {  state.push(state[-1] + state[-2]) } puts state.last.to_i

Result:

222232244629420445529739893461909967206666939096499764990979600

Pros

• The result is correct.

Cons

• This algorithm runs in O(n) linear time.

• My naive implementation above fills a 300-element array with integers.

An improvement can be made to throw away the unused values from the array

n = 298
state = [1,1];

n.times do
  state.push(state[-1] + state[-2])
  state.count > 2 && state.shift
end
puts state.last.to_i

Binet's Formula

n = 300
sqrt5 = Math.sqrt(5); 
( ((1 + sqrt5)** n) - ((1  - sqrt5)** n) ) / ((2 ** n) * sqrt5)

result:

222232244629422676106398124069050176556246085874450435841982464

Pros

• Runs in O(k) constant time (until the overhead of large integer addition takes over)

• Runs almost no space complexity

Cons

• Inaccurate due to rounding errors with floating point approximations of the irrational number square-root-of-5

Comparison

How accurate is Binet's formula? The following code displays the difference and percent difference between the two methods

state = [1,1]; 298.times  {  state << ( state[-1] + state[-2] ) }

sqrt5 = Math.sqrt(5)
def fib(n, sqrt5)
	return ( ( ((1 + sqrt5)** n) - ((1 - sqrt5)** n) ) / ((2 ** n) * sqrt5) ).to_i
end

results = []
state.each_with_index do |n, index|
	difference = (n - fib(index + 1, sqrt5))
	puts "N:#{index+ 1} " +
		 "⬤: #{n} " + 
		 "θ:#{ (difference/n) unless difference.zero?}% " + 
		 "Δ:#{difference}"
end

N is the index of the fibonacci number

⬤ (giant dot) is value the fibonacci number

Δ (delta) is the difference in the results produced by Binet's formula and dynamic programming

θ (theta) is the percent difference between the results produced by both algorithms

Results

Δ is 0 up until N = 72

N:71 ⬤: 308061521170129 θ:0%  Δ:0
N:72 ⬤: 498454011879264 θ:-1%  Δ:-1

Any problem requiring less than 72 elements of the fibonacci sequence will be accurate to a whole number integer with Binet's formula

At N = 300

N:300 
⬤:222232244629420445529739893461909967206666939096499764990979600 
θ:-1% 
Δ:-2230576658230607140209349579146777950670851002864

our result is off by quite a lot, but the percent of deviation is constant.

Bonus

in Haskell

let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
let fib n = fibs ! (n-1)
fib 300

Result

222232244629420445529739893461909967206666939096499764990979600