Squaring a number means multiplying it by itself, and is denoted by a superscript 2. For example, 22 = 2×2 = 4, 32 = 3×3 = 9, and 52 = 5×5 = 25. The square root of a number is a number which, when squared, results in the original number, and is denoted by a radical sign (√). For example, √25 = 5. Similarly, cubing a number means multiplying it by itself twice: 33 = 3×3×3 = 27, and the cube root of 27 is 3.
The square root of numbers which are not perfect squares can be computed approximately; for example, √2 is approximately 1.414213562. There is an algorithm similar to the long division algorithm that can be used to compute square roots. However, this algorithm is laborious.
A much faster procedure based on Newton’s method is frequently used to extract square roots on computers.
Newton’s method is a root-finding procedure: it finds places where a function f(x) is equal to zero. It approximates f(x) near a value x0 by a line passing through the point (x0, f(x0)) and having the same slope as the graph of the function itself at that point. The graph of the function has the slope f’(x0), the derivative of f at x0. The root of f(x) is approximated by the point at which this line has a root. This point is generally a better approximation to the root of the function than is x0, and is called x1. The approximation by a line process is repeated at x1, yielding a better approximation x2, and so on.
The equation of the approximating line is:
Letting xi+1 be the point where this is equal to zero, we have:
This works for any differentiable function f(x).
Now, suppose we want to compute the square root x of a value a. We need to define a function which has a zero when x is the square root of a. The function x2-a serves nicely: when x is equal to the square root of a, x2-a = (√a)2–a = a-a = 0. Applying Newton’s method, we have:
As it happens, this process converges for all positive a with any positive initial value x0: for any positive value a, there will come a time when successive xi values are arbitrarily close together, and they will be arbitrarily close to the actual value of the square root. We can detect this convergence by noting when successive xi values differ by only the amount we are willing for the answer to be wrong. Suppose we want the answer we get to be accurate to 10 digits: then we want
So the flowchart of the square root extraction process would be:
Why does this algorithm initialize x0 to be (a+1)/2? (Hint: If it initialized x0 to be 1, what would the first value of x1 be?) In your estimation, is it worth modifying the algorithm to initialize x0 to (a+1)/4 + a/(a+1)? Why or why not? If you cannot decide whether this modification is worthwhile, what further information would you need in order to be able to decide?
Why does this algorithm assign x1 to x0? Explain your answer in terms of xi and xi+1. What names for the variables in the algorithm would be more descriptive of their function than x0 and x1?
Flowcharts use separate boxes to indicate the sequencing of computations. Computations in the same box can be carried out in any order, but computations in different boxes must be carried out in the order in which the boxes appear. Can the process (rectangular) boxes in this flowchart be rearranged without changing the results? Why or why not? Is there a computation that can be moved to a different box without changing the results? Why or why not?
This algorithm uses a test in the middle of the loop to determine when the algorithm can exit the loop. Many programmers feel a test at the beginning or end of a loop is preferable to a test in the middle of the loop, and many programmers feel a test at the beginning of the loop is most preferable. Can the computations and test in the loop be rearranged to have the test at the end of the loop, without changing the results? How could the algorithm be restructured to use a test at the beginning of the loop?
Write an interface definition for a square root subroutine. Write a subroutine using the interface that computes the square root according to the flow chart above. Write a program that calls the square root function and displays the results for the values 1, 2, 3, 4, and 5.
Write a program to compare the square root subroutine you wrote in part 1 and the calculator’s or language’s square root built-in function. Have the program accept the value used as an argument to the routines from the user. Compare your routine and the calculator’s or language’s square root built-in function for the values 1, 2, 4, 10, and 100.
Try the following extreme values for a using the program you wrote in part 3: 1×10-99, 1×10-50, 1×1050, 9.999999999×1099, and 0. Does your square root subroutine work for all of these? (The actual square roots are approximately 3.16227766×10-50, 1×10-25, 1×1025, approximately 1×1050, and 0, respectively.) Is this an error in your implementation of the algorithm, an error in the algorithm itself, an error in problem analysis, an error in the problem statement, or an error in use? What can you do about it?
What happens if a is negative? What can you do about it?
Modify your program to extract cube roots instead of square roots. The relevant approximation is:
What should your initial value be? How does this program behave when presented with negative numbers? With zero?
Copyright © 2001 Brian Hetrick
Page last updated 30 December 2001.
Building Blocks I
Control Flow II
A First Program
Data Structures I
Building Blocks II
Data Structures II