4
$\begingroup$

I am studying Abelson and Sussman's Structure and Interpretation of Computer Programs, 2/e. I solved the exercise 1.7, which asks for a better stopping criteria for an iterative function to calculate the square root function, and then checked my solution against one that I found on this site: http://community.schemewiki.org/?sicp-ex-1.7

The original function iterated until $|\mathtt{guess}^2 - \mathtt{x}| < 0.001$, but the book points out that something better is needed because this does poorly both for very large and for very small x.

The solution on schemewiki.org iterates until $|\mathtt{improve(guess, x)-\mathtt{guess}}| < .001\; \mathtt{guess}$, following the book's suggestion of watching "how guess changes from one iteration to the next and stopping when the change is a very small fraction of the guess." (The improve function takes a guess and x and generates a better guess by averaging the guess with x/guess.)

While I instictively went for a precision relative to the magnitude of the radicand. $|\mathtt{guess}^2-x| < 0.001\;\mathtt{x}$.

Both functions seem to yield similar results. Mine seems more obvious and efficient to me. Maybe too obvious... I suppose there is something I missed ?

$\endgroup$
2
  • $\begingroup$ Why do you think your version "seems more obvious and efficient"? It does seem to require an answer twice as precise, i.e. 0.0005 guess, though I did not check how the precision improves on each iteration. $\endgroup$ – babou Apr 6 '15 at 9:46
  • $\begingroup$ I said "more efficient" because it doesn't call "improve". It really bothers me to call "improve" just to do this test. For all iterations but the last one, it's doing the same work twice. Ok, it can easily be avoided with an "oldguess" variable like shown in the second solution provided on schemewiki. But I still don't like having to boot the recursive procedure with a dummy value for oldguess. I say it's more "obvious" because it doesn't introduce any new elements. But I'm not sure I follow you on " It does require an answer twice as precise", could you help me picture this? $\endgroup$ – Yugo Amaryl Apr 6 '15 at 10:04
3
$\begingroup$

I did not check the code used in Abelson and Sussman's book or wiki. My guess is that the recursive (or iterative) procedure will somehow organize to compute improve(guess,x) only once. In a recursive procedure, you just compare the formal parameter which is the previous guess with the actual value (current guess) that you would pass for a recursive call, in order to decide whether actually do the call rather than return it. There may be a difference of one (wasted) iteration depending on how you do the test.

Regarding the fact that you do the test on $x$ or on $\sqrt x$, or rather $\mathtt{guess}^2$ or $\mathtt{guess}$, that does not give you the same precison if you look for the same difference.

One way of explaining it is that $|\mathtt{guess}^2-x|= |\mathtt{guess}^2-{\sqrt x}^2| = |\mathtt{guess}-\sqrt x|(\mathtt{guess}+\sqrt x)$
since the second factor has to be positive (at least when relative imprecision gets small).

Since $\mathtt{guess}$ is supposed to be very close to $\sqrt x$, we know that $\mathtt{guess}+\sqrt x$ is very close to $2\sqrt x$ or $2\;\mathtt{guess}$.

Hence $|\mathtt{guess}^2-x|$ is close to $2\sqrt x\;(\mathtt{guess}-\sqrt x)$, so that the condition $|\mathtt{guess}^2-x| < 0.001\;x$ can be replaced by $2\sqrt x\;|\mathtt{guess}-\sqrt x| < 0.001\;x$, i.e.
$|\mathtt{guess}-\sqrt x| < 0.0005\sqrt x$ or, still using the same approximation:
$|\mathtt{guess}-\sqrt x| < 0.0005\;\mathtt{guess}$

This can be further formalized, but the above informal reasonning gives you the idea.

However, I did not check how fast this conputation is converging, and what is the difference between $|\mathtt{improve(guess, x)-\mathtt{guess}}|\;$ and $|\mathtt{guess}-\sqrt x|$, i.e. how fast one gets closer to the exact answer with each new iteration (assuming the precision of the arithmetics is still good). Their ratio should also be accounted for. It depends on the formula used for computing the approximation, which I did not look at.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.