how or why the method long division for finding square root of a number works

Question

I was wondering how this method developed and also how it works to give the square root of a number upto a large number of decimal digits . Please guide me.

Answer 1

You presumably refer to the Babylonian method to evaluate square roots via divisions.

Assume that you want to compute the square root of $a$ and yo have an estimate $x\approx \sqrt a$. Then

$$x<\sqrt a\iff \frac ax>\sqrt a$$ so that if the estimate is too small (too large), $\dfrac ax$ is another estimate, too large (too small). And it turns out that the average of the two

$$\frac12\left(x+\frac ax\right)$$

is a much better estimate. You can repeat the computation at will.

E.g. for $\sqrt 2$,

$$1\to\frac32\to\frac{17}{12}\to\frac{577}{408}\to\frac{665857}{470832}\to\cdots$$

The square of the last fraction is $2.0000000000045\cdots$

---

Technical note 1:

The formula is an embodiment of Newton's method to solve nonlinear equations. It works by locally replacing the graph of the function at hand by its tangent. For the square root, we want to solve

$$f(t)=t^2-a=0.$$ The tangent to $f$ at a given $t$ has the equation

$$y=2t(x-t)+(t^2-a).$$ Then the solution of $y=0$ is

$$x=\frac{t^2+a}{2t}=\frac12\left(t+\frac at\right).$$

---

Technical note 2:

To study convergence of the iterations observe that

$$x_{n+1}=\frac{x_n^2+a}{2x_n}$$

implies

$$\frac{x_{n+1}-\sqrt a}{x_{n+1}+\sqrt a}=\frac{x_n^2-2x_n\sqrt a+a}{x_n^2+2x_n\sqrt a+a}=\left(\frac{x_{n}-\sqrt a}{x_{n}+\sqrt a}\right)^2$$

and by induction,

$$\frac{x_{n}-\sqrt a}{x_{n}+\sqrt a}=\left(\frac{x_0-\sqrt a}{x_0+\sqrt a}\right)^{2^n}.$$

For any positive $x_0$, the fraction on the right is smaller than $1$, and its powers tend to $0$ very quickly. Hence convergence of $x_n$ to $\sqrt a$ is guaranteed from any initial value.

Even with a very bad initial value,

$$(1-\epsilon)^2\approx 1-2\epsilon$$ shows that you gain at least one exact bit one every iteration. But when you are close, the number of bits doubles every time !

---

If you are referring to the written calculus method using the decimal representation, it is based on the identity

$$(10x+d)^2=100x^2+20xd+d^2.$$

If at some stage of the computation, you have obtained a $k$-digits approximation $x$ to the square root $x^2\approx a$, you can obtain a better approximation by appending another digit, and you take the largest such that $100x^2+20xd+d^2\le a$.

In this expression, the first term is the square of $x$ shifted left by two positions, then next is twice $x$ times the digit and shifted, and of course $d^2$ is the squared digit. For the choice of the digit, you rely on $20xd\simeq a-100x^2$ and perform the quick division $\dfrac{a-100x^2}{20x}$.

[I left implicit that as you go, you incorporate more and more digits of $a$, two by two, so that $a$ and $x^2$ are on the same order. Sorry for lack of rigor.]