I’ve been reading a lot about various algorithms lately, and there are a number that just strike me in awe. Their simplicity and efficiency at solving a problem are as masterful and poetic as a well written Haiku. It’s really fascinating.
I have a great example for you called the successive approximation of square root values, and I have written a program for you in C to demonstrate it in action.
Now the basic goal of successive approximation is to estimate ( read guess) the value of an unknown value by repeatedly comparing a sequence of known values. This almost plays out like an illusion by a mentalist or magician where properties of physics/science /math play in an unexpected way in the real world.
The practical application of this algorithm stems from early computing and microcontroller programming where only basic mathematical operators were able to be used (+, -, * , /). This means that when we needed to find square roots, sine functions, logarithms, etc, we had to get the answers through the use of these basic operators.
Now the way we achieve square roots through successive approximation is we use the formula:
B = ( A + ( n / A ) ) / 2
n = the value we look to find the square root of.
A = our guess at the square root value.
B = a potential correct answer.
Now the way it works in our algorithm, we will loop through this formula a number of times and compare the value of B to the value of A. If the difference between these values is less that 1 then we have finally reached a reasonable value. If we wanted a super precise approximation we could make it accurate below 1% difference, but in this example I just made the threshold < 1.
Let’s run through an example. Say we want to find the square root of 9. We will set the value of n = 9. Then we take a guess as to what the square root value will be. It doesn’t matter how far off you are from the correct answer, it just means it will take more loops to get to the correct answer. The closer your guess is the faster your program will run. Let’s be outrageous and guess A = 10.
As the program runs through its routine, A = 10, and after 1 iteration B = 5.4. We will set A = B and run through it again. Now A = 5.4 and B = 3.5. Again we set A = B and run through it again. Now A = 3.5 and B = 3.0. Now the difference between A and B is less than 1, and if we look at the value of B we have the correct square root of 9! It’s a little bit hokey, but it works! And if it only stretches our minds to how powerful basic operations can be, then we’ve accomplished our goal.
Here is our C code for you to run and enjoy.
// Peter C
printf("Enter a number you wish to find the square root value of: \n");
printf("Enter your approximation of the square root value: \n");
B = ( A + (n /A) ) / 2;
A = B;
B = ( A + (n /A) ) / 2;
}while(B/A < 1);
printf("Your result is: %d!", B);