On 23.10.2016 21:59, 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).
The closed form does not give you an O(1) procedure that computes the
same as the above code (with the same wrap-around-behaviour).
If arbitrary precision is used, the result grows linearly, so the
calculation cannot be better than linear. I don't think the closed form
gives you a procedure that is faster than Θ(n·log n) in that case.
