http://t3x.org/lisp64k/expt.html

LISPy things you can do in 64K bytes of core

Exponent Function

This function computes xy in the obvious way, i.e. by multiplying the number 1 y times by x. (context) It should be used for small exponents (y<20).

(setq expt
  (lambda (x y)
    (cond ((zerop y) #1) 
          (else (times x (expt x (diff y #1)))))))

For larger exponents, the following algorithm is more efficient:

x0 = 1
x2y = (xy)2
xy = x(x(y-1)/2)2
(setq expt
  (lambda (x y)
    (labels
      ((square (lambda (x) (times x x)))
       (expt1
         (lambda (y)
           (cond ((zerop y) #1)
                 ((zerop (rem y #2))
                   (square (expt1 (div y #2))))
                 (else
                   (times x (square (expt1 (div y #2)))))))))
      (expt1 y))))

contact  |  privacy