Что случилось с моей итеративной реализацией expmod?

Question

Следующая программа предназначена для расчета base^expo mod m.

(define (expmod base expo m) 
    (define (square n) 
    (* n n)) 
    (define (even? n) 
    (= (remainder n 2) 0)) 
    (define (expmod-iter base expo m result) 
    (cond ((= expo 0) result) 
      ((even? expo) 
      (expmod-iter base 
         (/ expo 2) 
         m 
         (remainder (square result) m))) 
      (else 
      (expmod-iter base 
         (- expo 1) 
         m 
         (remainder (* base result) m))))) 
    (expmod-iter base expo m 1)) 

На самом деле, я пытаюсь преобразовать a tail-recursive program from SICP его итерационного эквивалент. Вот оригинальная программа:

(define (expmod base exp m) 
    (cond ((= exp 0) 1) 
     ((even? exp) 
     (remainder (square (expmod base (/ exp 2) m)) 
        m)) 
     (else 
     (remainder (* base (expmod base (- exp 1) m)) 
        m)))) 

Результат (expmod 42 1000000007 1000000007) является 270001056, но, по словам Fermat's Little Theorem, так как 1000000007 первична, результат должен быть 42.

Что я делаю неправильно?

Answer 1

Это моя реализация итерационного expmod:

(define (expmod base exp mod) 
    (let loop ((base base) 
      (exp exp) 
      (result 1)) 
    (cond ((zero? exp) result) 
      ((odd? exp) (loop base (sub1 exp) (modulo (* result base) mod))) 
      (else (loop (modulo (sqr base) mod) (quotient exp 2) result))))) 

Испытано в Ракетка с входом образца. Вам нужно будет заменить sub1 и sqr с подходящими реализациями, если вы не используете Racket.

Обратите внимание, что, хотя вам нужно сделать квадрат базы для четного экспонента, вы можете на самом деле изменить результат этого, как вы можете видеть в моем коде. Таким образом, он не становится слишком массивным.