Documentation typo in CodePatterns

Q&A's, tips, howto's

Documentation typo in CodePatterns

Postby jef » Fri Sep 18, 2015 2:03 pm

Hi,

I realized that the code for the fibonacci functions in the codepatterns
section is wrong: http://www.newlisp.org/CodePatterns.html#toc-5

The code is:

Code: Select all
; classic recursion
; slow and resource hungry
(define (fib n)
    (if (< n 2) 1
        (+  (fib (- n 1))
            (fib (- n 2)))))

> (fib 12)
233


Should be:

Code: Select all
; classic recursion
; slow and resource hungry
(define (fib n)
    (if (< n 2) n
        (+  (fib (- n 1))
            (fib (- n 2)))))

> (fib 12)
144


The iterative version should be fixed also, something like
that should be correct:

Code: Select all
; iteration
; fast and also returns the whole list
(define (fibo n , f)
  (set 'f '(1 0))
  (case n
    (0 (1 f))
    (1 f)
    (true
      (dotimes (i (- n 1))
        (push (+ (f 0) (f 1)) f)))))

> (fibo 12)
(144 89 55 34 21 13 8 5 3 2 1 1 0)
jef
 
Posts: 11
Joined: Sun May 18, 2014 8:42 am

Re: Documentation typo in CodePatterns

Postby Lutz » Sat Sep 19, 2015 1:43 pm

It depends what you define as the Fibonacci sequence:

The expression (if (< n 2) 1 sees n as index into the sequence 1,1,2,3,5,8 …
The expression (if (< n 2) n sees n as index into the sequence 0,1,1,2,3,5,8 …

The original Fibonacci sequence does not contain a result for (fibo 0) (see the “rabbit” example), and one could argue, that the result for (fibo 0) should not be included but is undefined.

The first form is also faster for the same result:
Code: Select all
> (time (println (fib1 29)))
832040
459.522
> (time (println (fibn 30)))
832040
738.925
>
Lutz
 
Posts: 5279
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California


Return to newLISP in the real world

Who is online

Users browsing this forum: No registered users and 2 guests