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 说,“采用这种方法写出该过程时,你就把一个 Θ(logn) \Theta(log\thinspace n) 的计算过程变成 Θ(n) \Theta(n) 的了。” 请解释这一问题。

先测试一下使用这个建议的效果

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

展开式:

results matching ""

    No results matching ""