The lisp-way to solve Fibonnaci

问题:

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

回答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.

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

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

回答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.

回答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

回答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.

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

回答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.

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

回答10:

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

回答11:

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

回答12:

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

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

回答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