Can this function be simplified (made more “fast”)

Question

I was wondering if this is the fastest possible version of this function.

(defun foo (x y)
  (cond 
   ;if x = 0, return y+1
   ((zp x) (+ 1 y)) 
   ;if y = 0, return foo on decrement x and 1
   ((zp y) (foo (- x 1) 1)) 
   ;else run foo on decrement x and y = (foo x (- y 1))
   (t (foo (- x 1) (foo x (- y 1)))))) 

When I run this, I usually get stack overflow error, so I am trying to figure out a way to compute something like (foo 3 1000000) without using the computer.

From analyzing the function I think it is embedded foo in the recursive case that causes the overflow in (foo 3 1000000). But since you are decrementing y would the number of steps just equal y?

edit: removed lie from comments

Answer 1

Conceptually speaking, stack overflows don't have anything to do with speed, but they concern space usage. For instance, consider the following implementations of length. The first will run into a stack overflow for long lists. The second will too, unless your Lisp implements tail call optimization. The third will not. All have the same time complexity (speed), though; they're linear in the length of the list.

(defun length1 (list)
  (if (endp list)
      0
      (+ 1 (length1 (rest list)))))

(defun length2 (list)
  (labels ((l2 (list len)
             (if (endp list)
                 len
                 (l2 (rest list) (1+ len)))))
    (l2 list 0)))

(defun length3 (list)
  (do ((list list (rest list))
       (len 0 (1+ len)))
      ((endp list) len)))

You can do something similar for your code, though you'll still have one recursive call that will contribute to stack space. Since this does appear to be the Ackermann function, I'm going to use zerop instead of zp and ack instead of foo. Thus, you could do:

(defun foo2 (x y)
  (do () ((zp x) (+ 1 y))
    (if (zp y)
        (setf x (1- x)
              y 1)
        (psetf x (1- x)
               y (foo x (1- y))))))

Since x is decreasing by 1 on each iteration, and the only conditional change is on y, you could simplify this as:

(defun ack2 (x y)
  (do () ((zerop x) (1+ y))
    (if (zerop y)
        (setf x (1- x)
              y 1)
        (psetf x (1- x)
               y (ack2 x (1- y))))))

Since y is the only thing that conditionally changes during iterations, you could further simplify this to:

(defun ack3 (x y)
  (do ((x x (1- x))
       (y y (if (zerop y) 1 (ack3 x (1- y)))))
      ((zerop x) (1+ y))))

This is an expensive function to compute, and this will get you a little bit farther, but you're still not going to get, e.g., to (ackN 3 1000000). All these definitions are available for easy copying and pasting from http://pastebin.com/mNA9TNTm.

Answer 2

Generally, memoization is your friend in this type of computation. Might not apply as it depends on the specific arguments in the recursion; but it is a useful approach to explore.

Answer 3

12 years ago I wrote this:

(defun ackermann (m n)
  (declare (fixnum m n) (optimize (speed 3) (safety 0)))
  (let ((memo (make-hash-table :test #'equal))
        (ncal 0) (nhit 0))
    (labels ((ack (aa bb)
               (incf ncal)
               (cond ((zerop aa) (1+ bb))
                     ((= 1 aa) (+ 2 bb))
                     ((= 2 aa) (+ 3 (* 2 bb)))
                     ((= 3 aa) (- (ash 1 (+ 3 bb)) 3))
                     ((let* ((key (cons aa bb))
                             (val (gethash key memo)))
                        (cond (val (incf nhit) val)
                              (t (setq val (if (zerop bb)
                                               (ack (1- aa) 1)
                                               (ack (1- aa) (ack aa (1- bb)))))
                                 (setf (gethash key memo) val)
                                 val)))))))
      (let ((ret (ack m n)))
        (format t "A(~d,~d)=~:d (~:d calls, ~:d cache hits)~%"
                m n ret ncal nhit)
        (values ret memo)))))

As you can see, I am using an explicit formula for small a and memoization for larger a.

Note, however, that this function grows so fast that it makes little sense to try to compute the actual values; you will run out of atoms in the universe faster - memoization or not.