Question

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? \({ }^{24}\) Readers who are worried about the efficiency issues involved in using procedure calls to implement iteration should note the remarks on "tail recursion" in section 1.2.1.

Short answer

The new square root method improves accuracy for small and large numbers by focusing on iterative guess changes rather than squared value comparisons.

Step-by-step solution

Understanding the Good-enough? Test

The 'good-enough? test' checks if a square root guess is sufficiently accurate by comparing the square of the guess to the original number. It works well for numbers close to 1, but for very small numbers, the difference between the square of the guess and the original number remains large, making the guess seem never 'good-enough'. For large numbers, floating-point precision limits can make the squared value differ only slightly, even for inadequate guesses.

Example of Failure for Small Numbers

Consider finding the square root of 0.0001. A guess of 0.1 gives 0.01 when squared, which is much larger than 0.0001, hence the test would continue indicating the guess is not 'good-enough'. This makes convergence slow and inefficient.

Example of Failure for Large Numbers

Trying to find the square root of 1,000,000 using a similar method can result in guesses that are close to each other due to precision limits, but do not actually square to the number, leading the test to fail in recognizing this precision limitation.

Designing a New Testing Strategy

A new approach involves checking how much the guess changes with each iteration. If the change between successive guesses is smaller than a threshold (like 0.0001 times the guess), we can consider the approximation 'good-enough'. This strategy focuses on measuring relative improvements in the guess.

Implementing the Square Root Procedure

We define a procedure to compute square roots using our new termination test. Starting with a guess (e.g., half the number or 1.0), we update the guess using \[ ext{new\_guess} = rac{ ext{guess} + rac{ ext{number}}{ ext{guess}}}{2} \]and check if \[ rac{| ext{new\_guess} - ext{guess} |}{ ext{new\_guess}} < ext{threshold} \]. Iterations continue until this condition is true.

Testing with Small and Large Numbers

Using this method for 0.0001, the guess rapidly converges as we are more focused on the relative change rather than the absolute difference, which handles precision issues effectively. Applying it to 1,000,000, the method also quickly finds the root as relative convergence is observed, showing improved performance over the traditional good-enough? test.

Conclusion: Benefits of the New Method

The new method improved convergence and accuracy for both small and large numbers by emphasizing the change in successive approximations, circumventing the challenges of the initial good-enough? test.

Key concepts

Floating-point Precision

Floating-point precision refers to how accurately numbers with decimal points are represented within a computer. Computers represent numbers in a finite way, meaning there are limitations on how precisely they can store very large or very small numbers. This limitation can cause significant issues in calculations like finding square roots.
When computing the square root using the 'good-enough?' test, we can encounter errors due to floating-point precision limits. For very small numbers, such as 0.0001, even a good guess seems inaccurate because the precision is not sufficient to recognize the small value accurately when squared. Conversely, for large numbers like 1,000,000, the precision might not be enough to differentiate between guesses that are inaccurately close, failing to improve the approximation.

• Floating-point represents numbers with a finite precision.
• It can cause rounding errors, especially with very large or small numbers.
• Precision issues often affect calculations that require iterative approximations like square root finding.

To mitigate these effects, it's crucial to employ strategies that are less dependent on absolute precision and more on relative changes.

Iteration Strategy

An effective iteration strategy is critical when aiming to calculate accurate results through repeated approximations. In the problem of computing square roots, the traditional 'good-enough?' test might not be the best approach. Instead, observing changes between successive guesses is more reliable.
The new strategy involves checking how much each guess improves from the previous one. This is done by comparing the relative difference: if the change between successive guesses becomes a very small fraction of the guess itself, it's considered good enough. This method emphasizes improvements between iterations instead of just matching the result with an expected value.

• Focuses on relative changes across iterations.
• Ensures that the process adapts to the scale of the number.
• Especially useful for numbers with precision limitations.

This approach allows for better handling of both small and large numbers, as it effectively accommodates their different demands on precision.

Algorithm Efficiency

Algorithm efficiency concerns how quickly and effectively a numerical method can reach the desired result. In numerical problems, like finding square roots, efficiency relates to the speed of convergence - how fast the method can achieve a reliable estimate.
The new end test that relies on relative changes offers an improvement in efficiency over the traditional 'good-enough?' test. By observing the percentage change between iterations, this method quickly leads to convergence without requiring excessive iterations, even when precision is compromised.

• Ensures rapid convergence by focusing on percentage improvement.
• Avoids unnecessary iterations that do not significantly improve precision.
• Enhances computational speed, especially with problematic precision cases.

Thus, adopting a relative improvement criterion significantly reduces the iterations needed, thereby efficiently reaching an adequate approximation of the square root.

Testing Strategies

Testing strategies are essential in verifying the correctness and reliability of numerical methods used in calculations. The revised approach to testing when computing square roots illustrates the importance of adaptable testing methods.
Traditional methods often fail under specific conditions due to their reliance on absolute accuracy. The improved strategy, which focuses on how much each iteration result deviates relatively, proves vital in handling diverse ranges of numbers. By settling on a small fraction as the adequacy metric, this method adapts to precision issues while maintaining accuracy and correctness.

• Emphasizes relative accuracy over absolute comparisons.
• Adapts to the precision constraints of different numbers.
• Helps ensure method reliability under varied conditions.

Properly implemented, these strategies not only validate the correctness but also enhance confidence in the numerical method's results, providing robust solutions to both small and large number calculations.