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

Homecoming

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. – Caesura

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. – Diffusivity

@Tom Ritter Why don't you use paredit mode. It rocks. Give a try :) – Wellpreserved

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.

Mureil

Thanks for linking this tutorial. One of the best about this topic – Stubblefield

Answer 2

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

Patently

Answer 3

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:

• filter
• fold

Regarding other Lisp resources:

• Common Lisp—On Lisp
• Scheme—Structure and Interpretation of Computer Programs

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

Lachance

But tail call doesn't solve the O(2^n) problem. You still recalculate the same values over and over. – Nevels

The transformation to tail-recursion typically results in an iterative process, even if it technically uses recursion. – Lachance

@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. – Nevels

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. – Lachance

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

Because my Scheme is limited to the first few sections of SICP, so I haven't gotten to let yet. – Lachance

@SteveRowe It does not recalculate fib(n) over and over. It just adds the last two numbers consecutively until n reaches 0. – Stephanstephana

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

Anglophobia

Answer 5

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

Conspire

Answer 6

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.

Snort

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. – Homecoming

Answer 7

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)

Jemmie

implemented – Mcalister

Answer 8

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

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

Nevels

Answer 9

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

Gussiegussman

Answer 10

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

Paulettepauley

Answer 11

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

Swagsman

Answer 12

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

Wellpreserved

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. – Anglophobia

(append (list 1) (foo ...)) = (cons 1 (foo ...)) – Anglophobia

Both 'solutions' are wrong. You did not read the question correctly. – Berzelius

@Berzelius 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. – Wellpreserved

Answer 13

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

Invasive

Answer 14

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

Pokelogan

Is this an answer or do you have some issue and it's a question? – Foregone