// Square Root of a Number
#include <stdio.h>
#include <stdlib.h>
#define TRUE  1
#define FALSE 0

double avg(double a, double b){
	return (a + b)/2;
}

double absolute(double x){
	if(x > 0) return x;
	else return -x;
}

int check_goodness(double guess, double x){
	if(absolute(guess * guess - x) < 0.000000001) return TRUE;
	else return FALSE;
}

double improve_guess(double guess, double x){
	return avg(guess, x/guess);
}

int main(int argc, char const *argv[]){
	if(argc == 2){
		double x = atoi(argv[1]);
		double guess = 1.0;
		int i = 1;
		do{
			printf("Interation %d: %.4lf\n", i++, guess);
			guess = improve_guess(guess, x);
		}while(!check_goodness(guess, x));
	}
	return 0;
}

Source - Lecture 1A MIT 6.001 Structure and Interpretation, 1986

Algorithm

Square Root of X

  1. Let Guess = 1
  2. WHILE Guess is not Good-Enough DO
  3.      Improve Guess
  4. RETURN Guess


Good-Enough

  1. IF \(Guess \times Guess \approx X\) THEN RETURN TRUE
  2. ELSE RETURN FALSE


Improve Guess

  1. RETURN average of \(Guess, \frac{X}{Guess}\)

The algorithm to find the square root of any positive real number X is simple. We start with a guess that 1 is square root of X. We then improve our guess by averaging guess and x/guess. If our guess was low than the actual square root then averaging step would increase our guess otherwise it would decrease our guess. By repeating this averaging step we can reach to our actual square root very fast.

Example

Compile the above program using gcc

$ gcc sqrt.c -o sqrt
$ ./sqrt 25
Interation 1: 1.0000
Interation 2: 13.0000
Interation 3: 7.4615
Interation 4: 5.4060
Interation 5: 5.0152
Interation 6: 5.0000

$ ./sqrt 2
Interation 1: 1.0000
Interation 2: 1.5000
Interation 3: 1.4167
Interation 4: 1.4142