In my previous post, I had a seemingly 'elegant' solution of the fibonacci sequence using recursion, but alas, it was extremely inefficient and basically dropped dead at n > 40 (thanks to the Soothsayer for asking its asymptotic performance). Here is my second attempt to write a non-recursive version of Fibonacci number:
The new code runs fine for at least n = 65536 (i was impatient to test for numbers greater than that).
int
fib(int n)
{
unsigned long long n_minus1 = 1, n_minus2 = 1, current_value = 0;
unsigned int i = 0;
printf("fib(%3u) value is 1\nfib(%3u) value is 1\n", 1, 2);
for(i = 3; i <= n; i++)
{
current_value = n_minus1 + n_minus2;
n_minus2 = n_minus1;
n_minus1 = current_value; printf("fib(%3u) value is %llu\n", i, current_value);
}
return 0;
}/* fib */
How about the Haskell version? I will post it later.
4 comments:
show us pictures of your love shack! :)
maybe this will work for fibo:
#define p(y) printf("%ul", y)
unsigned long x,y,z;
x=1;y=1;z=1;
p(y);p(y);
while(y>=z){z=y;y+=x;x=z;p(y);}
yeap, your solution indeed generates the sequence correctly, but the catch is it is an infinite one. :) One of the requirements is to generate the n-th fib number specified through the function parameter.
:P the function should just continue until wraparound 32-bit wraparound.
Post a Comment