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.
