12

I wanted to try and learn Lisp, but I very quickly gave up. I figured I'd try again. I'm looking at Problem 2 on Project Euler - finding the sum of all even Fibonacci numbers under 4 Million.

I wrote the following code which works, but is all kinds of ugly. Chief among them is the fact that it's so slow - because it's doing naive recursion all the time.

When I wrote this program in Python I built up a list as I calculated and never recalculated numbers. I know I could do that here (somehow) but that doesn't seem to be true to the spirit of lisp, of functional programming. I gave up after #3, when I hit a recursion depth limit and had to rewrite my code to use a loop instead of recursion.

So I suppose my questions are:

  1. What's the 'right, lispy way' to solve this problem?
  2. How do you reconcile recursion and the notion of 'just calculating everything' with the practical limit of calculating everything?
  3. Any recommendations for learning lisp besides The Little Schemer, and Project Euler?

And here's my code:

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))
3
  • 1
    Please, don't litter parentheses when writing lisp code. See the last paragraph at gigamonkeys.com/book/syntax-and-semantics.html, "Formatting Lisp Code", for a guide.
    – Svante
    Mar 10, 2009 at 1:12
  • 1
    I disagree, partly. "Lonely-parens" are bad style, but if your reason for using them is to help get used to programming in Lisp, more power to you. Just remember to work on your style eventually.
    – Aaron
    Mar 11, 2009 at 4:19
  • @Tom Ritter Why don't you use paredit mode. It rocks. Give a try :)
    – aatifh
    Mar 11, 2009 at 14:33

14 Answers 14

16

http://fare.tunes.org/files/fun/fibonacci.lisp has a walk through of solving fibonacci, gradually improving the time and memory performance of the implementation.

1
  • Thanks for linking this tutorial. One of the best about this topic
    – anquegi
    Aug 28, 2023 at 6:40
9

Memoization is a way to cache results to a function, to avoid re-calculating the intermediary results over and over. Memoization basically means the first time you call a function with some args, calculate the answer and return it, and cache that answer; for subsequent calls to a function with those same args, just return the cached value.

In Lisp you can easily use higher-order functions and a macro to transparently memoize a function. Clojure has memoize as an included standard function. Also look on page 65 of On Lisp for a Common Lisp implementation of memoize. Here it is in Clojure:

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user> 

This can still cause a stack overflow if you call it on a large integer. e.g. immediately doing (fib 10000) will blow the stack because it still has to recurse very deeply (once). But if you prime the cache first, it no longer has to recurse deeply and this can be avoided. Simply doing this first (in Clojure):

(dorun (map fib-memo (range 1 10000)))

will be enough to then let you do (fib 10000) without problems.

(The specific subject of calculating Fibonacci numbers came up recently on the Clojure mailing list. There's a solution there based on the Lucas numbers which I don't understand in the slightest, but which is supposedly 40 times faster than a naive algorithm.)

7

Use tail recursion instead of naive recursion. Most Lisp implementations should perform the tailcall-optimization; no more recursion depth limit.

Beyond that, try to think of things in terms of lists and abstract operations you could perform on those lists. Two of the more relevant operations to consider:

Regarding other Lisp resources:

UPDATE: Tail-recursive Scheme fib function:

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))
6
  • But tail call doesn't solve the O(2^n) problem. You still recalculate the same values over and over.
    – Steve Rowe
    Mar 9, 2009 at 18:29
  • The transformation to tail-recursion typically results in an iterative process, even if it technically uses recursion.
    – Hank Gay
    Mar 9, 2009 at 20:23
  • @Hank, I don't think it would in this case. It stops stack growth, but you still end up calculating fib(n) over and over.
    – Steve Rowe
    Mar 9, 2009 at 22:52
  • This is the tail-recursive implementation I've seen most often, and it works by keeping a running tally, so it isn't an exponential Big O.
    – Hank Gay
    Mar 10, 2009 at 0:23
  • why have a separate function? fib-tr can be a let expression: (let fib-tr ((a 1) (b 1) (cnt 10)) (display a) (newline) (if (> cnt 0) (fib-tr b (+ a b) (- cnt 1)) #f))
    – Aaron
    Mar 11, 2009 at 6:59
4
(let ((a 1) (b 1))
  (flet ((nextfib ()
           (prog1 a
             (psetf a b b (+ a b)))))
    (loop for fib = (nextfib)
          while (<= fib 4000000)
          when (evenp fib)
            sum fib)))

Above defines a function NEXTFIB which will generate the next fibonacci number for each call. The LOOP sums the even results upto the limit of 4000000.

PROG1 returns the value of the first of its subexpressions. PSETF sets a and b in 'parallel'.

That's a common pattern. There is a generator function and one calls it repeatedly, filters the results and combines them.

3

The way to solve this is to work bottom-up, generating each Fibonnaci term one-by-one, and adding it to the sum if it's even, and stopping once we reach the 4 million threshold. My LISP is rusty, so here it is in psuedocode:

one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
  if curr % 2 == 0
    sum = sum + curr
  two_prior = one_prior
  one_prior = curr
  curr = one_prior + two_prior
2

danio's answer will help greatly with the performance questions.

Here's a short critic of your style:

 (defun fib(i)
   (if (= i 1) ;//Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2)))
     )
   )
 )

Refactor nested IFs into a COND.

Don't put parentheses on a line by themselves.

 (defun solve(i)
   (let ((f (fib i))) ;//Store result in local variable
     (print f) ;//For debugging
     (if (

Using ZEROP is clearer.

         (+ f (solve (+ i 1))) ;//add number
         (solve (+ i 1)) ;//Don't

Why do you put those // in? A semicolon followed by a space is enough.

) ) ) ) (print (solve 1))

You last PRINT statement makes me a bit suspicious. Are you running this program from a file or from the REPL? If you do the former then you should consider doing the latter. If you do the latter you can just say (solve 1) to get the result.

1
  • I put the // solely for the markdown auto-formatting. It doesn't recognize languages and was highlighting keywords in the comments. But it does recognize // and treats everything after it as a comment.
    – Tom Ritter
    Mar 10, 2009 at 13:29
2

In addition to all useful answers, the following formulas may provide even more efficiency -- calculating Fn in O(Log(n)) instead of O(2^n). This has to be coupled with memoization, and is a solid base for solving the problem:

F(2*n) = F(n)^2 + F(n-1)^2

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)
1
1

To expand on Danio's answer, the article at http://fare.tunes.org/files/fun/fibonacci.lisp presents two ways of making the code run faster. Using straight recursion (tail call or no) is O(2^n) and very slow. The difficulty is that each value gets calculated over and over again. You have to do things differently. The two recommendations are:

  1. Use an iterative approach.
(defun bubble-fib (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (check-type n fixnum)
  (loop repeat n
  with p = 0 with q = 1
  do (psetq p q
        q (+ p q))
  finally (return p)))
  1. Use Memoization. This means remembering the values see before and recalling them rather than recalculating them. The article provides a CL package that will do this as well as some code to do it yourself.
1

My understanding of "the spirit of lisp" is to detach yourself from any fixed, dogmatic, stuckup idea of the spirit of lisp, and use the lisp construct that most closely reflects the structure of computation required to solve your problem. For example,

(defun euler2 (&optional (n 4000000))
  (do ((i 1 j)
       (j 2 (+ i j))
       (k 0))
      ((<= n i) k)
    (when (evenp i) (incf k i))))

If you insist on recursion, here is another way:

(defun euler2 (&optional (n 4000000))
  (labels ((fn (i j k) 
             (if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
    (fn 1 2 0)))
1

Simple, efficient way of creating a list of fibonacci numbers:

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

(shiftf) takes any number of places and finally a value. Each place is set to the value of the next variable, with the last variable taking the value that comes after it. It returns the value of the first place. In other words, it shifts all the values left by one.

However, you don't need the full list (you only need the evens) and you don't need the list at all (you only need the sum), so this can be worked into the function directly. Every third fibonacci number is even, so...

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))
0
0

See both the videos and text located at: http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

0
(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))
4
  • 1
    Unfortunately generally that's not a good idea, since recursive functions like this may create a stack overflow (depends on max stack size and recursion depth). Scheme one would rewrite it to a tail recursive style. In Common Lisp actually we need to use iterative constructs. Mar 11, 2009 at 15:32
  • 1
    (append (list 1) (foo ...)) = (cons 1 (foo ...)) Mar 11, 2009 at 15:33
  • Both 'solutions' are wrong. You did not read the question correctly.
    – leppie
    Mar 12, 2009 at 8:01
  • 1
    @leppie why don't you try to answer the question instead of becoming useless commentator and voting other's down. Be a bit ethical and answer the question dude.
    – aatifh
    Mar 12, 2009 at 8:08
0

Here is a memoised version. In this case, since you have to compute each fibonacci number until you find one more than four million, using closed form solutions would no do much good.

This approach creates a lexical environment via let; create a dictionary fib-table and a function fib-memoed in that environment. The end product of this is fib-table is accesible from fib-memoed but no where else.

Now the kicker: since we have to compute fib for sequential values until some condition is met, we start the solver at fib 1. From here on, computing the next fib number entails at most 2 dictionary lookups and one addition: O(1) BOOM!

;; memoised fib function: make a hash table, then create                                      
;; the fib function in the lexical scope of the hash table                                    
(let ((fib-table (make-hash-table)))
  (setf (gethash 0 fib-table) 1)
  (setf (gethash 1 fib-table) 1)
  (defun fib-memoed (n)
    (let ((x (gethash n fib-table)))
      (cond ((not (null x))
             x)
            (t
             (let ((y (+ (fib-memoed (- n 1))
                         (fib-memoed (- n 2)))))
               (setf (gethash n fib-table) y)
               y))))))

(defun solve ()
  (let ((maxval 4000000))
    (labels ((aux (i acc)
               (let ((x (fib-memoed i)))
                 (cond ((> x maxval) acc)
                       ((evenp x)
                        (aux (1+ i) (+ x acc)))
                       (t (aux (1+ i) acc))))))
      (aux 1 0))))
-1

;;; I try to write code as suggestion of @PESTO

(defun Fibo-Test (n / one_prior two_prior curr sum i)

(setq i 2) (setq one_prior 1 two_prior 1 )

(cond

((= n 0) (setq sum 0) )

((= n 1) (setq sum 1) )

((= n 2) (setq sum 1) )

(T

(while (and (< i n) (< sum (* 4 1e6)))

;;; convert to Real-num

(setq sum (+ (float one_prior) (float two_prior)))

(setq i (1+ i))

(setq curr sum) (setq
one_prior two_prior two_prior curr
)

) ; end while

) ; end cond(T)

) ; end cond

(princ (strcat "\nF(" (itoa i) ") = " (RTOS sum) " . "))

(princ)

) ; end function Fibo-Test

1
  • 2
    Is this an answer or do you have some issue and it's a question?
    – barbsan
    Feb 27, 2019 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.