```
Subject:
```**Re: iterative-version for computing a Fibonacci number**

From: rpw3@rpw3.org (Rob Warnock)

Date: Fri, 28 Jul 2006 01:10:40 -0500

Newsgroups: comp.lang.lisp

Message-ID: <99adnZWsxPH9N1TZnZ2dnUVZ_oCdnZ2d@speakeasy.net>

thebjorn <BjornSteinarFjeldPettersen@gmail.com> wrote: +--------------- | Hi, perhaps someone can help me translate my Python version? I'm slowly | learning Lisp, but I'm out of my league on translating something like | this still :-( | | def fib(n): # generate the first n numbers in the fibonacci sequence | a,b = 0,1 # pairwise assignment a <- 0, b <-1 | for i in xrange(n-1): # i gets [0,n-1) | yield b # save state, yield b to calling context | a,b = b,a+b # return to here from calling context | return | | # sum all numbers, n, coming from the fib generator if they're even | x = sum(n for n in fib(200000) if n%2==0) | | it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is | 20899 for 100K and 41797 for 200K). +--------------- Someone else showed you one possible translation to Lisp, but I suspect that the following one is closer to the spirit of what your Python code seems to be actually doing, that is, creating a "generator". Since Common Lisp doesn't have user-visible continuations per se, the usual idiom in CL is to make a "function maker" which returns a closure which encapsulates the "continuation state", which you can later call to produce each successive element. Unlike your "fib(n)" above, the following version does not put an arbitrary upper limit on the number of elements returned; you control that externally in the caller. My results with CMUCL (in 32-bit mode) on a 1.8 GHz Athlon64 were 3.18 s & 12.92 s, respectively [I included the "system time" since CMUCL uses page-fault traps for GC], and gave the same number of digits (20899 & 41797, resp.) for the results as yours: > (defun make-fibber () (let ((a 0) (b 1)) (lambda () (prog1 b (psetf a b b (+ a b)))))) MAKE-FIBBER > (compile *) ; Compiling LAMBDA NIL: ; Compiling Top-Level Form: MAKE-FIBBER NIL NIL > (loop with fib = (make-fibber) ; quick test for i below 10 collect (funcall fib)) (1 1 2 3 5 8 13 21 34 55) > (defun sum-even-fibs (how-many) (let ((x (loop with fib = (make-fibber) for i below how-many and n = (funcall fib) when (evenp n) sum n))) (ceiling (log x 10)))) SUM-EVEN-FIBS > (compile *) ; Compiling LAMBDA (HOW-MANY): ; Compiling Top-Level Form: SUM-EVEN-FIBS NIL NIL > (time (sum-even-fibs 100000)) ; Compiling LAMBDA NIL: ; Compiling Top-Level Form: ; Evaluation took: ; 3.18f0 seconds of real time ; 2.5f0 seconds of user run time ; 0.67f0 seconds of system run time ; 5,724,123,132 CPU cycles ; [Run times include 0.95f0 seconds GC run time] ; 0 page faults and ; 581,748,776 bytes consed. ; 20899 -0.6777344f0 > (time (sum-even-fibs 200000)) ; Compiling LAMBDA NIL: ; Compiling Top-Level Form: ; Evaluation took: ; 12.92f0 seconds of real time ; 10.33f0 seconds of user run time ; 2.59f0 seconds of system run time ; 23,287,767,118 CPU cycles ; [Run times include 4.07f0 seconds GC run time] ; 0 page faults and ; 2,320,568,856 bytes consed. ; 41797 -0.12109375f0 > Also unlike yours [I think, as I'm not too sure about Python's "yield" operator], the above version allows you to create multiple independent "fib generators", and step them independently: > (let ((fib-vec (coerce (loop for i below 3 collect (make-fibber)) 'vector))) (loop for i below 25 do (let* ((index (random (length fib-vec))) (fib (funcall (aref fib-vec index)))) (format t "Fibber #~d returned ~d~%" index fib)))) Fibber #2 returned 1 Fibber #1 returned 1 Fibber #1 returned 1 Fibber #2 returned 1 Fibber #0 returned 1 Fibber #2 returned 2 Fibber #0 returned 1 Fibber #2 returned 3 Fibber #2 returned 5 Fibber #1 returned 2 Fibber #1 returned 3 Fibber #2 returned 8 Fibber #1 returned 5 Fibber #0 returned 2 Fibber #0 returned 3 Fibber #2 returned 13 Fibber #0 returned 5 Fibber #0 returned 8 Fibber #2 returned 21 Fibber #1 returned 8 Fibber #0 returned 13 Fibber #0 returned 21 Fibber #0 returned 34 Fibber #2 returned 34 Fibber #1 returned 13 NIL > -Rob ----- Rob Warnock <rpw3@rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607