Как написать быстрое возведение в степень?

Question

[Filipp42]

Пытаюсь написать хвостовой рекурсей быстрое возведение в степень:

(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))))

Не работает. Что я делаю не так?
Пишу эту функцию, потому что не уверен, что встроенная работает по быстрому алгоритму. Мне необходима функция для целых степеней, которая бы быстро возводила числа в степень по модулю. Есть ли в языке такая функция?

Comments

[Денис Загаевский]

Как именно не работает? Напиши тесты.
(1- p) это что? Должно быть (- p 1)

[Filipp42]

Денис Загаевский, Это функция инкремента в Лиспе.

Answer 1

[jcmvbkbc]

Не работает.

(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)))

так работает.

Что я делаю не так?

Не учитываешь, что при погружении в рекурсию n тоже может расти. Или неправильно интерпретируешь параметры fastexpt-iter. В моей интерпретации fastexpt-iter(n, p, a) = n ^ p * a.