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 说，“采用这种方法写出该过程时，你就把一个 Θ(log n) \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)

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)

展开式：

results matching ""

    No results matching ""