Exercise1-6 <---> Exercise1-8
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?
Ru: Проверка good-enough?, которую мы использовали для вычисления квадратных корней, будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел. Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативный подход к реализации good-enough? состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение. Верно ли, что на больших и маленьких числах она работает лучше?
Scheme solution:
(define (square x)
(* x x))
(define (good-enough? guess x)
(< (abs (/ (- (square guess) x) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
Haskell solution:
sqrt'iter guess x | abs ((guess * guess - x) / x) < 0.001 = guess
| otherwise = sqrt'iter ((guess + x / guess) / 2) x
OCaml solution:
let rec sqrt_iter guess x =
if abs_float ((guess *. guess -. x) /. x) < 0.001 then
guess
else
sqrt_iter ((guess +. x /. guess) /. 2.) x
Oberon/Component Pascal solution:
PROCEDURE SqrtIter (guess, x : REAL) : REAL;
VAR g : REAL;
BEGIN
g := guess;
WHILE ABS(g*g - x)/x > 0.001 DO
g := (g + (x/g))/2
END;
RETURN g
END SqrtIter;
Exercise1-6 <---> Exercise1-8
Comments
| Проще каждый раз таскать с собой предыдущий вариант, чем каждый раз его вычислять (define (sqrt-iter guess pre-guess x) (if (good-enough? guess pre-guess) guess (sqrt-iter (improve guess x) guess x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess pre-guess) (< (abs (- guess pre-guess)) 0.01)) (define (sqrt x) (sqrt-iter 1.0 0 x)) | ||||
| Posted by stassats at 2007-09-28 02:44:04 X | ||||
| Да, и тем более, что у нас же тут плавающая точка, так что число, если его заново вычислять, не всегда будет такое. | ||||
| Posted by stassats at 2007-09-28 02:52:36 X | ||||
| BTW, stassats, you can use this wiki-markup to enable syntax-highlighting in comments (just remove spaces between curly braces): { { { #!code scheme (define (scheme-code here)) } } } | ||||
| Posted by IvanVeselov at 2007-09-29 20:26:35 | ||||
The solution posted here is incorrect. You must watch how the *guess* changes, and you are done when the change is a small fraction of the *guess* itself. The posted solution is looking at the difference between the square of the guess and x, and then taking that as a fraction of x. stassats solution is closer, as he uses guess and pre-guess. This is the right strategy. However, the problem states that you must "stop when the change is a very small fraction of the guess." This means that good-enough should look like this: (define (good-enuff? guess last-guess)
Also, I'm not sure if this is necessary, but for the startup function sqrt, you could do the following, which is probably safer than assuming you can use 0 as the pre-guess: (define (square-root x)
| ||||
| Posted by bi01p1 at 2008-09-12 01:32:39 X | ||||
Just an addition, the smaller the change between two guesses to be detected, the more accurate the result of the square root operation is. Try with different values of change difference to stop guessing, such as, 0.001, 0.00001, and so on. Compare the operation results with those produced using the built-in sqrt. | ||||
| Posted by 70-57-97-53 at 2008-12-19 00:08:45 X | ||||
Solution is a pure mathematics. We have guess1, guess2,guess3, .... E.g. take a=guess1 and b=guess2 guess2=x/guess1 or b=x/a guess2 - guess1=b-a b-a=x/a - a a=x/b After replace a with x/b have: b-a=(b*b-x)/b So have be: (define (good-enough? guess x)
| ||||
| Posted by 83 at 2009-09-25 14:44:34 X | ||||