SICP

Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written

(define (expmod base exp m) (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

对比之前的版本

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

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

我们可以看出，只有一个语句的版本是全部算出 exp 次方的值之后再去进行 remainder 操作，而后一个版本，每次计算的都是比较小的值（因为每次递归返回的时候，都只是 remainder 的值，都小于 m。

我们现在用 Fermat 方法来测试 100000001 是否是素数，来验证一下这个想法。

使用第一种方法，假设，随机生成了一个小于该数的数为 99999999。那么我们就要求

(remainder
    (fast-expt 99999999 100000001)
    100000001)

我们就需要求出 $99999999^{100000001}$ 的数值。这是不现实的。而第二种方法中，每次 expmod 返回的值都不会大于 100000001。所做的操作最大的就是 square 或者是与 99999999 的乘积，是完全可以接受的。

SICP 全笔记