乐正

Actions speak louder than words.

Sicp-ex1-24

问题

修改练习1.22中的timed-prime-test过程,让它使用fast-prime?(费马方法),并检查 你在该练习中找出的12个素数。因为费马检查具有$\Theta (\log n)$的增长速度,对接近 1000000的素数检查与接近1000的素数检查作对期望时间之间的比较有怎么样的预期?你的 数据确实表明了这一预期吗?你能解释所发现的任何不符合预期的地方吗?

解答

首先将fast-prime?过程加载到解释器中:

fast-prime? (fast-prime.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(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 (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (prime? n)
  (fast-prime? n 10))

然后加载使用fast-prime?过程的寻找素数的过程:

练习1.24 (ex1-24.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(define (search-for-primes start count)
  (define (next-odd n)
    (if (odd? n) (+ n 2)
        (+ n 1)))

  (define (search-for-primes-iter current count)
    (cond ((= count 0) (display "are primes"))
          ((fast-prime? current 10)
           (display current)
           (newline)
           (search-for-primes-iter (next-odd current) (- count 1)))
          (else (search-for-primes-iter (next-odd current) count))))

  (search-for-primes-iter start count))

(define (timed-search-for-primes start-number count)
  (define start-time (real-time-clock))

  (search-for-primes start-number count)
  (newline)
  (display " *** ")
  (newline)
  (display "Time costed: ")
  (display (- (real-time-clock) start-time)))

使用新的寻找素数过程完成练习1.22中查找的素数。其结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(timed-search-for-primes 1000 3)
1009
1013
1019
are primes
 ***
Time costed: 1
;Unspecified return value

(timed-search-for-primes 10000 3)
10007
10009
10037
are primes
 ***
Time costed: 1
;Unspecified return value

(timed-search-for-primes 100000 3)
100003
100019
100043
are primes
 ***
Time costed: 1
;Unspecified return value

(timed-search-for-primes 1000000 3)
1000003
1000033
1000037
are primes
 ***
Time costed: 2
;Unspecified return value

尽管费马检查具有$\Theta (\log {n})$的增长速度,但由于程序运行的速度并不只受到运 行步数一个因素影响,所以只能说接近1000的素数检查一定比接近100000的素数检查快。

draft

« sicp-ex1-23 sicp-ex1-25 »

Comments