Chinaunix

标题: SICP 习题参考答案 1.2 [打印本页]

---

作者: win_hate    时间: 2008-09-07 09:49
标题: SICP 习题参考答案 1.2

1. 
   
2. 此帖为 SICP 章节 1.2 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。
   

复制代码

• 本节电子版：[1.2  Procedures and the Processes They Generate]
  
• 答案目录：[点这里]
  

[ 本帖最后由 win_hate 于 2008-9-13 16:56 编辑 ]

---

作者: win_hate    时间: 2008-09-07 09:49
标题: Exercise 1.9.
Exercise 1.9.  Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

---

作者: win_hate    时间: 2008-09-07 09:50
标题: Exercise 1.9. 答案
[解]  第一个是 recursive 的，而第二个是 iterative 的。

---

作者: win_hate    时间: 2008-09-07 09:51
标题: Exercise 1.10
Exercise 1.10.  The following procedure computes a mathematical function called Ackermann's function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n^2.

[ 本帖最后由 win_hate 于 2008-9-7 09:54 编辑 ]

---

作者: win_hate    时间: 2008-09-07 09:53
标题: Exercise 1.10. 答案
[解]
(A 0 n)=2n
(A 1 n)=2^n
(A 2 n) = 2^2^2...^2    // n 个 2，右结合

---

作者: win_hate    时间: 2008-09-07 11:18
标题: Exercise 1.11.
Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

---

作者: win_hate    时间: 2008-09-07 11:21
标题: Exercise 1.11. 答案
递归代码

1. 
   
2. (define (f n)
   
3.   (if (< n 3) n
   
4.       (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
   

复制代码

迭代代码

1. 
   
2. (define (g x y z n)
   
3.   (if (= 0 n) x
   
4.       (g y z (+ (* 3 x) (* 2 y) z) (- n 1))))
   

复制代码

迭代代码这样使用：

1. 
   
2. (g 0 1 2 n)
   

复制代码

[ 本帖最后由 win_hate 于 2008-9-7 11:22 编辑 ]

---

作者: win_hate    时间: 2008-09-07 11:24
标题: Exercise 1.12.
Exercise 1.12.  The following pattern of numbers is called Pascal's triangle.



The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

[ 本帖最后由 win_hate 于 2008-9-8 19:07 编辑 ]

---

作者: win_hate    时间: 2008-09-07 11:32
标题: Exercise 1.12. 答案

1. 
   
2. (define (binomial n m)
   
3.   (if (or (= m 0) (= m n))
   
4.       1
   
5.       (+ (binomial (- n 1) m) (binomial (- n 1) (- m 1)))))
   

复制代码

上面的递归虽然很直观，却是一个坏递归的例子。其空间需求以指数方式增长，并做了大量重复的工作。下面这个效率较高，但可读性就差一些。

1. 
   
2. (define (binomial n m)
   
3.   (define (f n m r)
   
4.     (if (= m 0) r (f (- n 1) (- m 1) (/ (* r n) m))))
   
5. 
   
6.   (cond ((< m 0) 0)
   
7.         ((= m 0) 1)
   
8.         ((> m n) 0)
   
9.         ((= n m) 1)
   
10.         ((and (> n 0) (> (* 2 m) n)) (f n (- n m) 1))
    
11.         (else (f n m 1))))
    

复制代码

[ 本帖最后由 win_hate 于 2008-9-7 12:23 编辑 ]

---

作者: win_hate    时间: 2008-09-08 19:15
标题: Exercise 1.12
Exercise 1.13.  Prove that Fib(n) is the closest integer to ^n/5, where  = (1 + 5)/2. Hint: Let   = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (^n  -^n)/5.

[ 本帖最后由 win_hate 于 2008-9-8 19:21 编辑 ]

---

作者: win_hate    时间: 2008-09-08 19:24
标题: Exercise 1.12 答案
Fib(n)=(phi^n-psi^n)/sqrt(5)

容易证明：

1、|psi|<1, 所以 |(psi)^n|<1
2、1/sqrt(5)<1/2

所以 |psi^n/sqrt(5)|<1/2，即 Fib(n) 是最接近 phi^n/sqrt(5) 的整数。

---

作者: win_hate    时间: 2008-09-08 19:26
标题: Exercise 1.14
Exercise 1.14.  Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

---

作者: win_hate    时间: 2008-09-08 19:28
标题: Exercise 1.14. 答案
等我素描班毕业后再画。

---

作者: win_hate    时间: 2008-09-08 19:30
标题: Exercise 1.15.
Exercise 1.15.  The sine of an angle (specified in radians) can be computed by making use of the approximation sin x x if x is sufficiently small, and the trigonometric identity



to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered ``sufficiently small'' if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a.  How many times is the procedure p applied when (sine 12.15) is evaluated?

b.  What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

[ 本帖最后由 win_hate 于 2008-9-8 19:31 编辑 ]

---

作者: win_hate    时间: 2008-09-08 19:36
标题: Exercise 1.15. 答案
a) 5 次

计算次数的代码为

1. 
   
2. (ceiling (/ (log 121.5) (log 3)))
   

复制代码

b) 如果直接用书中代码进行计算，则时间增长和空间增长都是， O(log_3 10a)

不过，因为 sin 是周期函数，所以在调用 sine 之前先约化到 [-pi, pi]  间是合适的。如采用这种方式，则时间和空间都是  O(1) 的。

[ 本帖最后由 win_hate 于 2008-9-8 19:41 编辑 ]

---

作者: win_hate    时间: 2008-09-09 13:08
标题: Exercise 1.16.
Exercise 1.16.  Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b^(n/2))^2 = (b^2)^(n/2), keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

[ 本帖最后由 win_hate 于 2008-9-9 13:15 编辑 ]

---

作者: win_hate    时间: 2008-09-09 13:11
标题: Exercise 1.16. 答案

1. 
   
2. (define (pow b n)
   
3.   (define (f b n c)
   
4.     (cond ((= n 0) c)
   
5.           ((even? n) (f (* b b) (/ n 2) c))
   
6.           (else (f b (- n 1) (* b c)))))
   
7. 
   
8.     (f b n 1))
   

复制代码

---

作者: win_hate    时间: 2008-09-09 13:16
标题: Exercise 1.17.
Exercise 1.17.  The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

---

作者: win_hate    时间: 2008-09-09 13:16
标题: Exercise 1.17. 答案

1. 
   
2. (define (mul a b)
   
3.   (define (f a b c)
   
4.     (cond ((= b 0) c)
   
5.           ((even? b) (f (+ a a) (/ b 2) c))
   
6.           (else (f a (- b 1) (+ c a)))))
   
7. 
   
8.   (f a b 0))
   

复制代码

---

作者: win_hate    时间: 2008-09-09 13:20
标题: Exercise 1.18.
Exercise 1.18.  Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.40

---

作者: win_hate    时间: 2008-09-09 13:21
标题: Exercise 1.18. 答案

1. 
   
2. (define (mul a b)
   
3.   (define (f a b c)
   
4.     (cond ((= b 0) c)
   
5.           ((even? b) (f (+ a a) (/ b 2) c))
   
6.           (else (f a (- b 1) (+ c a)))))
   
7. 
   
8.   (f a b 0))
   

复制代码

---

作者: win_hate    时间: 2008-09-09 13:28
标题: Exercise 1.19.
Exercise 1.19.   There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a  a + b and b  a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a  bq + aq + ap and b  bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:41

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

[ 本帖最后由 win_hate 于 2008-9-9 13:30 编辑 ]

---

作者: win_hate    时间: 2008-09-09 13:30
标题: Exercise 1.19. 答案

1. 
   
2. (define (fib n)
   
3.   (fib-iter 1 0 0 1 n))
   
4. (define (fib-iter a b p q count)
   
5.   (cond ((= count 0) b)
   
6.         ((even? count)
   
7.          (fib-iter a
   
8.                    b
   
9.                    (+ (* p p) (* q q))      ; compute p'
   
10.                    (+ (* 2 p q) (* q q))    ; compute q'
    
11.                    (/ count 2)))
    
12.         (else (fib-iter (+ (* b q) (* a q) (* a p))
    
13.                         (+ (* b p) (* a q))
    
14.                         p
    
15.                         q
    
16.                         (- count 1)))))
    

复制代码

理论分析：

把矩阵 T:=

1 1
1 0

乘到 (fib(n-1) fib(n-2))^t 上就可以得到 (fib(n) fin(n-1)). 所以求 (fib(n+1) fib(n)) 相当于计算 T^n (1,0)^t。

若 a 是半群 A 的一个元素，则总可以用本节说讲的方法计算 a^n. 这种方法实际上是从右向左扫描 n 的比特，也可以采用从左向右扫描比特方法。

如果 a 在 A 中有逆且容易求出，则计算的开销可以进一步减少。

参考资料：

• 关于 fib 序列的计算，可以参考我 blog 上的一个帖子：[计算 Fibonacci 数的一些注记]
  
• 关于 fibonacci 数列的一般性介绍，可以参考维基百科的词条: [Fibonacci Number].
  
• 关于 Fibonacci 的生平，可以参考维基百科的词条: [Fibonacci].
  

======================================================================

Leonardo of Pisa (Fibonacci)

1170~1250

意大利数学家

[ 本帖最后由 win_hate 于 2008-9-14 11:53 编辑 ]

---

作者: win_hate    时间: 2008-09-11 21:44
标题: Exercise 1.20.

1. 
   
2. (define (gcd a b)
   
3.   (if (= b 0)
   
4.       a
   
5.       (gcd b (remainder a b))))
   

复制代码

Exercise 1.20.  The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?

---

作者: win_hate    时间: 2008-09-11 22:02
标题: Exercise 1.20. 答案
应用序比较简单，把它放前面来。

(2) 应用序  

辗转序列为 206, 40, 6, 4, 2, 0

显然进行了 4 次 remainder.


(1) 正则序

把 reaminder 简单记为 r，分析一下逐步展开的过程

1. 
   
2. (if (= b 0) a
   
3.   (gcd b (r a b)))
   

复制代码

继续

1. 
   
2. (if (= b 0) a
   
3.   (if (= (r a b) 0) b
   
4.     (gcd (r a b) (r b (r a b)))))
   

复制代码

1. 
   
2. (if (= b 0) a
   
3.   (if (= (r a b) 0) b
   
4.     (if (= 0 (r b (r a b))) (r a b)
   
5.       (gcd (r b (r a b)) (r (r a b) (r b (r a b))))
   

复制代码

r 会在两个地方被执行，一是 if 判断 r 的结果是否为 0， 另一个是最终返回的最大公因子，它是用一串嵌套的 r 来求值的。

辗转序列为 205, 40, (r 205, 40), (r 40 (r 205, 40)) , (r (r 205, 40) (r 40 (r 205 40))), .....

设这串数中每个数包含 r 的个数为 a(n)，r 的增长模式为

x, y -> (r x y)

所以 a(n)=a(n-1)+a(n-2)+1，这是个什么序列？变个形

a(n)+1 = a(n-1)+1 + a(n-2)+1，a(0)+1=a(1)+1=1.

原来 a(n)=fib(n)-1

辗转序列的值为 205, 40, 6, 4, 2, 0，包含 r 的个数为  0, 0, 1, 2, 4, 7。用 if 进行判断时，r 执行了 1+2+4+7=14 (次).

但返回的最大公因子是辗转序列的倒数第二项，其中含有 4 个 r。所以 r 总共被执行了

(1+2+4+7)+4 = 18 (次).

[ 本帖最后由 win_hate 于 2008-9-11 22:20 编辑 ]

---

作者: win_hate    时间: 2008-09-12 13:13
标题: Exercise 1.21.
Exercise 1.21.  Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

---

作者: win_hate    时间: 2008-09-12 13:16
标题: Exercise 1.21. 答案

1. 
   
2. > (map smallest-divisor '(199 1999 19999))
   
3. (199 1999 7)
   

复制代码

---

作者: win_hate    时间: 2008-09-12 13:17
标题: Exercise 1.22.
Exercise 1.22.  Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of (n), you should expect that testing for primes around 10,000 should take about 10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

---

作者: win_hate    时间: 2008-09-12 13:20
标题: Exercise 1.22. 答案
在 guile, scm 中，runtime 的对应函数为 current-time，返回的单位是秒。在 mzscheme 中，runtime 的对应函数为 current-milliseconds，精确度要高一些。在这里，我们使用后者。

1. 
   
2. (define (search-for-primes a b)
   
3.   (define (timed-prime-test n)
   
4.     (newline)
   
5.     (display n)
   
6.     (start-prime-test n (current-milliseconds)))
   
7.   
   
8.   (define (start-prime-test n start-time)
   
9.     (if (prime? n)
   
10.          (report-prime (- (current-milliseconds) start-time))))
    
11.   
    
12.   (define (report-prime elapsed-time)
    
13.     (display " *** ")
    
14.     (display elapsed-time))
    
15. 
    
16.   (cond ((even? a) (search-for-primes (+ a 1) b))
    
17.         ((< a b) (if (timed-prime-test a) (search-for-primes (+ a 2) b)))))
    

复制代码

用上面的代码可以找出相应的素数为：

1009 , 10007, 100003, 1000003

接着讨论时间复杂度。现在的计算机速度很快，在我的机器上，测试前三个素数的时间为 0 毫秒，而测试 1000003 的时间是 1 毫秒。所以有必要把对一个数的测试反复执行多次。为此，我写了一个 prime-test-prof

1. 
   
2. (define (prime-test-prof p m)
   
3.     (define (f m)
   
4.       (cond ((> m 0) (prime? p)
   
5.              (f (- m 1)))))
   
6.             
   
7.   (let ((t (current-milliseconds)))
   
8.     (f m)
   
9.     (- (current-milliseconds) t)))
   

复制代码

执行 100 次的时间

1009: 5
10007: 12

(* 5 (sqrt 10)) =15.811388300841898

执行 1000 次的时间

1009: 45
10007:130

(* 45 (sqrt 10))=142.30249470757707

执行 10000 次的时间

1009: 224
10007:940

(* 224 (sqrt 10))=708.350195877717

执行 100000 次的时间

1009: 2153
10007: 7060

(* 2153 (sqrt 7060))=6808.383802342521

执行 500000 次的时间

1090: 9968
10007: 32669

(* 9968 (sqrt 10))=31521.583716558405

当执行次数比较多时，因子 sqrt(10) 还算比较精确的。

将被测试的数改为 100003 和 1000003 的结果与上面的类似，仍然是 3 倍左右的关系。 这里是一个执行 100000 次的结果

100000 次

100003：19649
1000003：62005

最后一个问题：

Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

题目中的 steps 比较含糊，不清楚是什么意思。如果是在一台理想的计算机上，这些 step 直接对应为机器的指令（或总复杂度为 O(1) 的指令序列），那么上述说法对运行时间的上界应该是正确的。

但如果一个 step 只是概念上的，则不然。比如在前面的运算中，我们用到加法，乘法，除法。注意到很多 scheme 实现支持任意长度的整数运算，所以这些运算的复杂度与参与运算的数的大小相关。

[ 本帖最后由 win_hate 于 2008-9-12 14:18 编辑 ]

---

作者: win_hate    时间: 2008-09-13 10:56
标题: Exercise 1.23.
Exercise 1.23.  The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?

---

作者: win_hate    时间: 2008-09-13 11:00
标题: Exercise 1.23. 答案
理论估计和实际测试的结果都支持工作量减半的说法。

我把 smallest-divisor 改为

1. 
   
2. (define (smallest-divisor n)
   
3.   (define (f m)
   
4.     (cond ((> (square m) n) n)
   
5.           ((divides? m n) m)
   
6.           (else (f (+ m 2)))))
   
7.   (if (even? n) 2 (f 3)))
   

复制代码

在改动之前，(prime-test-prof 100003 10000) 输出为 2319
在改动之后，输出为 1149.

---

作者: win_hate    时间: 2008-09-13 11:21
标题: Exercise 1.24.
Exercise 1.24.  Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has (log n) growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

---

作者: win_hate    时间: 2008-09-13 11:36
标题: Exercise 1.24. 答案
实际测试与 tha(log n) 的估计并不能很好地吻合。这里的 log (n) 与用 smallest-divisor 时的 sqrt(n) 估计不同。后者是一个很精确的估计，几乎就是实际的工作量；而前者是一个比较粗放的估计，只是一个边界。tha(log n) 是说，存在一组满足 log n 关系的上界，也存在一组满足 log n 关系的下界，实际的工作时间在两者之间。

[ 本帖最后由 win_hate 于 2008-9-13 11:52 编辑 ]

---

作者: win_hate    时间: 2008-09-13 11:38
标题: Exercise 1.25.
Exercise 1.25.  Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

---

作者: win_hate    时间: 2008-09-13 11:43
标题: Exercise 1.25. 答案
从纯数学的角度看，这个做法是完全正确的。在计算 a^n (mod m) 时，可以在中间过程中通过不断取模来限制对象的规模；也可以先计算出 a^n，最后取一次模。Alyssa P. Hacker 采用的就是后面的方法。从实现的角度看，这个做法是完全不可取的。

---

作者: win_hate    时间: 2008-09-13 11:45
标题: Exercise 1.26.
Exercise 1.26.  Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling 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))))

``I don't see what difference that could make,'' says Louis. ``I do.'' says Eva. ``By writing the procedure like that, you have transformed the (log n) process into a (n) process.'' Explain.

---

作者: win_hate    时间: 2008-09-13 11:47
标题: Exercise 1.26. 答案

1. 
   
2. (expmod base exp m)-> (remainder (* (expmod base (/ exp 2) m)
   
3.                                                             (expmod base (/ exp 2) m))
   

复制代码

这变成树型递归了，回忆经典的 fib 递归。

---

作者: win_hate    时间: 2008-09-14 10:29
标题: Exercise 1.27.
Exercise 1.27.  Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether a^n is congruent to a modulo n for every a<n, and try your procedure on the given Carmichael numbers.

---

作者: win_hate    时间: 2008-09-14 10:57
标题: Exercise 1.27. 答案

1. 
   
2. (define (fermat-liar? n)
   
3.   (define (test a)
   
4.     (cond ((= a n) #t)
   
5.           ((= (powmod a n n) a) #t)
   
6.           (else (test (+ a 1)))))
   
7. 
   
8.   (test 2))
   

复制代码

注意，上面的代码要求 n 为合数。如果 n 是素的，则上述函数总返回 #t.

按书上注释 ［47]，开始的几个 carmichael 数为: 561, 1105, 1729, 2465, 2821, 和 6601，用上面的过程测一下:

1. 
   
2. > (map fermat-liar? '(561 1105 1729 2465 2821 6601))
   
3. (#t #t #t #t #t #t)
   

复制代码

======================================================================


理论分析

Carmichael 数 n 总具有如下特点

• square free
• 若 n=p1 p2 ... pm, 则  pi-1 | n-1, 其中  0<i < m+1.
  

容易证明，对于任意  pi, 总有 pi^(n-1) =1 (mod n/pi)。这样就得到了 pi^n=pi (mod n)。

于是，对 [0,n) 中的任意一个素数，f:x->x^n (mod n) 是个单位映射。由于 f 是完全积性的，所以对 [0, n) 中的每个数，f 都是单位映射。

关于 Carmichael 数的一般性介绍，可以参考维基百科的词条 [Carmichael Number]

[ 本帖最后由 win_hate 于 2008-9-14 11:20 编辑 ]

---

作者: win_hate    时间: 2008-09-15 09:53
标题: Exercise 1.28.
Exercise 1.28.  One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n - 1)st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number a<n and raise a to the (n - 1)st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a ``nontrivial square root of 1 modulo n,'' that is, a number not equal to 1 or n - 1 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a<n, computing a^(n-1) in this way will reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check your procedure by testing various known primes and non-primes. Hint: One convenient way to make expmod signal is to have it return 0.

[ 本帖最后由 win_hate 于 2008-9-15 09:54 编辑 ]

---

作者: win_hate    时间: 2008-09-15 10:00
标题: Exercise 1.28. 答案

1. 
   
2. (define (mr-test n m)
   
3.   (define (pot2 m)
   
4.     (letrec ((f (lambda (e o)
   
5.                   (if (even? o) (f (+ e 1) (/ o 2))
   
6.                       (cons e o)))))
   
7.       (f 0 m)))
   
8.   
   
9.   (define (make-test-fun)
   
10.     (define (second-check b e)
    
11.       (cond ((= (- n 1) b) #t)
    
12.             ((= 1 b) #f)
    
13.             ((= e 1) #f)
    
14.             (else (second-check (modulo (* b b) n) (- e 1)))))
    
15.    
    
16.     (let* ((t (pot2 (- n 1))) (e (car t)) (o (cdr t)))
    
17.       (lambda ()
    
18.         (let* ((r (+ (random (- n 1)) 1)) (b (powmod r o n)))
    
19.           (cond ((= 1 b) #t)
    
20.                 ((= 0 e) #f)
    
21.                 ((= (- n 1) b) #t)
    
22.                 (else (second-check b e)))))))
    
23.   
    
24.   (let ((f (make-test-fun)))
    
25.     (letrec ((loop (lambda (m)
    
26.                      (cond ((= m 0) #t)
    
27.                            ((f) (loop (- m 1)))
    
28.                            (else #f)))))
    
29.       (loop m))))
    

复制代码

对 Carmichael 数试一下效果：

1. 
   
2. >(map (lambda (x) (mr-test x 5)) '(561 1105 1729 2465 2821 6601))
   
3. (#f #f #f #f #f #f)
   

复制代码

======================================================================

理论分析：

• 如果 n 是个素数，a in [0, n). 根据 Fermat 小定理，有 a^(n-1)=1 (mod n)。
  
• n-1 是偶数，可以写成 2^mk 的形式，其中 k 是奇数。于是  a^(n-1)=1 可以改写为  a^(2^m k)。
  
• 设  b=a^k，考虑以下序列
  
  B＝( b, b^2, b^8, ..., b^(2^m k) ) (mod n)
  
  序列中的每个均是其后继模 n 意义下的平方根。
  
• 当 n 为素数时， 模 n 意义下， 1 仅有两个平方根 1 和 -1 (这是 MR 测试用来区分素数、合数的关键。对于合数 n，1 的平方根可以多于两个)。
  
• B 序列可能的模式为
  
  模式 1：(? ? ? ... ? ? ? -1 1 ... 1)
  
  模式 2：(1 1 1 ... 1 1 1 1 1 ... 1)
  
  其中 `?' 为 1, -1 以外的数，而且第一种模式包括 (-1, 1, 1, ..., 1)
  
• mr 测试的大致步骤为，依次计算 B 序列中的数（除了最后一个），
  
  • 如果一上来就是 1，则是模式 2，可以马上返回，概率推断 n 为素数。
  • 如果在途中碰到一个 -1，则是模式 1， 可以马上返回，概率推断 n 为素数。
  • 如果在途中遇到 1（但不是B0)，则不是前述两种模式，必定为合数。
  • 如果在途中一直没有碰到 1, -1，则计算到倒数第二项终止。由于倒数第二项是末项的平方根，但不是 1,-1，所以末项必定不是 1, 从而 n 也必定是个合数。
    

代码说明：

• pot2 返回一对  cons e.o，如果 n=2^m k，则 e=m, k=o.
  
• make-test-fun 的返回值是一个函数，包含了必要的参数。之后每执行其返回值一次，就进行了一次随机的 mr-test.
  
• make-test-fun 中的 second-check 是对序列检查的第二部分（对 B0 的检查比较特殊，之后的检查是 second-check）。
  
• mr-test  的流程为用 make-test-fun 生成测试函数，并绑定在 f 上。用 loop 函数实现循环测试。
  

参考资料：

• 关于 Miller-Rabin 素性测试的一般性描述，可以参考维基百科的词条：[Miller–Rabin primality test]
• 对于 Miller-Rabin 测试的更深入讨论，如失误概率的大小等，可以参考更专业的文献。比如裴定一的 [算法数论].
  

[ 本帖最后由 win_hate 于 2008-9-15 10:50 编辑 ]

---

作者: win_hate    时间: 2008-09-15 11:05
标题: done
这小节完了，在这里留个空间，以备后用。

---

作者: win_hate    时间: 2008-09-15 11:30
标题: 花絮：Fermat vs Fermat
Fermat 小定理非常有名，它是素性判定的一件利器。Fermat 数也很有名， Fermat 声称所有 Fermat 数都是素的，特别地， F_5 是一个素数。下面我们把 Fermat 小定理用到 Fermat 数上：

1. 
   
2. >(define f5 (+ 1 (pow 2 32)))
   
3. >(powmod 2 (- f5 1) f5)
   
4. 1
   

复制代码

Oops

再来

1. 
   
2. >(powmod 3 (- f5 1) f5)
   
3. 3029026160
   

复制代码

f5 不是一个素数！

虽然上面的计算不太适合手工进行，但却远非不可行的。那个时代的数学家虽然没有计算机，但那也导致了他们精于手工计算。以 Fermat 的能力，他确可以进行这种检验。Fermat 为什么不对 F5 进行检验呢？要么是他太自信了，要么就是他根本没注意到 Fermat 小定理还可以进行素性测试，我比较倾向于后一种推测。

Fermat 数列堪称史上最阴险之数列。它的前 5 个，规模比较小，适合手工分解，全是素数。但从第 6 个开始，这些数的规模急剧增长，变得不适合手工分解，但似乎都是合数！这分明就是为 Fermat 准备的一个陷阱。

Fermat 死于 1665  年，直到 100 多年后(1772)，Euler 才发现了 F5 的分解式。其方法很巧妙，大大减少了因子的测试，但利用了 Feramt 数的特征，并不是一个通用的分解方法。

[ 本帖最后由 win_hate 于 2008-9-15 11:32 编辑 ]

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2