Question

Maybe you have tried to hit the square root key on a calculator multiple times and then squared the number again an equal number of times. These set of inverse mathematical operations should of course bring you back to the starting value for the computations, but this does not always happen. To avoid tedious pressing of calculator keys we can let a computer automate the process. Here is an appropriate program: from math import sqrt for n in range(1, 60): r = 2.0 for i in range(n): r = sqrt(r) for i in range(n): r = r**2 print ’%d times sqrt and **2: %.16f’ % (n, r) Explain with words what the program does. Then run the program. Round-off errors are here completely destroying the calculations when $\mathrm{n}$ is large enough! Investigate the case when we come back to 1 instead of 2 by fixing the $\mathrm{n}$ value and printing out $\mathrm{r}$ in both for loops over i. Can you now explain why we come back to 1 and not 2 ? Name of program file: repeated_sqrt.py.

Short answer

Due to round-off errors and 1 being a stable fixed point under square and square root operations, the program sometimes returns 1 instead of 2 for large 'n'.

Step-by-step solution

Understanding the Program

The program performs a series of mathematical operations on a starting value of 2.0. It calculates the square root of the value 'r' repeatedly 'n' times, and then calculates the square of 'r' the same number of times. These operations are supposed to reverse each other, ideally bringing the number back to the starting value of 2.0. The program iterates this process for values of 'n' from 1 to 59 and prints the final result of 'r' after all operations are performed.

Investigating Round-Off Errors

Theoretically, performing the square root and squaring operations an equal number of times should leave the number unchanged. However, due to the limitations of floating-point arithmetic in computers, round-off errors occur. These errors accumulate as the number of operations increases, especially when 'n' is large, leading to the result diverging from the expected value of 2.0.

Modification for Debugging

To investigate the phenomenon, modify the program to print the intermediate values of 'r' inside both 'for loops' by adding print statements. This helps observe how 'r' changes during each iteration of the square root and squaring operations to determine why the final result may end up as 1 instead of 2 when 'n' is large.

Understanding the Result Divergence

Upon running the modified program, observe that very small numerical differences from the true mathematical result occur because each square root and square operation introduces a small error. When 'n' is sufficiently large, these minute errors compound significantly. The repeating operations may force 'r' closer to 1, which is a stable fixed point for these operations, hence the result eventually stabilizes to 1 rather than returning to 2.

Conclusions about Fixed Points

The reason the result stabilizes at 1 instead of returning to 2 is due to 1 being a fixed point for both the square root and the squaring operations. Any small errors introduced by floating-point approximation in the operations around 1 get progressively reduced, reinforcing the convergence to 1 rather than 2 as 'n' increases.

Key concepts

Round-off Errors

Floating-point arithmetic, which computers use to represent real numbers, often results in round-off errors. These small discrepancies can occur because computers have a finite number of digits to represent numbers, leading to slight inaccuracies. When you perform arithmetic operations involving these numbers, such as repeatedly finding square roots and squaring a value, these tiny errors can accumulate.
Why do round-off errors matter? Over multiple iterations, especially in problems involving many operations, these errors grow. Taking repeated square roots and subsequently squaring them in a loop (as shown in the exercise) is a perfect situation to observe their effect. Ideally, repeatedly finding the square root and then squaring the same number should yield the initial number. However, due to round-off errors, the outcome diverges from expectations. When 'n' becomes large, round-off errors become significantly impactful, causing divergences like obtaining 1 instead of 2.

Debugging Programs with Print Statements

When faced with unexpected behavior in a program, such as not getting the expected result due to round-off errors, print statements can be invaluable. By inserting print statements into critical parts of the program, such as inside loops that perform mathematical operations, you can gain insights into how your variables change over time.
In the context of the exercise, modifying the program to print the value of 'r' within both loops sheds light on the round-off errors' effect at each step. By examining these intermediate values, you can see how 'r' gradually diverges from its expected path. Print statements are a straightforward yet powerful debugging tool, often used by programmers to track variable states or logic flow, especially when dealing with complex operations like floating-point arithmetic.

Fixed Points in Numerical Operations

In mathematics, a fixed point of a function is a value that is unchanged by the function. For the squaring function and its inverse, the square root, 1 is a significant fixed point. When handling floating-point arithmetic, especially with many iterations, tiny round-off errors can steer the result towards this fixed point.
This behavior is apparent in the exercise when repeated square root and squaring operations cause 'r' to stabilize at 1 instead of 2. Initially, minor deviations might just seem like minor errors. But, over many cycles, they compound until the result drifts towards the fixed point, which is 1 in this case. Recognizing fixed points helps explain why values converge and provides insight into the limitations of numerical methods, especially when using iteration and floating-point calculations together.