[OT] fastest fibbonacci

[Matthias Bentrup via Digitalmars-d]

On Sunday, 23 October 2016 at 23:17:28 UTC, Stefam Koch wrote:
> On Sunday, 23 October 2016 at 19:59:16 UTC, Minas Mina wrote:
>> On Sunday, 23 October 2016 at 13:04:30 UTC, Stefam Koch wrote:
>>> Hi Guys,
>>>
>>> while brushing up on my C and algorithm skills, accidently 
>>> created a version of fibbonaci which I deem to be faster then 
>>> the other ones floating around.
>>>
>>> It's also more concise
>>>
>>> the code is :
>>>
>>> int computeFib(int n)
>>> {
>>>     int t = 1;
>>>     int result = 0;
>>>
>>>     while(n--)
>>>     {
>>>         result = t - result;
>>>         t = t + result;
>>>     }
>>>
>>>    return result;
>>> }
>>
>> You can even calculate Fibonacci in O(1).
>
> An approximation of it.

The fibonacci sequence can be represented exactly as a linear 
combination of two exponential functions, but the two bases of 
the exponentials and the linear multipliers of them are 
irrational numbers, which cannot be represented exactly on a 
computer.

However the rounding error is so small, that rounding to int will 
give you always the correct answer as long as you stay within the 
precision limit of the floating point type you use, e.g. a real 
should give you 64-bit fibonacci in O(1), if the exponential 
function is O(1).

PS: the exact formula is fib(n) = 1/sqrt(5) * (0.5 + 
0.5sqrt(5))^n - 1/sqrt(5) * (0.5 - 0.5sqrt(5))^n. If you round to 
integer anyway, the second term can be ignored as it is always <= 
0.5.