"Strong typing vs. strong testing"

[Raffael Cavallaro]

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