![]() |
Previous | Table Of Contents | Next | ![]() |
Successive Approximation
Successive approximation algorithms are those algorithms that continue to better approximate some desired result all the longer you allow them to run. You typically iterate these algorithms meaning that you repeat the same processing step over and over again. How do you get such an algorithm started? With an initial guess (and you thought guessing wasn't allowed in math!). It doesn't matter where you start these algorithms since they converge on (head to) the correct answer. If your initial guess is particularly bad then more iterations will be required to achieve a given accuracy, but other than that it doesn't matter where you start.
We are going to write a program which implements a successive approximation algorithm for computing the square root of a number. Most calculators (including our RPN calculator) have a keystroke dedicated for computing square roots and the algorithm that we will study could very well be used internally by the calculator for that keystroke. If we are searching for the square root of n then we select an initial guess A and plug n and A into the following equation:
This equation solves for B, which is the new, improved approximation for the square root of n. Until we are happy with this approximation, we continue repeating the process by copying the new B value into A and then re-executing the same equation to get a new B value. A few iterations of this algorithm for finding the square root of n=9 starting from an initial guess of A=1 are shown below:
So after only 4 iterations we are within a very small percentage of the true answer that sqrt(n) = sqrt(9) = 3. To prove that the initial guess really doesn't matter I will repeat these first 4 iterations, this time using A = 10 for the initial guess:
Since we knew that the square root of 9 was 3 it was pretty easy to tell when we had run the algorithm enough to produce an acceptable result. But we want to be able to write a program that can solve for any square root and this means we can't employ knowledge of the answer in the program.
Our program needs a way to decide that it has run long enough and can quit. We might decide to always run the algorithm for a fixed number of iterations, such as 10. But then the quality of the final result would depend upon how close the initial guess was to the actual square root. There is a better way to know when to stop iterating.
When our initial guess was 1 the algorithm produced a new guess of 5, which means the guess changed by 4 out of 1 or 400%. When the initial guess was 5 the algorithm produced a new guess of 3.4, which means the guess changed by 1.6 out of 5 or 32%. When the initial guess was 3.4 the algorithm produced a new guess of 3.02353 which means the guess changed by .37647 out of 3.4 or 11%. When the initial guess was 3.02353 the algorithm produced a new guess of 3.00009 which means the guess changed by .02344 out of 3.02353 or .7%. So as we performed the algorithm for the first 4 iterations the percent change in the answer went from 400% to 32% to 11% to .7%.
Does this give you the idea that the program could continue looping until the new guess is basically not much different than the old guess, which must indicate that both guesses are pretty close to the true answer? Note that we are comparing two consecutive guesses to each other instead of comparing the latest guess to the true answer (which we don't know).
If you stop iterating the algorithm when two consecutive approximations are within, say, .001 of each other then the program will produce excellent results for the sqrt(n) as long as the true sqrt(n) is much larger than .001 . But this program will halt too soon when asked to compute, say, sqrt(.00000001). So we want to continue to iterate until the change in the approximation is a small PERCENTAGE rather than a small number.
Another cute aspect of this method of computing a square root is that it only requires that the hardware support the 4 basic math operations of +, -, *, and /. And, as we will learn in the next section of our curriculum where we study an Intel 8051 microprocessor, these are the only math functions built into a microprocessor. Hence it is a software algorithm such as the successive approximation algorithm shown here that must provide other results such as square roots, sine functions, logarithms, etc.
My implementation of this successive approximation algorithm for computing a square root can be found in the SquareRoot.txt file. Try it out! To compute the square root of 8 you would use the keystroke sequence 8, GSB 0. Remember that you can single step this (or any other) program to watch it do its thing.
![]() |
Previous | Table Of Contents | Next | ![]() |