1.26
练习 1.26：Louis Reasoner 在做练习 1.24 时遇到了很大的困难，他的 fast-prime? 检查看起来运行得比他得 prime? 还慢。Louise 请他得朋友 Eva Lu Ator 过来帮忙。在检查 Louis 的代码时，两个人发现他重写了 expmod 过程，其中用了一个显式的乘法，而没有调用 square：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
“我看不出这会造成什么不同，”Louis 说。“我能看出，”Eva 说，“采用这种方法写出该过程时，你就把一个 的计算过程变成 的了。” 请解释这一问题。
先测试一下使用这个建议的效果
(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 (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
m)
)
(else
(remainder (* base (expmod base (- exp 1) m))
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-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 (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 (* (expmod base (/ exp 2) m) (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 的实现已经不算太差了。
通过将 square 替换成显式地乘法，导致 (expmod base (/ exp 2) m) 的计算次数在每次计算余数时，都会增加一倍，又由于递归，导致最终大量的重复计算。如果不能通过定义 square 的方式来避免，可以采用过程式语言中的特性，先将 (expmod base (/ exp 2) m) 计算出来储存在一个变量中，然后再乘以自己。从而达到和 square 相同的效果。
1.24 和 1.26 的区别从代码上看仅在于把 square 展开成了 乘法*，来对比一下其展开式。
1.24 版：
(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 (square x) (* x x))
(expmod 2 10 100)
其展开式：
1.26 版：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
m)
)
(else
(remainder (* base (expmod base (- exp 1) m))
m)
)
)
)
(expmod 2 10 100)
展开式：