How to calculate the square root of a number? [duplicate]

Solution 1:

There's one algorithm which is not bad at all, and it's stable. It involves no guessing, but you do need a starting point. To illustrate the algorithm, suppose you want to find $\sqrt{2}$. Start with anything (the closer the better); for example start with $1$. Because $1 < \sqrt{2}$, then $2/1=2 > \sqrt{2}$. Average these to get $1.5$. $1.5$ is too large, which means that $2/1.5=4/3=1.3333\cdots$ will be smaller than $\sqrt{2}$. Average these two to obtain $\frac{1}{2}(3/2+4/3)=\frac{1}{2}\frac{17}{6}=\frac{17}{12}=1.416666\cdots$. This value is too small, and $2/(17/12)=\frac{24}{17}$ is too large. So average these to get $$ \frac{1}{2}\left(\frac{17}{12}+\frac{24}{17}\right)=\frac{577}{408}=1.4142156862\cdots $$ This is already accurate to 6 decimal places. Repeating this process leads quickly to a good approximation of $\sqrt{2}$. One more iteration gives $$ \frac{1}{2}\left(\frac{577}{408}+2\frac{408}{577}\right) =\frac{665857}{470832}=1.4142135623747\cdots, $$ which is accurate to about 12 digits. The starting guess of $1$ wasn't all that great, but it still didn't take many iterations to get a good value of $\sqrt{2}$.

Solution 2:

One method for approximating roots is Newton's Method, which uses a tangent line approximation to approach the actual value of a root.

Since it is given that $f(x) \approx f(x_0) + (x - x_0)f'(x_0)$, consider the function $f(x) = x^2 - 2$. Clearly, this quadratic has root $\sqrt{2}$. The goal is to get closer and closer to the y-intercept of this function (which is $\sqrt{2}$). We do this by taking the tangent line approximation of a value on the curve $x^2 - 2$ (say, $1.5$) and finding where that line intercepts the y-axis. Then, we plug the intercept in and get a new (more accurate) intercept.

_{(source: lamar.edu)}

Check Paul's Online Notes for more info, or Wikipedia.

But to answer your question definitively, no. There is no way to get the value of an irrational number like $\sqrt{2}$ through a simple formula; it nearly requires computation. :(

Solution 3:

The easiest way to find $\sqrt[n]{a}$ for integer $n$ and $a>0$ efficiently is to use the Newton-Raphson approximation to invert the function $f : x \mapsto x^n - a$. But one must be careful with choosing the right starting point, so that the iteration will converge quadratically. Quadratic convergence means that at each step the error becomes approximately a constant times its square, which is equivalent to the error being proportional to $c^{2^k}$ after $k$ steps, for some $c \in (0,1)$

Let $x_0$ be such that $x_0 \in \sqrt[n]{a}[1,1+\frac{1}{4n})$

For each natural $k$ from $0$ to $\infty$:

  Let $x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)} = x_k - \dfrac{{x_k}^n-a}{n{x_k}^{n-1}} = \dfrac{(n-1){x_k}^n-a}{n{x_k}^{n-1}}$

Then $( x_k : k \in \mathbb{N} )$ converges quadratically to $\sqrt[n]{a}$ uniformly for all $a>0$

General Case

For any real function $f$ such that $f(r) = 0$ and $f' \ne 0$ and $f''$ exists and $\left|\frac{f''}{2f'(r)}\right| \le m$ for some $m$:

  Let $a = f'(r) \ne 0$

  Then $f(r+d) = a d + g(d) d^2$ for any $d$ for some function $g$ such that:

    $g(d) \in a [-m,m]$ for any $d$

  Also $f'(r+d) = a + h(d) d$ for any $d$ for some function $h$ such that:

    $h(d) \in a [-m,m]$ for any $d$

  Let $( x_k : k \in \mathbb{N} )$ be such that:

    $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ for any natural $k$

    $|x_0-r| \le \frac{1}{6m}$

  For each natural $k$ from $0$ to $\infty$:

    $x_k = r + d_k$ for some $d_k$

    $|d_k| \le |d_0| \le \frac{1}{6m}$ by invariance

    $x_{k+1} = (r+d_k) - \dfrac{ad_k+g(d_k){d_k}^2}{a+h(d_k){d_k}} \in (r+d_k) - \dfrac{d_k+[-m,m]{d_k}^2}{1+[-m,m]{d_k}}$

    Thus $d_{k+1} \in d_k - (d_k+[-m,m]{d_k}^2) (1-[-m,m]{d_k}+[0,2]([-m,m]{d_k})^2)$ because:

      $\frac{1}{1+t} \in 1-t+[0,2]t^2$ for any $t \ge -\frac{1}{2}$

    Thus $d_{k+1} \in d_k - (d_k+[-m,m]{d_k}^2) (1+[-m,m]{d_k}+\frac{1}{3}[-m,m]d_k) \\ \quad \subseteq \frac{7}{3}[-m,m]{d_k}^2 + \frac{4}{3}[-m,m]^2{d_k}^3 \subseteq \frac{7}{3}[-m,m]{d_k}^2 + \frac{7}{18}[-m,m]{d_k}^2 \\ \quad \subset 3[-m,m]{d_k}^2 \subset [-1,1]d_k$

    Thus the invariance is preserved

    Also $3 m |d_{k+1}| < ( 3 m |d_k| )^2$

  Therefore $3 m |d_k| < ( 3 m |d_0| )^{2^k} \le 2^{-2^k}$ for any natural $k$

  Thus $x_k \to r$ quadratically as $k \to \infty$

Notes

In the case of finding $r = \sqrt[n]{a}$, the function $f : x \mapsto x^n - a$ has $\frac{f''}{2f'(r)}$ being $x \mapsto \frac{(n-1)x^{n-2}}{2r^{n-1}}$ which is bounded on $r[1,1+\frac{1}{4n})$ by $m = \frac{2n}{3r}$ because $\frac{n}{2r} (\frac{x}{r})^{n-2} \le \frac{n}{2r} (1+\frac{1}{4n})^n < \frac{n}{2r} e^{1/4} < m$. Thus $|x_0-r| < \frac{r}{4n} = \frac{1}{6m}$.

The procedure to find $x_0$ for efficient arbitrary precision arithmetic can be as follows:

  Find the minimum integer $d$ such that $(2^d)^n \ge a$

  Binary search on $[2^{d-1},2^d]$ to find $r$ until within an error of $\frac{2^{d-1}}{4n}$

  Return the upper bound when the upper and lower bounds are within the error margin

  The upper bound is between $r$ and $r+\frac{2^{d-1}}{4n} < r+\frac{r}{4n}$