1.25
练习 1.25：Alyssa P. Hacker 提出，在写 expmod 时我们做了过多的额外工作。她说，毕竟我们已经知道怎样计算乘幂，因此只需要简单地写：
(define (expmod base exp m)
(remainder (fast-expt base exp) m))
她说的对吗？这一过程能很好地用于我们的快速素数检查程序吗？请解释这些问题。
先测试一下使用这个建议的效果
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)
)
)
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a)
)
(try-it (+ 1 (random (- n 1))))
)
(define (expmod base exp m)
(remainder (fast-expt base exp) m)
)
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (fast-prime? n 5)
(report-prime (- (runtime) start-time)) (display " 不是素数！")))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (square x) (* x x))
(timed-prime-test 7)
(timed-prime-test 14)
分别找出大于 1 000、10 000、100 000、1 000 000 的三个最小素数。
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)
)
)
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a)
)
(try-it (+ 1 (random (- n 1))))
)
(define (expmod base exp m)
(remainder (fast-expt base exp) m)
)
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)
)
)
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a)
)
(try-it (+ 1 (random (- n 1))))
)
(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)
)
)
)
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (fast-prime? n 5)
(report-prime n (- (runtime) start-time)) #f))
(define (square x) (* x x))
(define (report-prime n elapsed-time)
(newline)
(display n)
(display " *** ")
(display elapsed-time)
(display ", 它的 \\log{n} 倍时间是 ")
(display (* elapsed-time (log elapsed-time)))
)
(define (timed-prime-test-between n1 n2 found)
(if (timed-prime-test n1)
(if (or (> found 1) (> n1 n2))
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 (+ found 1))
)
(if (> n1 n2)
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 found)
)
)
)
(newline)
(display "大于 1000 的三个最小素数：")
(timed-prime-test-between 1001 9999 0)
(newline)
(newline)
(display "大于 10 000 的三个最小素数：")
(timed-prime-test-between 10001 99999 0)
(newline)
(newline)
(display "大于 100 000 的三个最小素数：")
(timed-prime-test-between 100001 999999 0)
(newline)
(newline)
(display "大于 1 000 000 的三个最小素数：")
(timed-prime-test-between 1000001 9999999 0)
(newline)
对比 1.24，可以看出，得出的结果是一致的，但是更慢。
对比 1.25 与 1.24 的具体实现，代码上的区别仅在于 1.24 是将 remainder 算子嵌入了 fast-expt 的执行分支里，从代码上看 1.24 的代码重复更多（remainder 在每个分支都要写一次，而 1.25 通过将 remainder 写在最外层，显得更优雅，更正交），但是其性能却更好。
处于快速实现素数检查的目的，该方法导致了更慢的实现是不可接受的。我还还不能解释这个现象的根本原因。