/*---------------------------------------------------------------------- File : heron.c Contents: compute the square root of a number with Heron's algorithm Author : Christian Borgelt History : 05.11.1997 file created 06.11.1997 comments extended 17.11.1997 check for correct argument added ----------------------------------------------------------------------*/ #include #include #define PRECISION 0.000001 /* desired precision of square root */ int main (int argc, char *argv[]) { /* --- compute square root */ double x; /* number to compute square root of */ double y_curr; /* current approx. of square root */ double y_prev; /* previous approx. of square root */ if (argc != 2) { /* if wrong number of arguments given */ printf("usage: %s x\n", argv[0]); printf("compute the square root of x with Heron's algorithm\n"); return 0; /* print a usage message */ } /* and abort the program */ x = atof(argv[1]); /* convert argument to a number */ if (x < 0) { /* check for correct argument */ printf("%s: illegal number\n", argv[0]); return 1; } y_curr = 0.5 *(1.0 +x); /* compute first approximation */ do { /* note current approximation */ y_prev = y_curr; /* and compute the next */ y_curr = 0.5 *(y_prev +x/y_prev); } while (y_prev -y_curr > PRECISION); /* while desired prec. not reached */ printf("%.15f\n", y_curr); /* print result (the square root) */ return 0; /* return 'ok' */ } /* main() */ /*---------------------------------------------------------------------- Heron's algorithm to compute the square root of a number is based on the following iteration formula: Let x be the number of which the square root is to be computed. Then y_{n+1} = 0.5*(y_n +x/y_n) provides increasingly better approximations of sqrt(x). The start value y_1 can be chosen arbitrarily. It does not affect the result but only the number of steps to reach a desired precision. So simply choose 1. Heron's algorithm is a safe way to compute the square root up to given precision, because it can be shown that 0 <= y_n -sqrt(x) <= y_{n-1} -y_n. Note that we compute the first step of the iteration before we start the loop. It is not possible to start with y_curr = 1 and let the loop compute the first approximation, since that y_prev > y_curr can be proven only from the second step on. (As a counterexample for the first step take x = 2. Then in the first step it is y_curr = 0.5 *(1 +2) = 1.5 > 1.) Thus if we computed the first approximation in the loop, it would terminate after the first execution with a very imprecise result. This program also demonstrates how to evaluate command line arguments. Command line arguments are the strings you type in at the terminal after the program name when you invoke the program. These arguments are passed to a C program in two parameters of the main function, usually named argc (for 'argument count') and argv (for 'argument vector'). The first (argc) contains the number of strings you typed in at the terminal when you invoked the program. Note: the number of strings, not the number of arguments of the program. The program's name is also a string you typed in and hence it is passed to the program and counted as an argument. It follows that argc must always be at least 1. If program arguments are given, argc is greater than 1. The above program takes one argument, namely the number to compute the square root of. Hence argc must be 2: There are the program's name and the number. The first thing we do is to check argc. If it is not 2, then the program was not invoked properly. It is good style to print out a usage message in this case, to give the user a hint how to use the program. We provide only a very brief usage message, which tells the user that the program expects one argument x. In the usage message we do not use a fixed name of the program. Although this file is named 'heron.c' there is no obligation to call the executable program 'heron'. It could also be called 'sqrt', for example (using the -o option of the compiler). In this case a usage message 'usage: heron x' would be confusing, since the user typed 'sqrt' to invoke the program. To avoid this, we get the program's name from the argument vector. A vector is an ordered set of objects of the same type, in this case an ordered set of strings. That it consists of strings is indicated by the 'char *' data type. That it is a vector is indicated by the '[]' after the parameter name. The first element of a vector always has the index 0 in C. Hence argv[0] is the first string typed in at the command line, which must be the program's name. So we print it in the usage message. In this way we always print the name the user typed in to invoke the program. If the check on the argument count succeeds, that is, if argc is 2 as expected, we get the number to compute the square root of from the second argument. Since the first argument has index 0, the second argument has index 1. We convert this argument to a number using the standard library function atof ('ascii to float'). This is necessary, since the arguments are always strings, not numbers. And then we are ready to do the computations described above. Exercise: Modify this program in such a way that the desired precision can be given as a second optional parameter to the program. (Hint: argc can then be 2 or 3. If it is three, assume that you can find the precision in argv[2], otherwise use a default precision.) ----------------------------------------------------------------------*/