On 2010-10-01 22:44:11 -0400, Paul Rubin said:
I have no idea what that fancy algorithm is doing, but the number it
prints appears to be the 2000th Fibonacci number rather than the 1000th.
I think you're mistaken. fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2
... fib(11)= 89 ...
fib(1000) =
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
If
you like we can do it iteratively instead, which, as in haskel, takes
no perceptible time:
CL-USER 133 > (defun fib (x)
(if (< x 1) 0
(loop
repeat x
for previous = 0 then result
and result = 1 then (+ result previous)
finally (return result))))
FIB
CL-USER 134 > (compile 'fib)
FIB
NIL
NIL
CL-USER 135 > (time (fib 1000))
Timing the evaluation of (FIB 1000)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 60088 bytes
0 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
The
relevant points are:
1. common lisp implementations produce fast code
2. the result of fib(1000) is going to overflow c integer types
warmest regards,
Ralph
--
Raffael Cavallaro
--
http://mail.python.org/mailman/listinfo/python-list
