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 写在最外层，显得更优雅，更正交），但是其性能却更好。

处于快速实现素数检查的目的，该方法导致了更慢的实现是不可接受的。我还还不能解释这个现象的根本原因。

results matching ""

    No results matching ""