How do you find a square root of a number? Think about that for a second. We are so used to using integers, memorizing numbers (to a certain decimals) or relying on computer to calculate a square root for us, and have lost the understanding in performing this computation ourselves. For example, nearly everyone can immediately answer 2 for \(\sqrt{4}\) or 3 for \(\sqrt{9}\). But, how many of us can tell the square root between 4 and 9 right off the bat? How about \(\sqrt{5}\)? I can't. I have to use my calculator, but I know that \(\sqrt{5}\) falls somewhere between 2.2 and 2.4, because I remember that \(22^2 =484\) and \(24^2 = 576\), which by taking a tenth of 22 or using \(2.2^2\) would give us 4.84. Therefore, \(\sqrt{5}\) must be less than 2.4 but greater than 2.2. Now, what is the answer and how does a computer calculate that?
Iterative Substitution
Let the number that we are interested to compute the square root be represented by b. For this discussion, we will assume that \(b > 0\). Our problem is to find x such that:
$$\ x = \sqrt{b}$$
Take square on both sides:
$$\ x^2 = b$$
Rearrange above:
$$\ x = \frac{b}{x}$$
This is an implicit equation for \(x\), in which dependent variable (i.e. \(x\)) cannot be separated. For more definition about implicit equation, see here: calculushowto. Naturally, this form of equation suggests the use of the iterative substitution algorithm or fixed-point iteration method to update \(x\) from the previous \(x\):
$$\ x_{new} = \frac{b}{x_{old}}$$
Or, we can sub "new" and "old" with the iteration count, \(n\):
$$\ x_{n+1} = \frac{b}{x_n}$$
where \(n = 0, 1, 2, 3,...\) and \(x_0\) is an initial guess at a solution.
Example
Let b=9 and \(x_0\)=2, we see that we are bouncing around the answer.
