The Fibonacci Function

(This is the first of a series of articles on advanced programming techniques.)

There are two contrasting ways of writing the Fibonacci function: recursive and iterative. Recursive looks like this:

(defun fibo (n)
  "Recursive fibonacci function."
  (if (< n 2)
      1
    (+ (fibo (- n 1))
       (fibo (- n 2)))))

and iterative looks like this

(defun fibo2 (n)
  "Iterative Fibonacci function"
  (do ((i n (- i 1))
       (old 1)
       (new)
       (result 1))
      ((< i 2) result)
      (setf new (+ result old))
      (setf old result)
      (setf result new)))

You should at this point spot that the recursive version is better. If you preferred the iterative version, you ought to read on and learn why.

Programs are supposed to be read by people as well as run on computers and to help this should be as declarative as possible. Optimizations should be abstracted away.

Compare these

(defun mystery (abc)
  "What does this do?"
  (if (< abc 2)
      1
    (+ (mystery (- abc 1))
       (mystery (- abc 2)))))

(defun enigma (abc)
  "Now try to figure out what this does!"
  (do ((def abc (- def 1))
       (ghi 1)
       (jkl)
       (mno 1))
      ((< def 2) mno)
      (setf jkl (+ mno ghi))
      (setf ghi mno)
      (setf mno jkl)))

It is immediately clear, just by looking at it, that mystery generates Fibonacci numbers, but enigma is almost completely opaque. A computer will still run it, but a person will only understand it with difficulty. Yet they are exactly the same functions as fibo and fibo2 .

You may still be objecting that the recursive version is going to be much slower because it's repeatedly being called with the same argument during the recursive calls, and a quick benchmark confirms this:

eval> (time (fibo 20))
9.023471s
10946

eval> (time (fibo2 20))
0.002941s
10946

Several thousand times slower.

I will now prove that the recursive version can be made faster than the iterative version, using a technique called memoization. (Common Lispers, please note that this is Emblem, so there are slight divergencies from Common Lisp.)

(setf FIBO_HASH (makeHashTable 100)) ;100 hash buckets.

(defun fibo3 (n)
  "Fibonacci function with DIY memoization."
  (if (eq (getHash n FIBO_HASH)
           _) ;Undefined?
      (setf (getHash n FIBO_HASH)
            (if (< n 2)
                1
              (+ (fibo3 (- n 1))
                 (fibo3 (- n 2)))))
    (getHash n FIBO_HASH)))

What I'm now doing is storing newly computed values in a hash table, and retrieving already computed values from the hash table, thereby avoiding their recomputation. However, this destroys the elegance of the original recursive definition. (getHash is a very popular Lisp function in Amsterdam cafes...)

Macros to the rescue!

fibo3 can be translated into more conventional languages such as C and Java. However, virtually unique to Lisp is the ability to redefine the very mechanism by which functions are defined. This can be used to restore the elegance which was lost when the hashing mechanism was added:

(defmacro defmemo (fun args . body)
  "Memoize macro.   Only works for functions of one argument."
  (let ((doc '())
        (ret '())
        (argName (car (_argNames args)))) ;Retrieve the arg name.
    ;; Handle the documentation string, if present.
    (when (eq (typeOf (car body)) 'Str)
      (setf doc (list (pop body))))
    ;; Handle the return type declaration, if present.
    (when (and (eq (typeOf (car body)) 'List)
               (eq (caar body) 'returns))
      (setf ret (list (pop body))))
    ;; Put hash table on the function name's property list.
    `(progn (setf (get ',fun 'hash) (makeHashTable 100))
            ;; Generate the memoizing function definition.
            (defun ,fun ,args
              ,@doc
              ,@ret
              (let ((hash (get ',fun 'hash)))
                (if (eq (getHash ,argName hash) _)
                    (setf (getHash ,argName hash)
                          ,@body) ;Save the function's value in the hash table.
                  (getHash ,argName hash))))))) ;Retrieve precomputed value.

and with this, we can now define

(defmemo fibo4 (n)
  "Memoized Fibonacci function definition."
  (if (< n 2)
      1
    (+ (fibo4 (- n 1))
       (fibo4 (- n 2)))))

Looks pretty much like the original definition. The first time it runs, it's slower than the iterative version, but repeated calls are much faster, because it's just doing hash table lookup:

eval> (time (fibo4 20))
0.030606s
10946                                                                           
eval> (time (fibo4 20))
0.000385s
10946

The same mechanism can be used for other functions, such as factorial:

(defmemo fac (n)
  "Memoized factorial function definition."
  (if (< n 2)
      1
    (* n (fac (- n 1)))))

This page was linked to from

index
Emblem

and was last updated on Jul 26 at 03:42.