The lisp-way to solve Fibonnaci

Question

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 the even Fibbonacci 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))

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.)

Answer 5

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.

Answer 6

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)))

Answer 7

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.

Answer 8

(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.

Answer 9

(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)))

Answer 10

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)