Q:

Definition of power functions

I needed to write a simple function that could raise a value x to the n'th power. I found out I could write this function in 2 different ways:
(defun power1 (x n)
  "Raise x to the n'th power"
  (cond ((zerop n)
          1.0)
         ((< n 0.0)
          (/ 1.0 (reduce #'* (loop for i below (- n) collect x))))
         (t
          (reduce #'* (loop for i below n collect x)))))

(defun power2 (x n)
  "Raise x to the n'th power"
  (cond ((zerop n)
         1.0)
        ((< n 0.0)
         (/ 1.0 (power2 x (- n))))
        (t
         (* x (power2 x (- n 1))))))

Now, I was curious to known which of these 2 functions is better. So I ran some calls to these functions wrapped in a call to the time function. Here are some results:

(time (power1 2 100))
took 0 milliseconds (0.000 seconds) to run.
2,248 bytes of memory allocated.

(time (power2 2 100))
took 0 milliseconds (0.000 seconds) to run.
800 bytes of memory allocated.

(time (power1 2 1000))
took 0 milliseconds (0.000 seconds) to run.
82,232 bytes of memory allocated.

(time (power2 2 1000))
> Error: FLOATING-POINT-OVERFLOW detected

The first function takes more memory, since it creates an entire list, while the second function uses recursion. But the first one can handle larger numbers.
How can I choose which of these functions is the best? Choose for memory usage, readability, Lisp-like style, range of inputs it can handle, .... Maybe a function that uses tail-call optimization would be even better?
(defun power3 (x n)
  (labels ((pow (x n acc)
             (if (zerop n)
                 acc
                 (pow x (- n 1) (* acc x)))))
    (cond ((zerop n) 1.0)
          ((< n 0.0) (/ 1.0 (pow x (- n) 1.0)))
          (t (pow x n 1.0)))))

(time (power3 2 100))
took 1 milliseconds (0.001 seconds) to run.
800 bytes of memory allocated.

A:

Major
All 3 of your functions are linear (they do O(n) multiplications) while, in fact, only O(log(n)) is necessary:
(defun pow (x n)
  (if (minusp n)
      (/ (pow x (- n)))
      (multiple-value-bind (d r) (floor n 2)
        (let ((p (if (zerop d) 1 (pow x d))))
          (* p p (if (zerop r) 1 x))))))

In addition to much fewer multiplications, I am returning ratios for rational x.
Minor
Use minusp instead of comparison with 0.0 and (/ a) instead of (/ 1 a).

