*Squaring* a number means multiplying it by itself, and is
denoted by a superscript 2.
For example, 2^{2} = 2×2 = 4, 3^{2} = 3×3
= 9, and 5^{2} = 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: 3^{3} = 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
*x*_{0} by a line passing through the point
(*x*_{0}, *f*(*x*_{0})) and
having the same slope as the graph of the function itself at that
point.
The graph of the function has the slope
*f*’(*x*_{0}), the derivative of *f* at
*x*_{0}.
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 *x*_{0}, and is called
*x*_{1}.
The approximation by a line process is repeated at
*x*_{1}, yielding a better approximation
*x*_{2}, and so on.

The equation of the approximating line is:

Letting *x*_{i+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 *x*^{2}-*a* serves nicely: when
*x* is equal to the square root of *a*,
*x*^{2}-*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 *x*_{0}: for any positive
value *a*, there will come a time when successive
*x*_{i} 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
*x*_{i} 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 *x*_{0} to be
(*a*+1)/2?
(Hint: If it initialized *x*_{0} to be 1, what
would the first value of *x*_{1} be?)
In your estimation, is it worth modifying the algorithm to initialize
*x*_{0} 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 *x*_{1} to
*x*_{0}?
Explain your answer in terms of *x*_{i} and
*x*_{i+1}.
What names for the variables in the algorithm would be more
descriptive of their function than *x*_{0} and
*x*_{1}?

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.

In JavaScript, the function Math.abs(x) computes the absolute value of the value x. In Visual Basic for Applications, the function Abs(x) computes the absolute value of the value x. In the calculator, the operator Abs (OPTN F6 [next] F4 [NUM] F1 [ABS] on the 9850, OPTN next F1 [NUM] F1 [ABS] on the 7400) x computes the absolute value of the value x.

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.

In JavaScript, the function Math.sqrt(x) computes the square root of
the value x.
In Visual Basic for Applications, the function sqr(x) computes the
square root of the value x.
In the calculator, the operator √ (SHIFT *x*^{2})
*x* computes the square root of the value x.

Try the following extreme values for a using the program you wrote in
part 3: 1×10^{-99}, 1×10^{-50},
1×10^{50}, 9.999999999×10^{99}, 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×10^{25}, approximately 1×10^{50}, 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?

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 30 December 2001.

Tutorial

Building Blocks I

Control Flow II

Basic I/O

Algorithms

A First Program

Exercises

Square Roots

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card