With calculators as commonplace as watches, it’s usually no big deal to find the square root of a particular number should the need arise. But years ago, students were taught manual techniques that could be used to arrive at an approximation of the square root of a number. One such approximation method that lends itself most readily to solution by a computer is known as the Newton-Raphson Iteration Technique. In Program 8.8, you write a square root function that uses this technique to arrive at an approximation of the square root of a number.
The Newton-Raphson method can be easily described as follows.You begin by selecting a “guess” at the square root of the number. The closer that this guess is to the actual square root, the fewer the number of calculations that have to be performed to arrive at the square root. For the sake of argument, however, assume that you are not very good at guessing and, therefore, always make an initial guess of 1.
The number whose square root you want to obtain is divided by the initial guess and is then added to the value of guess. This intermediate result is then divided by 2. The result of this division becomes the new guess for another go-around with the formula. That is, the number whose square root you are calculating is divided by this new guess, added into this new guess, and then divided by 2. This result then becomes the new guess and another iteration is performed.
Because you don’t want to continue this iterative process forever, you need some way of knowing when to stop. Because the successive guesses that are derived by repeated evaluation of the formula get closer and closer to the true value of the square root, you can set a limit that you can use for deciding when to terminate the process. The differ- ence between the square of the guess and the number itself can then be compared against this limit—usually called epsilon (e). If the difference is less than e, the desired accuracy for the square root has been obtained and the iterative process can be terminated.
This procedure can be expressed in terms of an algorithm, as shown next.
Newton-Raphson Method to Compute the Square Root of x
Step 1: Set the value of guess to 1.
Step 2: If |guess2 – x| < ε, proceed to step 4.
Step 3: Set the value of guess to (x / guess + guess) / 2 and return to step 2.
Step 4: The guess is the approximation of the square root.
It is necessary to test the absolute difference of guess and x against e in step 2 because the value of guess can approach the square root of x from either side.
Now that you have an algorithm for finding the square root at your disposal, it once again becomes a relatively straightforward task to develop a function to calculate the square root. For the value of e in the following function, the value .00001 was arbitrarily chosen. See the example in Program 8.8.
Program 8.8 Calculating the Square Root of a Number
// Function to calculate the absolute value of a number
#include <stdio.h>
float absoluteValue (float x)
{
if ( x < 0 )
x = -x;
return (x);
}
// Function to compute the square root of a number
float squareRoot (float x)
{
const float epsilon = .00001;
float guess = 1.0;
while ( absoluteValue (guess * guess – x) >= epsilon )
guess = ( x / guess + guess ) / 2.0;
return guess;
}
int main (void)
{
printf (“squareRoot (2.0) = %f\n”, squareRoot (2.0));
printf (“squareRoot (144.0) = %f\n”, squareRoot (144.0));
printf (“squareRoot (17.5) = %f\n”, squareRoot (17.5));
return 0;
}
Program 8.8 Output
squareRoot (2.0) = 1.414216
squareRoot (144.0) = 12.000000
squareRoot (17.5) = 4.183300
The actual values that are displayed by running this program on your computer system might differ slightly in the less significant digits.
The preceding program requires a detailed analysis. The absoluteValue function is defined first. This is the same function that was used in Program 8.7.
Next, you find the squareRoot function. This function takes one argument called x and returns a value of type float. Inside the body of the function, two local variables called epsilon and guess are defined. The value of epsilon, which is used to determine when to end the iteration process, is set to .00001. The value of your guess at the square root of the number is initially set to 1.0. These initial values are assigned to these two variables each time that the function is called.
After the local variables have been declared, a while loop is set up to perform the iterative calculations. The statement that immediately follows the while condition is repetitively executed as long as the absolute difference between guess2 and x is greater than or equal to epsilon. The expression
guess * guess – x
is evaluated and the result of the evaluation is passed to the absoluteValue function. The result returned by the absoluteValue function is then compared against the value of epsilon. If the value is greater than or equal to epsilon, the desired accuracy of the square root has not yet been obtained. In that case, another iteration of the loop is per- formed to calculate the next value of guess.
Eventually, the value of guess is close enough to the true value of the square root, and the while loop terminates. At that point, the value of guess is returned to the call- ing program. Inside the main function, this returned value is passed to the printf func- tion, where it is displayed.
You might have noticed that both the absoluteValue function and the squareRoot function have formal parameters named x. The C compiler doesn’t get confused, howev- er, and keeps these two values distinct.
In fact, a function always has its own set of formal parameters. So the formal parame- ter x used inside the absoluteValue function is distinct from the formal parameter x used inside the squareRoot function.
The same is true for local variables.You can declare local variables with the same name inside as many functions as you want. The C compiler does not confuse the usage of these variables because a local variable can only be accessed from within the function where it is defined. Another way of saying this is that the scope of a local variable is the function in which it is defined. (As you discover in Chapter 11, “Pointers,” C does pro- vide a mechanism for indirectly accessing a local variable from outside of a function.)
Based upon this discussion, you can understand that when the value of guess2 – x is passed to the absoluteValue function and assigned to the formal parameter x, this assignment has absolutely no effect on the value of x inside the squareRoot function.
1. Declaring Return Types and Argument Types
As mentioned previously, the C compiler assumes that a function returns a value of type int as the default case. More specifically, when a call is made to a function, the compiler assumes that the function returns a value of type int unless either of the following has occurred:
- The function has been defined in the program before the function call is encoun- tered.
- The value returned by the function has been declared before the function call is encountered.
In Program 8.8, the absoluteValue function is defined before the compiler encounters a call to this function from within the squareRoot function. The compiler knows, there- fore, that when this call is encountered, the absoluteValue function will return a value of type float. Had the absoluteValue function been defined after the squareRoot function, then upon encountering the call to the absoluteValue function, the compiler would have assumed that this function returned an integer value. Most C compilers catch this error and generate an appropriate diagnostic message.
To be able to define the absoluteValue function after the squareRoot function (or even in another file—see Chapter 15), you must declare the type of result returned by the absoluteValue function before the function is called. The declaration can be made inside the squareRoot function itself, or outside of any function. In the latter case, the declara- tion is usually made at the beginning of the program.
Not only is the function declaration used to declare the function’s return type, but it is also used to tell the compiler how many arguments the function takes and what their types are.
To declare absoluteValue as a function that returns a value of type float and that takes a single argument, also of type float, the following declaration is used:
float absoluteValue (float);
As you can see, you just have to specify the argument type inside the parentheses, and not its name.You can optionally specify a “dummy” name after the type if you want:
float absoluteValue (float x);
This name doesn’t have to be the same as the one used in the function definition—the compiler ignores it anyway.
A foolproof way to write a function declaration is to simply use your text editor to make a copy of the first line from the actual definition of the function. Remember to place a semicolon at the end.
If the function doesn’t take an argument, use the keyword void between the paren- theses. If the function doesn’t return a value, this fact can also be declared to thwart any attempts at using the function as if it does:
void calculateTriangularNumber (int n);
If the function takes a variable number of arguments (such as is the case with printf and scanf), the compiler must be informed. The declaration
int printf (char *format, …);
tells the compiler that printf takes a character pointer as its first argument (more on that later), and is followed by any number of additional arguments (the use of the …). printf and scanf are declared in the special file stdio.h. This is why you have been placing the following line at the start of each of your programs:
#include <stdio.h>
Without this line, the compiler can assume printf and scanf take a fixed number of arguments, which could result in incorrect code being generated.
The compiler automatically converts your arguments to the appropriate types when a function is called, but only if you have placed the function’s definition or have declared the function and its argument types before the call.
Here are some reminders and suggestions about functions:
- Remember that, by default, the compiler assumes that a function returns an int.
- When defining a function that returns an int, define it as such.
- When defining a function that doesn’t return a value, define it as void.
- The compiler converts your arguments to agree with the ones the function expects only if you have previously defined or declared the function.
- To play it safe, declare all functions in your program, even if they are defined before they are called. (You might decide later to move them somewhere else in your file or even to another file.)
2. Checking Function Arguments
The square root of a negative number takes you away from the realm of real numbers and into the area of imaginary numbers. So what happens if you pass a negative number to your squareRoot function? The fact is, the Newton-Raphson process would never converge; that is, the value of guess would not get closer to the correct value of the square root with each iteration of the loop. Therefore, the criteria set up for termination of the while loop would never be satisfied, and the program would enter an infinite loop. Execution of the program would have to be abnormally terminated by typing in some command or pressing a special key at the terminal (such as Ctrl+C).
Obviously, modifying the program to correctly account for this situation is called for in this case.You could put the burden on the calling routine and mandate that it never pass a negative argument to the squareRoot function. Although this approach might seem reasonable, it does have its drawbacks. Eventually, you would develop a program that used the squareRoot function but which forgot to check the argument before call- ing the function. If a negative number were then passed to the function, the program would go into an infinite loop as described and would have to be aborted.
A much wiser and safer solution to the problem is to place the onus of checking the value of the argument on the squareRoot function itself. In that way, the function is “protected” from any program that used it. A reasonable approach to take is to check the value of the argument x inside the function and then (optionally) display a message if the argument is negative. The function can then immediately return without performing its calculations. As an indication to the calling routine that the squareRoot function did not work as expected, a value not normally returned by the function could be returned.1
The following is a modified squareRoot function, which tests the value of its argu- ment and which also includes a prototype declaration for the absoluteValue function as described in the previous section.
/* Function to compute the square root of a number.
If a negative argument is passed, then a message
is displayed and -1.0 is returned. */
float squareRoot (float x)
{
const float epsilon = .00001;
float guess = 1.0;
float absoluteValue (float x);
if ( x < 0 )
{
printf (“Negative argument to squareRoot.\n”);
return -1.0;
}
while ( absoluteValue (guess * guess – x) >= epsilon )
guess = ( x / guess + guess ) / 2.0;
return guess;
}
If a negative argument is passed to the preceding function, an appropriate message is dis- played, and the value –1.0 is immediately returned to the calling routine. If the argu- ment is not negative, calculation of the square root proceeds as previously described.
As you can see from the modified squareRoot function (and as you also saw in the last example from Chapter 7, “Working with Arrays”), you can have more than one return statement in a function. Whenever a return is executed, control is immediately sent back to the calling function; any program statements in the function that appear after the return are not executed. This fact also makes the return statement ideal for use by a function that does not return a value. In such a case, as noted earlier in this chapter, the return statement takes the simpler form
return;
because no value is to be returned. Obviously, if the function is supposed to return a value, this form cannot be used to return from the function.
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.