algorithm - 我的迭代 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)))))

在 Racket 中使用您的示例输入进行了测试。如果您不使用 Racket，则需要将 sub1 和 sqr 替换为合适的实现。

请注意，虽然您确实必须对偶数指数的底进行平方，但您实际上可以修改其结果，正如您在我的代码中看到的那样。所以它不会变得太大。