How to write fast exponentiation?

Question

Lisp

I'm trying to write tail recursion fast exponentiation:

(defun fastexpt-iter (n p count)
  (format t "n: ~A p: ~A count: ~A ~%" n p count)
  (if (= 1 p)
      count
      (if (evenp p)
    (fastexpt-iter n (/ p 2) (* count count))
    (fastexpt-iter n (1-  p) (* n count)))))

(defun fastexpt (n p)
  (if (zerop p)
      1
      (if (evenp p)
    (fastexpt-iter n p n)
    (fastexpt-iter n p 1))))

Does not work. What am I doing wrong?
I am writing this function because I am not sure that the built-in one works according to a fast algorithm. I need a function for integer powers that would quickly raise numbers to a power modulo. Does the language have such a function?

Answer 1

Does not work.

(defun fastexpt-iter (n p a)
  (format t "n: ~A p: ~A a: ~A~%" n p a)
  (if (= 1 p)
    (* n a)
    (if (evenp p)
      (fastexpt-iter (* n n) (/ p 2) a)
      (fastexpt-iter n (1-  p) (* a n)))))

(defun fastexpt (n p)
  (if (zerop p)
    1
    (fastexpt-iter n p 1)))

that's how it works.

What am I doing wrong?

You do not take into account that when immersed in the recursion, n can also grow. Or you are misinterpreting the fastexpt-iter parameters. In my interpretation fastexpt-iter(n, p, a) = n ^ p * a.