Irreal

Atabey Kaygun is a mathematician who likes to experiment with various (mostly mathematical) algorithms using Common Lisp. Many times, a function is most naturally implemented via recursion but this can lead to disastrously inefficient implementations. The canonical example is the Fibonacci sequence. Its definition is \[\begin{equation*} fib(n) = \begin{cases} 0 & x = 0\\ 1 & x = 1\\ fib(n-1) + fib(n-2) & x > 1\\ \end{cases} \end{equation*}\] so a natural implementation is

(defun fib (n)
  (cond
    ((zerop n) 0)
    ((= n 1) 1)
    (t (+ (fib (1- n)) (fib (- n 2))))))

But when we run

(time (fib 45))

we get

: 1134903170

Evaluation took:
  60.287 seconds of real time
  60.217115 seconds of total run time (60.163250 user, 0.053865 system)
  99.88% CPU
  132,297,562,672 processor cycles
  0 bytes consed

What’s going on here is that the same values are computed over and over. I wrote about this and various other, more efficient implementations here and gave some timings (although for Scheme not Common Lisp) here. The times for the other implementations are too small to measure with a 100 Hz clock. As explained in the first post, calculating \(fib(45)\) recursively makes 3,672,623,805 calls to \(fib\).

For this reason, the recursive implementation is never used and serves mostly as a warning to n00bs about the dangers of blindly using recursion. Still, the recursive implementation is natural and in many other situations the only reasonable solution. That’s where Atabey comes to our aid. He provides a Common Lisp macro, mem-defun, that implements memoization, a technique where previously calculated function values are cached so that subsequent calls to the function for the same argument are retrieved from the cache rather than being recalculated.

The mem-defun macro is a drop-in replacement for defun. Head over to his post for the definition. When we use his macro

(mem-defun fib (n)
  (cond
    ((zerop n) 0)
    ((= n 1) 1)
    (t (+ (fib (1- n)) (fib (- n 2))))))

and rerun the test

(time(fib 45))

we get

: 1134903170

Evaluation took:
  0.000 seconds of real time
  0.000018 seconds of total run time (0.000018 user, 0.000000 system)
  100.00% CPU
  37,477 processor cycles
  0 bytes consed

a clear win. It’s probably not as fast as one of the alternative implementations but when you need to use recursion, it can be a lifesaver.