Exercise 1.45
We saw in Section 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-dampedy 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/y3 converge. On the other hand, if we average damp twice (., use the average damp of the average damp of y->x/y3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth 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 nth roots using fixed-point, average-damp,and the repeated procedure of Exercise1.43. Assume that any arithmetic operations you need are available as primitives.
This question was so difficult that I ended up not being able to do it on my own. One is how to find how many times to perform average-damp, I thought it was n-2 at first, tried a few and found that it was obviously not, and then guessed whether it was n/2, the result is still not right, finally searched the Internet to realize that it is log 2(n), interested in can refer to the Zhihu'sThis answer.I knew the number of times to repeat the execution, and again ran into problems when writing the code. I still didn't understand the concept of "using a procedure as the return value of another procedure" well, and I didn't understand it.
(repeated average-damp n)After that, you have to pass it a procedure as a parameter to average-damp, and I finally googled someone else's answer to figure it out. Here is my answer:
; look for x cap (a poem) f(x) average value
(define (average-damp f)
(lambda (x) (average x (f x))))
; For any positive integer n，look for使得 2^k < n maximum k (be) worth
(define (max-expt n)
(define (iter k pre)
(if (< n pre)
(- k 1)
(iter (+ k 1) (* 2 pre))))
(iter 1 2))
(define (nth-root x n)
(fixed-point ((repeated average-damp (max-expt n))
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
(display (nth-root 2 2))
(newline)
(display (nth-root 32 5))
(newline)
; in the end
1.4142135623746899
2.000001512995761