def fib n
a, b = 0, 1
n.times {a, b = b, a + b}
return a
end
?
Name:
Anonymous2011-05-16 1:36
How's this?
int fib (int a, int b, int n)
{
if (n) return fib (b, a+b, n-1);
else return a;
}
and you call it like this:
fib (1, 1, times)
All in glorious C.
>>21
ARE YOU FUCKING RETARDED >>13 IS JUST A TAIL-RECURSIVE SOLUTION WITHOUT A SUGARY WRAPPER FUNCTION AND IT SAYS IT RIGHT THERE IN >>13 HOW YOU CALL IT.
>>32
You also have to rearrange the stack. On x86, the return address is stored on the stack, so it's one more thing to worry about while rearranging.
No problem if you're using a calling convention that uses registers for the return value and, possibly, the arguments.
>>36
After fib 1000000 and higher, it'll be getting quite slow( takes one minute to calculate 10^6 fibs here ). This would be true even in an implementation which uses fixed size bignums and is written in assembly (the difference in the generated assembly for the loop between the C, Common Lisp and x86 asm version isn't too big here to actually make a big enough difference). >>6's solution might be faster and I plan on trying it, but it is indeed inaccurate as irrational numbers are not computable with infinite precision (if real numbers can even exist consistently as anything but ideal mathematical objects is a mystery to me), but the result could be accurate enough given enough precision. I don't feel like waiting hours for fib 10^9 to finish computing using the accurate algorithm, so if we want to test accuracy, mind giving me a hash of the result or better yet the result itself?
<interactive>:1:0:
Couldn't match expected type `t1 -> t'
against inferred type `[Integer]'
In the expression: fibs (1000000000)
In the definition of `it': it = fibs (1000000000)
Name:
Anonymous2011-05-17 0:12
First, for the second command, you would use fibs !! 1000000000, as fibs is a list, not a function.
Second, the space requirements will literally murder your computer, as the system allocates a billion bignums.