SICP 1.2 过程及产生的过程
填坑
笔记
递归与迭代
说到递归的时候有两层含义。
一是指语法形式。从语法形式上讲，函数调用自身称为递归。
二是指计算方式。从计算方式上讲，将问题求解一层层地转化为子问题求解的计算方式称为递归。相对应地，从最底层的子问题开始求解，逐渐求得更高层乃至最后问题的计算方式称为迭代。
书中介绍了求阶乘的两种方法。从语法形式上讲都是递归。从计算方式上讲，一个是递归，一个是迭代。
递归的计算通常分为两步。一步是将问题的求解层层深入逐步化为子问题解的组合，也就是递进。下一步是求解子问题的解，组合这些解，层层返回，也就是回归。
迭代的计算只有一步。从最底层的问题开始求解，由底层问题的解得出高层问题的解，一层层叠上去，最终得到问题的解。
递归的计算过程是先展开后收缩，所以线性递归看来的形状像是一个从左到右箭头。
迭代的计算过程是一层层叠上去的，所以迭代看起来的形状像是一个从上到下直桶。
书中提到了尾递归。还提到了有了尾递归，循环结构就只是语法糖。
迭代计算过程的递归称为尾递归。尾递归之所以能够被现在编译器优化为循环是因为没有了回归的过程，也就是每一步的计算结果只与输入（参数）有关，不用考虑解的组合方式，如阶乘解的组合方式是相乘，斐波那契解的组合方式是相加。不考虑后可以丢弃上一步计算产生的结果和环境，防止爆栈。
递归的计算过程问题只分解为一个子问题的求解称为线性递归。
可能是因为这种方式子问题的增长是线性的 = = 。
递归的计算过程问题分解为两个子问题的求解称为树形递归，更确切地说是二叉树型递归。书中斐波那契的求解过程就是一个二叉树的中序遍历过程。
如果问题分解为三个子问题呢？那当然是三叉树啦！
递归转迭代
递归转迭代有一定的通用技巧。对于那些一眼就能看出如何迭代的，最简单的方式是用循环结构写一遍，然后转成递归的语法形式。如果看不出来，还有一条比较有用的技巧。把计算过程用到的所有上一个过程的量放到输入中，也就是参数化。所有计算的状态只需要全部输入就能还原。将迭代的过程转为参数的变化过程，这个过程中，设法保持参数变化，但结果不变。这一点可以参考习题 1.16
复杂度
衡量复杂度沿用了数学中的阶级比较记号。
$O$ 表示渐近上界，类似于 $\le$
$\Theta$ 表示夹在中间，类似于 $=$
$\Omega$ 表示渐进下界，类似于 $\ge$
这是大写记号。还有对应的小写记号。
$o$ 表示上界，类似于 $<$
$\omega$ 表示下界，类似于 $>$
例如对于 $f(n) = 3n^2 + n$ 有
$f(n) = O(n^2)$
$f(n) = \Theta(n^2)$
$f(n) = \Omega(n^2)$
$f(n) = o(n^3)$
$f(n) = \omega(n)$
因为 $O$ 表示渐进上界，所以经常用来描述算法最坏情况。
因为 $\Omega$ 表示渐进下界，所以经常用来描述算法最好情况。
而 $\Theta$ 通常用于描述算法的平均情况。
$O$ 会更常用。因为有时只需要知道最坏情况，还有就是 $O$ 打起来方便啊。不支持数学公式的情况下打 $\Theta$ 和 $\Omega$ 还要去找字符。
复杂度可以用于分析时间复杂度和空间复杂度。
时间复杂度是问题求解的步骤次数。
空间复杂度是问题求解的所需要的额外空间。
对于递归，空间复杂度的求解所需要的额外空间主要是记录参数，也就是求递归的深度。 时间复杂度可以考虑使用主方法求解。
习题
习题 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.
1 | (define (+ a b) |
分别展开就能区分。第一种方法
1 | (+ 2 3) |
第二种方法
1 | (+ 2 3) |
可以看出，第一种方式式子越来越长，整个过程像是一个箭头。而第二种式子式子长度不变，整个过程像是直桶。
第一种是递归的，因为它展开后再收缩，需要记录整个计算链。
第二种是迭代的，因为它没有发生嵌套，只需要记录两个变量。
习题 1.10
Exercise 1.10. The following procedure computes a mathematical function called Ackermann’s function.
1 | (define (A x y) |
What are the values of the following expressions?
1 | (A 1 10) |
Consider the following procedures, where A is the procedure defined above:
1 | (define (f n) (A 0 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$.
将式子带入求值即可。 (A 1 10)
1 | (A 1 10) |
(A 2 4)
1 | (A 2 4) |
(A 3 3)
1 | (A 3 3) |
(f n)
1 | (f n) |
(g n)
1 | (g n) |
(h n)
1 | (h n) |
所以答案是
(A 1 10) 为 $1024$
(A 2 4) 为 $65536$
(A 3 3) 为 $65536$
(f n) 为 $2n$
(g n) 为 $2^n$
(h n) 为
$$
h(n) = \begin{cases} 0 , &n = 0\\underbrace{2 ^ {2 ^ {2 ^ {. ^ {. ^{. ^ 2 }}}}}}_{n个 2} & n \ge 1 \end{cases}
$$
习题 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 \ge 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.
递归形式的很好写，直接翻译即可。
1 | (define (f n) |
观察递归的计算过程，分为两步。第一步展开，将递归式展开到有具体数值的分支。第二步计算，一步步计算回去。所以第二步就是想要的迭代。考虑到 $f(n)$ 需要 $f(n-1)$ ，$f(n-2)$ 和 $f(n-3)$ 三个变量，再加上当前计算到了第几个还需要一个变量。所以一共需要四个变量。用 $a$ $b$ $c$ 分别代表 $f(n-1)$ $f(n-2)$ $f(n-3)$ 。根据 $f$ 的定义得。
$a \leftarrow a + 2b + 3c$
$b \leftarrow a$
$c \leftarrow b$
翻译成代码
1 | (define (f-iter a b c n) |
但是这样的代码是有问题的。因为没有考虑 $n < 3$ 的情况。考虑到 $n < 3$ 的情况应该是这样的
1 | (define (f-iter a b c n) |
通过观察规律发现 $c = f(n)$ 所以还可以这么写
1 | (define (f-iter a b c n) |
测试
1 | (f 1) |
习题 1.12
Exercise 1.12. The following pattern of numbers is called Pascal’s triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
规律题目已经说明，假设 (y row col) 表示第 row 行第 col 列的值，则有
$$
y(row,col) = \begin{cases} 1, & col = 1\1 , & col = row\y(row - 1,col - 1) + y(row - 1,col) , & otherwise\end{cases}
$$
对应的代码为
1 | (define (y row col) |
测试
1 | (y 1 1) |
习题 1.13
Exercise 1.13. Prove that $Fib(n)$ is the closest integer to $\phi^n/\sqrt 5$, where $\phi = (1 + \sqrt 5) / 2$. Hint: Let $\psi = (1 - \sqrt 5)/2$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $Fib(n) = (\phi^n - \psi^n) / \sqrt 5$.
题目提示先证明 $Fib(n) = (\phi^n - \psi^n) / \sqrt 5$ 。
这里使用最偷懒最耍赖的数学归纳法来证明。
当 $n = 0$ 时 $Fib(0) = (\phi^0 - \psi^0)/\sqrt 5 = 0 / \sqrt 5 = 0$ ，等式成立。
当 $n = 1$ 时
$$
\begin{aligned}
Fib(1)& = (\phi^1 - \psi^ 1) / \sqrt 5
\&= (\phi - \psi) / \sqrt 5
\&= (\frac{(1+ \sqrt5)}{2} - \frac{(1 - \sqrt 5)}{2}) / \sqrt 5
\&= \sqrt5 / \sqrt 5
\&= 1
\end{aligned}
$$
等式成立。
设当 $n = k$ 时， $Fib(k) = (\phi^k - \psi^k) / \sqrt 5$ 成立。
当 $ n = k + 1$ 时
$$
\begin{aligned}
&Fib(k+1)
\=& Fib(k) + Fib(k - 1)
\=& (\phi^k - \psi^k) / \sqrt{5} + (\phi^{k-1} - \psi^{k-1}) / \sqrt 5
\=& \frac{(\phi^k+\phi^{k-1}) - (\psi^k + \psi^{k-1})} {\sqrt 5}
\=& \frac{\phi^{k+1}(\phi^{-1} + \phi^{-2}) - \psi^{k+1}(\psi^{-1} + \psi^{-2})}{\sqrt 5}
\=& \cfrac{\phi^{k+1}\cfrac{(\phi + 1)}{ \phi^2} - \psi^{k+1}\cfrac{(\psi+1)}{\psi^2}}{\sqrt 5}
\=& \cfrac{\phi^{k+1}\cfrac{\cfrac{1+\sqrt 5}{2} + 1}{(\cfrac{1+\sqrt5}{2})^2} - \psi^{k+1}\cfrac{\cfrac{1 - \sqrt5}{2} + 1}{(\cfrac{1-\sqrt5}{2})^2}}{\sqrt 5}
\=& \cfrac{\phi^{k+1}\cfrac{\cfrac{3+\sqrt 5}{2}}{\cfrac{3+\sqrt 5}{2}} - \psi^{k+1}\cfrac{\cfrac{3-\sqrt 5}{2}}{\cfrac{3-\sqrt 5}{2}}}{\sqrt 5}
\=& \cfrac{\phi^{k+1} - \psi^{k+1}}{\sqrt 5}
\end{aligned}
$$
证毕。
接着证明 $Fib(n)$ 是最接近 $\phi^n/\sqrt 5$ 的整数。
若要证明 $Fib(n)$ 是最接近 $\phi^n/\sqrt 5$ 的整数，
只需要证明 $|Fib(n) - \phi^n/\sqrt 5| < 1$
根据上面的结论有
$$
\begin{aligned}
\left|Fib(n) - \frac{\phi^n}{\sqrt 5}\right| &= \left|\frac{\phi^n - \psi^n}{\sqrt 5} - \frac{\phi^n}{\sqrt 5}\right|
\&= \left|-\frac{\psi^n}{\sqrt 5}\right|
\&= \frac{|\psi^n|}{\sqrt5}
\&< \frac{1}{\sqrt 5} \left(\because 0 < \left|\frac{1 - \sqrt 5}{2}\right| < 1 \right)
\&< 1
\end{aligned}
$$
证毕。
习题 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?
先看程序是怎么执行的。
1 | c 11 5 |
接着求时间复杂度和空间复杂度。
空间复杂度是树的最大深度。显然对于换硬币问题，嵌套最深的情况是全部都以最小的零钱兑换。也就是深度是 $change \div 1 = change$ 。所以空间复杂度是 $\Theta(change)$ 或者说 $\Theta(n)$ 。
时间复杂度是树的子节点个数。
没算出来= =
习题 1.15
Exercise 1.15. The sine of an angle (specified in radians) can be computed by making use of the approximation $\sin x \approx x$ if x is sufficiently small, and the trigonometric identity
$$
\sin x = 3 \sin \frac{x}{3} - 4\sin^3 \frac{x}{3}
$$
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:
1 | (define (cube x) (* x x x)) |
a. How many times is the procedure
papplied 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?
执行过程
1 | (sine 12.15) |
最后迭代到 (p (p (p (p (p (sine 0.0555556)))))) 所以问题 a 的答案是 p 一共被调用了 5 次。
空间复杂度等于树的深度，在这里等于 p 的调用次数 $x$，根据题意有
$$
\begin{aligned}
&angle \div 3^x < 0.1
\& angle < 0.1 \times 3^x
\& 10angle < 3^x
\& \log_3{10angle} < x
\end{aligned}
$$
所以空间复杂度为 $\Theta(\log_3{angle})$ 或者说 $\Theta(\log{n})$
时间复杂度等于树的节点数，在这里也等于 p 的调用次数，所以时间复杂度为 $\Theta(\log{n})$ 。
习题 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 $ab^n$ 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.)
题目的提示已经说得很清楚了。按照题目的思路做就可以了。题目思路如下
除了底 $b$，幂 $n$ 还需要一个变量 $a$ 来记录累积的值，在迭代中保持 $ab^n$ 不变。也就是
当 $n = 0$ 时，结果为 $ab^n$
当 $n$ 是偶数时 ， $b^n = (b^2)^{n/2}$ ， a 不变 。 此时 $ab^n = a(b^2)^{n/2}$ ，转化为求 $\frac{n}{2}$ 次方。
当 $n$ 是奇数时，$b^n = b \cdot b^{(n-1)}$ ，$ a \leftarrow a \cdot b$ ，此时 $ab^n = b \cdot b^{n-1}$ ，转化为求 $n-1$ 次方
写成代码是
1 | (define (square x) (* x x)) |
测试
1 | (fast-expt 2 1) |
这种找出恒等关系的做法很常用。
习题 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:
1 | (define (* a b) |
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, andhalve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous tofast-exptthat uses a logarithmic number of steps.
按照题目原有的思路 $ a $ 一直变大，$b$ 一直变小直到 $0$ 为止。不过 $a$ 变大使用 double ，$b$ 变小使用 halve 。
还需要考虑 $ b$ 的奇偶性。
当 $b$ 是偶数时，$a \cdot b = double(a) \cdot halve(b)$ 。
当 $b$ 是奇数时，$a \cdot b = a + a \cdot ( b -1)$ 。
写成代码是
1 | (define (* a b) |
习题 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
将上题改成迭代式的。需要多一个变量记录累积值。
1 | (define (mul-iter a b acc) |
习题 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-iterprocess of section 1.2.2: $ a \leftarrow a + b$ and $b \leftarrow 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 $T^n$, the $n$th 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 $T_{pq}$, where $T_{pq}$ transforms the pair $(a,b)$ according to $a \leftarrow bq + aq + ap$ and $b \leftarrow bp + aq$ . Show that if we apply such a transformation $T_{pq}$ twice, the effect is the same as using a single transformation $T_{p^{,}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 $T^n$ 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
1 | (define (fib n) |
不得不说这个算法真的很机智。线性迭代很容易想到矩阵变换，多次变化相当于矩阵的幂，通过矩阵乘法的结合律就能一次把整个变换矩阵算出来，最后应用到 $a$ ，$b$ 的初始值就可以算出最终的值。
用迭代法计算 $Fib(n) = b_n$ 是这样的。
有一对$(a,b)$ 的初始值$(a_0,b_0)$ ，那么 $(a_1,b_1)$ 是这么得来的
$$
\begin{aligned}
&a_1 \leftarrow 1a_0 + 1b_0 \
&b_1 \leftarrow 1a_0 + 0b_0
\end{aligned}
$$
用矩阵表示就是
$$
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}
\times
\begin{bmatrix}
a_0\b_0
\end{bmatrix}
=
\begin{bmatrix}
a_1\b_1
\end{bmatrix}
$$
可以发现只要乘上左边的矩阵 $T = \begin{bmatrix}1 & 1\1 & 0\end{bmatrix}$ 就可以得到下一对 $(a,b)$
要求 $Fib(2)$ 的值由 $Fib(n) = b_n$ 得知只需要求 $b_2$
由 $b_0$ 到 $b_2$ 需要做两次变换，也就是
$$
\begin{aligned}
\begin{bmatrix}
a_2\b_2
\end{bmatrix}
&=
\begin{bmatrix}
1 & 1\
1 & 0
\end{bmatrix}
\times
\begin{bmatrix}
a_1\b_1
\end{bmatrix}
\&=
\begin{bmatrix}
1 & 1\
1 & 0
\end{bmatrix}^2
\times
\begin{bmatrix}
a_0\b_0
\end{bmatrix}
\&=
\begin{bmatrix}
2 & 1\
1 & 1
\end{bmatrix}
\times
\begin{bmatrix}
a_0\b_0
\end{bmatrix}
\end{aligned}
$$
由矩阵的定义得 $b_2 = 1a_0 + 1b_0 = a_0 + b_0$ 。
在迭代法开始时 $a = 1,b=0$ 也就是 $a_0 = 1,b_0 = 0$
所以 $Fib(2) = b_2 = a_0 + b_0 = 1 + 0 = 1$ 。与其他方式计算的结果相同。
回到题目中机智的算法，它其实是这样的
当 $ n $ 是偶数时，$Fib(n) = T^n b_0 = (T^2)^{n/2} b_0$ 。
当 $n$ 是奇数时，$Fib(n) = T \cdot T^{n-1} b_0$
题目源代码丢失的部分是求偶数条件下 $p$ 和 $q$ 的值。
题目给出的 $(a,b)$ 递推式是
$$
\begin{aligned}
&a_1 \leftarrow (p+q)a_0 + qb_0 \
&b_1 \leftarrow qa_0 + pb_0
\end{aligned}
$$
用矩阵表示是
$$
\begin{bmatrix}
p+q & q\
q & p
\end{bmatrix}
\times
\begin{bmatrix}
a_0\b_0
\end{bmatrix}
=
\begin{bmatrix}
a_1\b_1
\end{bmatrix}
$$
所以变换矩阵 $T = \begin{bmatrix}p+q & q\q & p\end{bmatrix}$ ，那么
$$
\begin{aligned}
T^2 &= T \cdot T
\&=
\begin{bmatrix}
p+q & q\
q & p
\end{bmatrix}
\times
\begin{bmatrix}
p+q & q\
q & p
\end{bmatrix}
\&=
\begin{bmatrix}
(p+q)^2 + q^2 & q(p+q) + qp\
q(p+q)+pq & q^2 + p^2
\end{bmatrix}
\end{aligned}
$$
对比 $T$ 和 $T^2$ 得
$$
\begin{aligned}
p &\leftarrow q^2 + p^2\
q &\leftarrow q(p+q) + pq
\end{aligned}
$$
所以最后答案是
1 | (define (fib-iter a b p q count) |
测试
1 | (fib 3) |
习题 1.20
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 ifis 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 remainderoperations are actually performed in the normal-order evaluation of(gcd 206 40)? In the applicative-order evaluation?
求 normal-order 和 applicative-order 中的 remainder 调用次数。if 语句先执行判断语句，后执行条件分支。
按 normal-order 展开
1 | (gcd 206 40) |
按 applicative-order 展开
1 | (gcd 206 40) |
所以答案是 normal-order 18 次 ，applicative-order 4 次。
习题 1.21
Exercise 1.21. Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.
用 smallest-divisor 求 199，1999，19999 的最小约数
求值
1 | (smallest-divisor 199) |
习题 1.22
Exercise 1.22. Most Lisp implementations include a primitive called
runtimethat returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The followingtimed-prime-testprocedure, 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.
1 | (define (timed-prime-test n) |
Using this procedure, write a procedure
search-for-primesthat 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 $\Theta(\sqrt n)$ , you should expect that testing for primes around $10,000$ should take about $\sqrt {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 $\sqrt 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?
编写一个查找一定区间所有奇数中的函数 search-for-prime
1 | (define (search-for-prime begin end) |
测试发现现在机器速度太快了。所以前后 runtime 差值太小总是 0 。所以改为计算总的时间。从Machine-Time得知尝试了几种不同的计时方式。发现 real-time-clock 效果较好。
1 | (define (time-for n start-time) |
测试
1 | 1 ]=> (search 100000) |
每次 search n 的计算次数为单次计算次数乘上1000 。结果为 $1000\sqrt n = \Theta(\sqrt n)$ 。
所以如果 (search 1000000) 耗时为 202 ，
那么 (search 10000000) 应该等于
$\Theta(\sqrt {10^8}) = \Theta(\sqrt {10} \cdot \sqrt {10^7}) $
$= \sqrt {10} * 202 \approx 638$ 。
但从上面看出实际结果是 344
习题 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?
找最小约数的时候考虑了除了 2 以外的偶数，做了多余的工作。所以编写函数 next 返回下一个奇数。
1 | (define (next x) |
相应的修改find-divisor 中的 (+ test-divisor 1) 为 (next test-divisor)
1 | (define (smallest-divisor n) |
测试时间
1 | (search 100000) |
$10^6$ 的时间为之前的 1.6 倍，而 $10^7$ 为之前的 1.1 倍。
习题 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 $\Theta(\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?
将 prime? 改为 fast-prime?
1 | (define (timed-prime-test n) |
$1000$ 太小了。分别选择 $10^5$ ，$10^6$ 和 $10^7$ 附近的质数进行测试
1 | (timed-prime-test 100003) |
$10^6$ 的复杂度是
$\Theta(\log_2{10^6}) = \Theta(\log_2{10^5 \cdot 10})$
$= \Theta(\log_2{10}) + \Theta(\log_2{10^5})$
$\Theta(\log_2{10^5}) $ 也就是 $10^5$ 的时间 $63$
所以 $\Theta(\log_2{10}) = \Theta(\log_2{10^6}) - \Theta(\log_2{10^5}) $
$= 78 - 63 = 15$ 。
类似地，$\Theta(\log_2{10^7}) = \Theta(\log_2{10^6}) + \Theta(\log_2{10}) $
$= 78 + 15 = 93$ 。
跟实际时间 $94$ 非常接近。
习题 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
1 | (define (expmod base exp m) |
Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
看起来没有什么问题。随便测试了几个也没问题。既然是用了不同的方式，肯定有区别。
先看原来的求值过程
1 | (expmod 5 2 4) |
对比本题中的 (expmod 5 2 4) = (remainder 25 4)
发现书中的不是直接求余，而是先把数字减小后求余。这样的好处是当防止在数字比较大的情况下整数溢出。
习题 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 hisprime?test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis’s code, they find that he has rewritten theexpmodprocedure to use an explicit multiplication, rather than callingsquare:
1 | (define (expmod base exp 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 $\Theta(\log n)$ process into a $\Theta(n)$ process.’’ Explain.
这种情形有点类似 applicative-order 和 normal-order 的区别。
例如 (square (+ 1 1)) 和 (* (+ 1 1) (+ 1 1)) 计算过程
1 | (square (+ 1 1)) |
所以不用 square 的情况下会多计算一次。
如果像题目中这种需要计算的式子是递归的，那么相当于每次都多计算了一次。
原来只需要计算 $\log_2{n}$ 次。
现在需要每次都计算两次。求值展开的形状相当于二叉树，叶子数量就是计算次数。
叶子数量等于 2 的树高次方。树高为 $\log_2{n}$ 。所以叶子数量为 $2^h = 2^{\log_2{n}} = n$ 。
所以复杂度为 $\Theta(n)$ 。
习题 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.
编写函数对 $n$ 用所有小于 $n$ 的数进行费马测试。
首先编写一次费马测试的函数。
1 | (define (one-fermat-test n a) |
其次编写对所有小于 $n$ 的数进行费马测试的函数 (test n a)
当 $ a \le 2$ 时，无论 $n$ 是多少直接通过费马测验。
当 $ a > 2$ 时，$test (n,a) = one-fermat-test(n,a) \wedge test(n,a-1)$
写成代码
1 | (define (test-all n a) |
费马测试
1 | (define (fermat-test n) |
测试
1 | (fermat-test 3) |
果然 561 和 1105 把费马测试给耍了。
习题 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
expmodprocedure. However, whenever we perform the squaring step inexpmod, 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 theexpmodprocedure 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 makeexpmodsignal is to have it return 0.
如果米勒测试的非平凡平方根 $number \in (1,n-1)$ ，那么对于非素数的奇数 $9$ 有
$2^2 \equiv 4 \pmod {9} $
$3^2 \equiv 0 \pmod 9$
$4^2 \equiv 7 \pmod 9$
$5^2 \equiv 7 \pmod 9$
$6^2 \equiv 0 \pmod 9$
$7^2 \equiv 4 \pmod 9$
显然没有任何一个数满足 $ number^2 \equiv 1 \pmod 9$ 。但是题目中说到对于非素数的奇数至少有一半小于 $n$ 的数 $a$ 在计算$a^{n-1} \bmod n$ 的过程中可以找到非平凡平方根。
那么把条件改为非平凡平方根不一定小于 $n$ ，那么对于质数 $13$ 在计算 $10^{12} \bmod 13$ 过程中发现
$10^6 = (10^3)^2 \equiv 1 \pmod {13}$
也就是存在非平凡平方根 $10^3$ ，使得 $13$ 没有通过米勒测试。但是 $13$ 是质数。
后来找 Miller-Rabin 测试的相关资料。发现了一篇文章。恍然大悟。原来是计算过程不是这样的。觉得写不出更好的。所以答案请看这篇文章。
总结
这一小节主要讲述了解决问题的两种方式，递归和迭代。分别介绍了它们的特点。同时引入算法复杂度的衡量方法，目的是为了督促读者写出更好的解决方法。
这一小节有不少习题还挺难的。花了很多时间才多完。自以为编程老司机结果才第二小节就翻车了（逃