SICP读书笔记1.2 | Senghoo Kim

练习 1.9

方法1

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

所以方法1是递归计算过程

方法2

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

所以方法2是送代计算过程

练习1.10

(A 1 10) ;1024
(A 2 4)  ;65536
(A 3 3)  ;65536

(f n)为 $2 \times n$

(g n)为 $2^n$

(h n)为 $2^{2^{ \cdot^{ \cdot^2} } }$ 有n个2

练习1.11

递归


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

送代

(define (f n)
  (define (iter a b c cnt)
    (if (= cnt 0)
        a
        (iter (+ a
                 (* 2 b)
                 (* 3 c))
              a b
              (- cnt 1))))
  (if (< n 3)
      n
      (iter 2 1 0 (- n 2))))

练习1.12

(define (pascal x y)
  (cond ((= x 0) 1)
        ((= y 0) 1)
        ((= x y) 1)
        (else (+ (pascal (- x 1) (- y 1))
                 (pascal (- x 1) y)))))

练习 1.15

a) 5次

参数分别为:

(p (sine 4.05))
(p (sine 1.35))
(p (sine 0.45))
(p (sine 0.15))
(p (sine 0.05))

b) $log n :$

angle 每次变为上次的三分之一

练习 1.16

每次循环 $x^y = a \times b^n$

(define (fast-expt x y)
  (define (iter a b n)
    (if (= n 0)
        a
        (if (even? n)
            (iter a (* b b) (/ n 2))
            (iter (* a b) b (- n 1))) ))
  (iter 1 x y))

练习 1.17

每次循环 $x \times y = s + a \times b$

(define (double a)
  (* a 2))

(define (halve a)
  (/ a 2))

(define (times a b)
  (if (= b 1)
      a
      (if (even? b)
          (double (fast-times a (halve b)))
          (+ a (fast-times a (- b 1))))))

练习 1.18

每次循环 $x \times y = s + a \times b$

(define (double a)
  (* a 2))

(define (halve a)
  (/ a 2))

(define (fast-times x y)
  (define (iter s a b)
    (if (= b 0)
        s
        (if (even? b)
            (iter s (double a) (halve b))
            (iter (+ s a) a (- b 1)))))
  (iter 0 x y))

练习1.19

$a \leftarrow bq+aq+ap$ $b \leftarrow bp+aq$

推出

$a' \leftarrow (2pq+q^2)b + (2pq+q^2)a + (q^2 p^2)a$ $b' \leftarrow (p^2+q^2)b + (2pq+q^2)a$ $\therefore$ $p' = p^2+q^2$ $q' = 2pq+q^2$

完整程序：

(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
                   (+ (* p p) (* q q))
                   (+ (* p q 2) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

练习1.20

正则序：

(gcd 206 40) ;; 0次
(if (= 40 0) 206 (gcd 40 (remainder 206 40))) ;; 1 次
(if (= (remainder 206 40) 0) 40 (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))  ;;4次
....

从中看出gcd在正则序求值的过程中。remainder 的计算次数根据送代次数指数级增长。

应用序

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 6 (remainder 40 6))
(gcd 4 (remainder 6 4))
(gcd 2 (remainder 4 2))

应用序求值过程中remainder 的计算次数根据送代次数线性增长

练习1.21

代码:

(define (square n) (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((devides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (devides? a b)
  (= (remainder b a) 0))

结果:

#;496> (smallest-divisor 199)
199
#;506> (smallest-divisor 1999)
1999
#;512> (smallest-divisor 19999)
7

练习1.22

继续练习1.21的代码

(define (prime? n)
  (= n (smallest-divisor n)))

(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))

(define (search-for-primes min max)
  (cond ((even? min) (search-for-primes (+ min 1) max))
        ((< min max)
         (timed-prime-test min)
         (search-for-primes (+ min 2) max))))

练习1.23

(define (square n) (* n n))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (devides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((devides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (next test-divisor)
  (if (= test-divisor 2)
      3
      (+ test-divisor 2)))

练习1.24

(define (expmod base exp n)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) n))
                    n))
        (else
         (remainder (* base (expmod base (- exp 1) n))
                    n))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

运行速度没按预期等比变化的原因是，速度不光受算法影响，还受机器负载，解释器优化等多方面的影响。

练习1.25

新的函数可能会产生精度不够导致的误差

fast-expt的计算结果可能很大，导致精度不够或者溢出，并且从计算速度上处理这种超大数字效率很低。

练习 1.26

(* (expmod base (/ exp 2) m)
   (expmod base (/ exp 2) m))

这部分代码实际上是计算了两次expmod 然后相乘，而不是计算一次然后区平方。

所以此段代码没起到原本的计算规模减少一半的效果。所以复杂度为 $\Theta(n)$

练习1.27

(define (expmod base exp n)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) n))
                    n))
        (else
         (remainder (* base (expmod base (- exp 1) n))
                    n))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (define (iter i)
    (cond ((>= i n) #t)
          ((try-it i) (iter (+ i 1)))
          (else #f)))
  (iter 1))

练习1.28

书中描述的Miller-Rabin 好像和其他地方描述的算法好像有点不一样。

其他地方的描述共参考

Wikipedia

Matrix64

单纯书中的描述的算法来看证明如下(如有错误请多指教)：

根据书中描述，对于数p如果存在x ( $x \neq 1 , x \neq (p-1), x \le p$ )

$x^2 mod p = 1$

则 p不是素数

证明如下

$x^2 \equiv 1 \pmod p$ $x^2 -1 \equiv 0 \pmod p$ $(x-1)(x+1) \equiv 0 \pmod p$

如果p 是素数：

$(x+1) \mod p = 0$ 或 $(x-1) \mod p = 0$

但是 $x \neq 1 , x \neq (p-1), x \le p$ 不符合要求。

得证

根据上面的结果，新的函数为：

(define (expmod base exp n)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) n))
                    n))
        (else
         (remainder (* base (expmod base (- exp 1) n))
                    n))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

测试

#;520> (fermat-test 561)
#f
#;548> (fermat-test 1105)
#f
#;558> (fermat-test 1729)
#f
#;568> (fermat-test 2465)
#f
#;581> (fermat-test 2821)
#f
#;595> (fermat-test 6601)
#f