Previous: 5.2.1 The for Statement
Up: 5.2 New Control Constructs
Previous Page: 5.2.1 The for Statement
Previous: 5.2.1 The for Statement
Up: 5.2 New Control Constructs
Previous Page: 5.2.1 The for Statement
In while statements and for statements, the condition is tested for each iteration before the loop body is executed. Thus, it is possible that the loop may not be executed even once if the loop condition evaluates to False the first time. The C language provides another looping construct which guarantees that the body will be executed at least once: the do...while statement. The loop condition is tested after the body is executed, and the loop continues or terminates depending on the condition value. The syntax for the do...while statement is:
Figure 5.3 shows the control flow for this construct. As with the other loop constructs, the break and continue statements can also be used with the do...while statement. The choice of a loop construct depends on the program logic. There are situations when one construct may be preferable to another.
Programs are often written to find a solution (or solutions) to
an algebraic equation; for example:
Here, the solution for the variable,
, is the square root of
.
In general, such solutions are real numbers, and as we have seen,
floating point representations of real numbers use a finite number of bits,
and are therefore limited in the precision of the result.
Solutions to most numeric problems can never be exact (all solutions are
precise only up to a certain number of decimal digits) but
the result may be sufficiently close to the real solution to be acceptable.
One important numeric computation method to find solutions to equations
involves successive approximations.
This method starts with a for the solution to
the problem, and tests if the guess satisfies the equation.
If the guess is close enough for a solution, it is accepted and
computation terminates; otherwise,
the guess is improved, i.e. brought closer to the
solution and the process is repeated.
After each iteration, the guess is closer and closer to the solution,
until it is acceptably close enough.
One successive approximation algorithm
we will use is Newton's method to compute the square root of a number, .
Newton's method starts with an arbitrary guess, and if
it is not good enough, it is improved by averaging the guess with
.
The process continues until the guess is close enough. Here is an example of the
process for square root of 9.0:
In just three iterations, we have arrived close to the square root of 9.0
(which is 3.0). We will say a guess is close enough to the solution,
if and the
square of
differ by a small value, say 0.001, or less.
The algorithm is simple:
begin with an initial guess
repeatedly do the following
improve the guess
while it is not close enough
We will start with an arbitrary guess, say 1.0, for the square
root of the number, guess = 1.0;
do
guess = improve(guess, x);
while (!close(guess, x))
The body of the loop follows the keyword do.
The loop body is executed and then
the while expression is tested for True or False.
If it is True, the loop is
repeated; otherwise, the loop is terminated. The above loop body calls on a
function improve() to improve the guess and
the condition is then tested to
see if the improved guess is close enough by the function close().
As we said, the difference between do...while and the other loop constructs is that in this case the loop is executed at least once; while loops and for loops may be executed zero times if the loop condition is initially False. In the case of successive approximations, we always expect the initial guess to need improvement; so, the loop must be executed at least once.
Figure 5.4 shows the implementation of the driver. The source file includes a header file mathutil.h that declares the function prototypes for close(), improve(), and other functions defined in a source file, mathutil.c, shown in Figure 5.5. The two source files sqroot.c and mathutil.c must be compiled and linked to create an executable file. Here is mathutil.h:
/* File: mathutil.h */ /* File contains prototypes for functions defined in mathutil.c */ double improve(double guess, double x); int close(double guess, double x); double absolute(double x);Notice we have used the type, double for the parameters and return values of the functions because precision is important in successive approximation algorithms. It is best to use double precision in all such computations. We have also included the header file, tfdef.h, which defines the symbolic constants TRUE and FALSE.
The program driver uses a loop to read a positive, double precision number into x using the conversion specification %lf. (When a double precision number is printed, conversion specification is still %f since a printed double precision floating point number looks the same as a single precision number). If the number read into x is negative or zero, a message is printed and the loop is repeated until a positive number is read. We have used the do...while construct here, since we know that the loop must be executed at least once to get the desired data.
Next, guess is initialized to 1.0 and the loop body improves guess We have included a debug statement to print the value of the improved guess during program testing. The loop repeats until guess is close enough to be an acceptable solution.
We still need to write the
functions improve() and close().
The function close() tests if the absolute value of the
difference between the square of guess and x
is small enough. We will use a function, absolute(),
that returns the absolute value of its argument. Figure 5.5
shows close() and absolute() in the source file, mathutil.c.
Some of the functions defined in this source file are also called within it, e.g. absolute(), so we have included mathutil.h in this source file, as well as tfdef.h, which defines TRUE and FALSE. Finally, we write the function improve() which merely returns the average of guess and x / guess.
Sample Session:
Next, we modify our program to encapsulate it into a function, sqroot(),
and to provide user control over the precision desired for the solution
instead of building it into the function, close().
The sqroot()
function requires two arguments, a number and an acceptable error in the
solution.
We also require a new function close2() that checks if a given guess
is close enough to a solution with a specified margin of error. With this
modification, it is not necessary to use double for numbers
in main(). Only the
actual computations need to be double type for greater precision.
Figure 5.6 shows the
revised driver in which float numbers are used in main()
and the function sqroot() is called to find the square root.
Figure 5.7 shows the prototypes added to mathutil.h
and the new functions in mathutil.c.
The driver simply repeats the following loop: read a number; if the number is negative, continue the loop; otherwise, call sqroot() to find the square root of the number within specified margin; print the value. The function sqroot() merely starts with a guess and improves it in a loop until it is within an allowable margin of error. The final acceptable guess is returned. The function close2() tests if a guess is close to the solution within a specified error.
In main(), numbers are read into float variables, so when arguments are passed to sqroot(), they are cast to double. Likewise, the returned double value is cast to float before assigning it to the variable root. Here is the statement that uses cast operators to convert types:
root = (float) sqroot((double) x, 0.001);Recall that a floating point constant is always assumed to be of type double. If function prototypes are declared, we don't have to convert the types explicitly by cast operators, the compiler will take care of that for both the arguments and the returned value. However, the explicit cast operators improve readability by showing that conversions are taking place.
Sample Session:
In Chapter
we will see that standard library functions are available to
compute the square root and the absolute value of a number.
Our emphasis here has been
to illustrate program development using just the basics of a programming
language, viz. expressions including assignments, branching, and looping.