rchatley/extreme_startup — Issue #18: Wrong fibonacci algorithm ;)
Author: oc
Created: 2011-10-21 10:46:55+00:00
State: open

Code from server:

```ruby
def correct_answer
n = which_number
root5 = Math.sqrt(5)
phi = 0.5 + root5/2
Integer(0.5 + phi**n/root5)
end
```

While this is a mathematically clever way, this fails miserably on larger fibonaccis due to precision issues. sqrt(5) is an irrational number, its precision is calculated to over 1 mill decimals. Ruby float: ```Math.sqrt(5) == 2.23606797749979``` is just too imprecise.

It actually fails already with fib(71):

```ruby
def gr_fib(n)
root5 = Math.sqrt(5)
phi = 0.5 + root5/2
Integer(0.5 + phi**n/root5)
end
```

```
>> (69...72).map { |n| gr_fib n }
=> [117669030460994, 190392490709135, 308061521170130]
>> 117669030460994+190392490709135
=> 308061521170129
```

I suggest to use an iterative version instead. For instance:

```ruby
def fib(n)
a, b = 0, 1
(0...n).each { |_| a, b = b, a + b }
a
end
```