Re: iterative-version for computing a Fibonacci number

"arnuld" <arnuld3@xxxxxxxxx> writes:

hai guys,

i came across "Project Euler" while i was searching for some problems
to work on. i find a problem related to Fibonacci numbers.

Statement:-- Find the sum of all the even terms in the Fibonacci
sequence below one million.

OK, i solved it by writing these functions & it works correctly:

(defun fibo-million (bound)
(do ((n 0 (+ n 1))
(sum 0))
((> n bound) sum)
(if (evenp (fibo n))
(setq sum (+ sum (fibo n))))))


;; helper-function for fibo-million
;; computes the fibonacci number for the given number
(defun fibo (n)
(cond ((= n 0) 0)
((= n 1) 1)
(t (+ (fibo (- n 1))
(fibo (- n 2))))))


Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
minutes waiting at REPL but REPL was still calculating.....

WHY? because the helper-function named "fibo" was taking too long to
compute fib 100.

Because you're computing an exponential number of times (fibo n) for
all n<100.

A quick and dirty solution to speed up your program is to memoize the
function fibo. It'll use O(n) space.


then i thought of writing an iterative version of it but failed to
think of anything. i tried to write using DO but was not able to come
up even with 2 lines of code.
do you have any idea for computing a fibonacci number using an
iterative method?

Just start from 0 instead of n.

(defun fibo-i (n)
(labels ((fibo-i-1 (i f-1 f-2)
(if (= i n)
(+ f-1 f-2)
(fibo-i-1 (1+ i) (+ f-1 f-2) f-1))))
(fibo-i-1 0 1 -1)))


( i once saw both styles for computing a factorial, recursive version
took long time but ate less memory whereas iterative version was quick
and ate lots of memory)

For factionnal, the recursive one takes more memory than the iterative one:

(defun fact-r (n)
(if (= 1 n)
1 ; last factor, we still need to multiply.
(* n ; stacks up n
(fact-r (1- n))))) ; no tail call, we still need to multiply.

(defun fact-i (n)
(labels ((fact-i-1 (i f)
(if (= i n)
(* i f) ; last multiplication, we can exit.
(fact-i-1 (1+ i) (* i f))))) ; tail call, no stack used.
(fact-i-1 1 1)))

--
__Pascal Bourguignon__ http://www.informatimago.com/

Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
.

Relevant Pages