Exercise 1.45: We saw in 1.3.3
that attempting to compute square roots by naively finding a fixed point of
y
↦
x
/
y does not converge, and that this can be fixed by average
damping. The same method works for finding cube roots as fixed points of the
average-damped y
↦
x
/
y
2. Unfortunately, the process does not
work for fourth roots—a single average damp is not enough to make a
fixed-point search for y
↦
x
/
y
3 converge. On the other hand, if
we average damp twice (i.e., use the average damp of the average damp of
y
↦
x
/
y
3) the fixed-point search does converge. Do some experiments
to determine how many average damps are required to compute n
th roots as a
fixed-point search based upon repeated average damping of y
↦
x
/
y
n
−
1.
Use this to implement a simple procedure for computing
n
th roots using fixed-point, average-damp, and the
repeated procedure of Exercise 1.43. Assume that any arithmetic
operations you need are available as primitives.
练习 1.45：我们在 1.3.3 节看到，通过朴素地求 y ↦ x/y 的不动点来计算平方根并不收敛，而通过平均阻尼 (average damping) 可以解决这个问题。同样的方法也适用于将立方根求解为平均阻尼后的 y ↦ x/y² 的不动点。遗憾的是，这一方法对四次方根不奏效——单次平均阻尼不足以使 y ↦ x/y³ 的不动点搜索收敛。另一方面，若进行两次平均阻尼（即对 y ↦ x/y³ 的平均阻尼再做一次平均阻尼），不动点搜索确实能收敛。做一些实验，确定计算 n 次方根时，基于对 y ↦ x/yⁿ⁻¹ 反复平均阻尼进行不动点搜索，需要多少次平均阻尼。利用这一结果，结合 fixed-point、average-damp 和练习 1.43 中的 repeated 过程，实现一个计算 n 次方根的简单过程。假设你所需的任何算术运算都作为基本过程可用。