SICP 习题参考答案 1.2

win_hate

理论估计和实际测试的结果都支持工作量减半的说法。

我把 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

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

实际测试与 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

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

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

win_hate

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

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

复制代码

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

win_hate

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

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

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 编辑 ]