Re: Computing fibonacci numbers (rank newbie)

Hi John

John Thingstad wrote:

On Tue, 22 May 2007 19:11:12 +0200, Jeff Rollin
<jeffrey.rollin@xxxxxxxxxxxxxx> wrote:



Well there is a lot wrong here.
A Fibonacci sequence is:

fib(n) = fib(n-1) + fib(n-2)

n 0 1 2 3 4 5 6
fib 1 1 2 3 5 8 13

For one thing you have to start at the beginning.
The loop is nonsense.
This is a useful first approximation:

(defun fib (n &optional (cur 1) (n-2 1) (n-1 1))
(cond
((< n 2) 1)
((= cur n) n-1)
(t (fib n (1+ cur) n-1 (+ n-2 n-1)))))

As you see it remembers 3 values.

So the (defun...) line initializes cur, n-2, and n-1, allowing you to
specify them if you wish?

cur is the current counter
n-2 is the value from the iteration two calls ago
n-1 is the value from 1 call ago
since we only start at 2 these are defaulted to 1 so fib(2)=1+1=2
The second condition exits with the accumulated value which is stored in
n-1
The default branch uses a recursive call to fib. it:
1. increments cur
2. stores n-1 in the n-2 position

Not sure I understand why you write "n-1" and not "(n-1)" here.

3. calculates current fib value and stores it in n-1 position

The good news is that this function is tail-recursive so the compiler
can optimize the call away and make a loop for you.
(The ANSI standard does not guaranteed this but most compilers do this if
optimisation debug < speed or debug < 3 which is usually default)

The bad news is that this is terribly inefficient for computing all values
up to 10000.

That's fair enough. I'm just trying to get a handle on the process here.
Optimization can come later. You can probably tell this code isn't going
anywhere near a production app any time soon ;-).

It is much better to remember the result of the last computations.

(defun fibseq (n &optional (cur 1) (seq (list 1 1)))
(cond
((< n 1) 1)
((< n 2) (list 1 1))
((= cur n) (nreverse seq))
(t (fibseq n (1+ cur) (push (+ (second seq) (first seq)) seq)))))

CL-USER 5 > (fibseq 6)
(1 1 2 3 5 8 13)

Kinda like the last one but this one returns a list of the Fibonacci
numbers.
Since you use push you get the numbers pushed on the list in the reverse
order.
Therefore before we exit we in-place reverse the list.
Also we can now read the two last values from the seq list.

Be aware that this list gets very big for 10000.


See above, re: optimization.

Thankyou very much, very helpful.

Jeff.

.

Relevant Pages

  • Re: Damn you, FEDEX! or Nikon D40 lost in Springfield, MO blackhole.
    ... the 2 mp Mavica he had been using with a Nikon D40. ... After shopping around, he got me to order one for him. ... The shipper had it insured, but from what I have read it could take weeks to sort this crap out. ... You may get your insurance from FedEx and a couple weeks later they find it and deliver it. ...
    (alt.photography)
  • Re: um.....this is...!
    ... > replacing n with n-1, ... > substrctinge that last equations, ... > The Fibonacci sequence is ...
    (sci.math)
  • Re: um.....this is...!
    ... replacing n with n-1, ... substrctinge that last equations, ... The Fibonacci sequence is ... Then band averify the same requrrence relation with the same initial ...
    (sci.math)
  • Re: The Sci-Fi Rejection Letter That Time Forgot
    ... nations have stockpiled arsenals of these incredible bombs and the time the story is set. ...
    (rec.arts.sf.written)
  • RE: copied music cds have a skip in last 18 seconds
    ... If installing all missing Windows Updates doesn't fix your problem ... xiowan.......in tucson ...
    (microsoft.public.windows.mediacenter)