On 2010-10-01 16:47:02 -0400, BartC said:
I had a quick look at Lisp to see if your claims had any basis. I tried
this program:
(defun fib (n)
(if (< n 2)
n
(+ n (fib (- n 1)) (fib (- n 2)) )
))
But it gave the wrong results and it took ages to figure out why. Even
after downloading a working version for comparison, it's was difficult
to spot the extraneous 'n' (I think I was concentrating on getting the
round brackets all in the right places).
I saw it immediately, but I'm familiar with lisp and you are not -
those two parentheses (what you call "round brackets") on a line by
themselves are a dead giveaway.
I thought you were saying that Lisp (and dynamic typing in general) was
better for pointing out errors? The above error in C would have been
picked up more easily I think (due to less parentheses clutter, and
more obvious separators between terms).
As for speed, executing fib(38) took about 60 seconds on my machine
(gnu clisp with no switches set). (Compared with 3.5 seconds, for my
own interpreted, dynamic language, and 0.6 seconds for C.)
Compiled lisp is fast, but you need to actually compile it:
CL-USER 96 > (defun fib (n)
(declare (optimize speed (debug 0)))
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
FIB
CL-USER 97 > (compile 'fib)
FIB
NIL
NIL
CL-USER 98 > (time (fib 38))
Timing the evaluation of (FIB 38)
User time = 0.888
System time = 0.002
Elapsed time = 0.877
Allocation = 142568 bytes
0 Page faults
39088169
which is in the same range as your .6 seconds for your equivalent c program.
What happens when you want fib(1000) or fib(1000000)? Then the naive
recursive version isn't very useful (it's just too slow), and the
result is going to overflow c integer types.
in lisp:
CL-USER 118 > (defun fact (n) (if (zerop n) 1 (* n (fact (1- n)))))
FACT
CL-USER 119 > (defun fib (n)
(/ (loop for k from 1 to n by 2
sum (/ (* (expt 5 (/ (1- k) 2)) (fact n))
(fact k) (fact (- n k))))
(expt 2 (1- n))))
FIB
CL-USER 120 > (compile 'fact)
FACT
NIL
NIL
CL-USER 121 > (compile 'fib)
FIB
NIL
NIL
CL-USER 122 > (time (fib 1000))
Timing the evaluation of (FIB 1000)
User time = 0.760
System time = 0.007
Elapsed time = 0.748
Allocation = 474522008 bytes
147 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
warmest
regards,
Ralph
--
Raffael Cavallaro
--
http://mail.python.org/mailman/listinfo/python-list
