SICP 习题 1.7

Exercise 1.7.  The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers,arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess.Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

练习 1.7. 在计算平方根时使用的足够好的测试对于找到非常小的数字的平方根来说不是非常有效的。此外，在实际计算机中，算术运算几乎总是以有限精度进行。这使得我们的测试对于非常大的数字来说是不够的。请解释这些陈述，并给出小和大数字的测试失败的示例。实现足够好的测试的另一种策略是观察猜测如何从一次迭代到下一次迭代，并在变化是猜测的非常小的分数时停止。设计一个平方根过程，该过程使用这种最终测试。这对于小和大数字来说是否更好？

对非常小的数字

考虑尝试求解 √(0.0000001)：

• 当前测试认为猜测足够好，如果 |(猜测²) - x| < 0.001

0.001 实际上远大于 0.0000001，所以我们接受的猜测相对于输入的数字可能非常不准确。

对非常大的数字

有限精度算术意味着大数中的微小相对误差可能会变得大于我们 0.001 的阈值。

例如，对于 √(10⁹⁰)，乘法中的小舍入误差可能导致测试永远无法成功

改进方法

(define (sqrt-iter-new guess prev-guess x)
  (if (good-enough-new? guess prev-guess)
      guess
      (sqrt-iter-new (improve guess x)
                     guess
                     x)))

(define (good-enough-new? guess prev-guess)
  (< (abs (/ (- guess prev-guess) guess)) 0.000001))

(define (sqrt-new x)
  (sqrt-iter-new 1.0 0.0 x))

其中：

• 而不是检查 |(guess²) - x| < 0.001，我们现在检查 |guess - previous_guess|/|guess| < 0.000001
• 我们追踪当前的猜测和之前的猜测
• 相对变化阈值（0.000001 或 0.0001%）与猜测的大小成比例。

附：程序

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
		 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (square x)
  (* x x))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(displayln (sqrt 9))
(displayln (sqrt (+ 100 37)))
(displayln (square (sqrt 1000)))

本文作者：Maeiee

本文链接：SICP 习题 1.7

版权声明：如无特别声明，本文即为原创文章，版权归 Maeiee 所有，未经允许不得转载！

喜欢我文章的朋友请随缘打赏，鼓励我创作更多更好的作品！