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)
7 *** 4
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)
大于 1000 的三个最小素数:
1009 *** 123, 它的 \log{n} 倍时间是 591.8986757108073
1013 *** 109, 它的 \log{n} 倍时间是 511.3569191629766
1019 *** 101, 它的 \log{n} 倍时间是 466.1271722009672 测试结束!
大于 10 000 的三个最小素数:
10007 *** 1223, 它的 \log{n} 倍时间是 8694.382991945411
10009 *** 1499, 它的 \log{n} 倍时间是 10961.517693655795
10037 *** 1680, 它的 \log{n} 倍时间是 12476.602441627472 测试结束!
大于 100 000 的三个最小素数:
对比 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)
展开式: