apr 10

(defmacro w-gensyms (names &body body)
  `(let ,(loop for i in names collect `(,i (gensym)))
     ,@body))

(defmacro defun-memoized (func args &body body)
  (w-gensyms (hash i j)
    `(let ((,hash (make-hash-table :test 'equalp)))
       (defun ,func ,args
         (multiple-value-bind (,i ,j)
            (gethash (list ,@args) ,hash)
            (if ,j ,i
              (setf (gethash (list ,@args) ,hash) ,@body)))))))

(defun-memoized a_n (n)
    (cond ((= n 1) 3)
          ((= n 2) 3)
          (t (/ (+ (expt (a_n (1- n)) 2) 2007)
                (a_n (- n 2))))))

(compile 'a_n)

(format t "~d~%"
  (/ (+ (expt (a_n 2007) 2) (expt (a_n 2006) 2))
     (* (a_n 2007) (a_n 2006))))