# Algorithms for “solving” $\sqrt{2}$

The very first words out of my mouth need to be this... "Solving" is the wrong term since I am speaking about irrational numbers. I just don't know which word is the correct word... So that can be part $1$ of my question... what is the correct word since you obviously can't "solve" an irrational number because it goes forever.

Part $2$ (my real question) are there algorithms for figuring out the answer to a problem like the square root of $2$ other than guess-and-checking your way to infinity? Again, I'm obviously not asking for an algorithm to give me the never ending answer because that's crazy... but for example if I wanted to know what the $15^{th}$ decimal place of the square root of $2$ was, is there an algorithm for that?

Thank you! (I'm new here and know nothing about how to format math questions so any help or links would be appreciated as well, thanks!)

-
If you could help me figure out better tags to use in my question that would be nice too :) –  Albert Renshaw Jan 31 '13 at 6:17
What do you mean by 'solving' $\sqrt{2}$? I'd say that $\sqrt{2} = \sqrt{2}$. If you mean show that $\sqrt{2}$ is the root of some equation (say $f(x) = x^2-2$), then simply substitute in and show that the algebra works out. Or do you mean calculating rational approximation / decimal approximation? –  Calvin Lin Jan 31 '13 at 6:20
Are you looking for methods of computing square roots? There is a simple long-division-like method that gives you correct digits one by one. –  Rahul Jan 31 '13 at 6:31
^Brilliant! I don't have enough reputation to up-vote you but this is what I was looking for as well, thank you :) –  Albert Renshaw Jan 31 '13 at 6:46
@AlbertRenshaw You do now! ;) –  Rustyn Jan 31 '13 at 7:29

You can use newton's method to compute the digits of $\sqrt{(2)}$:
Let: $$f(x) = x^2 -2$$ Define the iteration: $$x_0 = 1\\ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ This will converge to $\sqrt{2}$ quadratically.

If you want to compute other square roots:

Consider:
$$g(x) = x^2 - a$$

Which has the iterants: $$x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$$ As mentioned below.

There's also what's called the continued fraction expansion of an algebraic number. You can use a finite continued fraction expansion.

As an example: $$x_0 = 1 \\ x_1 = \frac{1}{2}\left(x_0 + \frac{2}{x_0}\right) =\frac{1}{2}\left( \large \textbf{1} + \frac{2}{ \large \mathbf{1}}\right) = \frac{3}{2}\\ x_2 = \frac{1}{2}\left(x_1 + \frac{2}{x_1}\right) = \frac{1}{2}\left( \large \mathbf{\frac{3}{2}} + \frac{2}{ \large \mathbf{\frac{3}{2}}}\right), \text{ etc. }$$

Since we are using Newton's method, and you are wondering why it converges to the root of $f(x)$,

Note the following:
$\textbf{Theorem}$: Suppose that the function $f$ has a zero at $\alpha$, i.e., $f(\alpha) = 0$

If $f$ is continuously differentiable and its derivative is nonzero at $\alpha$, then there exists a neighborhood of $\alpha$ such that for all starting values $x_0$ in that neighborhood, the sequence ${x_n}$ will converge to $\alpha$.

So if we choose our starting guess appropriately, Newton's method always converges to the root of the equation if $f$ has these properties .

-
In the case of the square root of $a$, this simplifies to $x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$. –  André Nicolas Jan 31 '13 at 6:23
Are you saying 1+(1-(1^2-2)/(2*1))+((1-(1^2-2)/(2*1))-(1^3-2)/(3*1))+(((1-(1^2-2)/(2*1))-(1-(1^‌​3-2)/(3*1)))-(4^2-2)/(4*1))... Sorry it's been a LONG time since I've worked with iterations and what-not I just want to make sure I take the sum of each n value in your defined iteration. (I'm not familiar with Newton's Method) –  Albert Renshaw Jan 31 '13 at 6:34
@AlbertRenshaw No, you don't sum them up. –  Rustyn Jan 31 '13 at 6:36
@AlbertRenshaw have a look at the wikipedia page (en.wikipedia.org/wiki/Newton's_method). There is an animation that should give you a strong intuition for how it works. –  in_wolframAlpha_we_trust Jan 31 '13 at 8:33
I posted a really neat alternative to Newton's method for computing square-roots efficiently at the bottom of this page: math.stackexchange.com/questions/287213/fast-square-roots/…. –  Peder Jan 31 '13 at 15:16

You can also compute square roots using continued fractions. For example for $\sqrt{2}$ you have $$\sqrt{2}=1+(\sqrt{2}-1)=1+\frac{(\sqrt{2}-1)(\sqrt{2}+1)}{\sqrt{2}+1}=1+\frac{1}{\sqrt{2}+1}$$ where $1$ is the integer part of $\sqrt{2}$. Then repeat the process for $\sqrt{2}+1$ whose integer part is $2$: $$\sqrt{2}+1=2+(\sqrt{2}-1)=2+\frac{(\sqrt{2}-1)(\sqrt{2}+1)}{\sqrt{2}+1}=2+\frac{1}{\sqrt{2}+1}$$ therefore by repeating the process we have $$\sqrt{2}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\cdots}}}}$$

-
I like this peder, thank you for elaborating on this for him. I mentioned this in my answer but your motivating example deserves a +1. –  Rustyn Jan 31 '13 at 19:43

A related problem. Another way to go is the Taylor series. Derive the Taylor series of the function $\sqrt{x}$ at the point $x=1$

$$\sqrt{x} = 1+{\frac {1}{2}} \left( x-1 \right) -{\frac {1}{8}} \left( x-1 \right) ^{2}+{\frac {1}{16}} \left( x-1 \right)^{3}-{\frac{5}{128} } \left( x-1 \right)^{4}+O\left( \left( x-1 \right) ^{5} \right).$$

If you plug in $x=2$, you get an approximate value for the $\sqrt{2}\sim 1.398437500$. Increasing the number of terms in the series improves the approximation.

Added: We can write the Taylor series of $\sqrt{x}$ explicitly by finding the $n$th derivative of $\sqrt{x}$ as

$$\sqrt{x} = \sum _{n=0}^{\infty }\frac{\sqrt {\pi }}{2}\,{\frac {{a}^{\frac{1}{2}-n} \left( x-a\right)^{n}}{\Gamma\left( \frac{3}{2}-n \right)n! }}.$$

Substituting $x=1$ in the above formula gives the Taylor series at the point $x=1$

$$\sqrt{x} = \sum _{n=0}^{\infty }\frac{\sqrt {\pi }}{2}\,{\frac { \left( x-1\right)^{n}}{\Gamma\left( \frac{3}{2} - n \right)n! }}.$$

Putting $x=2$ in the above equation, we have

$$\sqrt{2} = \sum _{n=0}^{\infty }\,{\frac {\sqrt{\pi}}{2\,\Gamma\left( \frac{3}{2} - n \right)n! }}.$$

-
Very nice indeed! –  Albert Renshaw Feb 1 '13 at 3:02
@AlbertRenshaw: You are welcome. –  Mhenni Benghorbal Feb 1 '13 at 3:23
Using taylor with $\sqrt{1+1}$ converges extremely slowly since we are so far away from the starting point of our iteration. Eg at the very edge of divergence in fact! It is much faster to use that $$\sqrt{2} = \frac{7}{10}\sqrt{1 - \frac{1}{50}}$$ and now use the taylorexpansion with $1/50$ instead of $1$. –  N3buchadnezzar Feb 16 '14 at 15:57

Following Rystyn's answer: it is nice to write down the decimals to understand how good the convergence is in Newton's method:

1.000000000000000000000000000000000000000000000000000000000000000000000
1.500000000000000000000000000000000000000000000000000000000000000000000
1.416666666666666666666666666666666666666666666666666666666666666666666
1.414215686274509803921568627450980392156862745098039215686274509803921
1.414213562374689910626295578890134910116559622115744044584905019200054
1.414213562373095048801689623502530243614981925776197428498289498623195
1.414213562373095048801688724209698078569671875377234001561013133113265
1.414213562373095048801688724209698078569671875376948073176679737990732
1.414213562373095048801688724209698078569671875376948073176679737990732
1.414213562373095048801688724209698078569671875376948073176679737990732

-


1.500000000000000000000000000000000000000 -> 2.250000000000000000000000000000000000000

1.416666666666666666666666666666666666667 -> 2.006944444444444444444444444444444444444

1.414215686274509803921568627450980392157 -> 2.000006007304882737408688965782391387928

1.414213562374689910626295578890134910117 -> 2.000000000004510950444942772099280764361

1.414213562373095048801689623502530243615 -> 2.000000000000000000000002543584239585437

1.414213562373095048801688724209698078570 -> 2.000000000000000000000000000000000000000

1.414213562373095048801688724209698078570 -> 2.000000000000000000000000000000000000000

1.414213562373095048801688724209698078570 -> 2.000000000000000000000000000000000000000

1.414213562373095048801688724209698078570 -> 2.000000000000000000000000000000000000000

1.414213562373095048801688724209698078570 -> 2.000000000000000000000000000000000000000

-