2
$\begingroup$

This question already has an answer here:

By searching I found few methods but all of them involve guessing which is not what I want.

I need to know how to calculate the square root using a formula or something. In other words how does the calculator calculate the square root?

$\endgroup$

marked as duplicate by Rahul, Lost1, M Turgeon, Namaste calculus Jul 10 '14 at 11:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ en.wikipedia.org/wiki/Methods_of_computing_square_roots $\endgroup$ – blue May 17 '14 at 17:37
  • 1
    $\begingroup$ Thanks for your help, I don't understand how I didn't find this while searching. $\endgroup$ – Mhmd May 17 '14 at 17:49
  • 1
    $\begingroup$ Also, the guess-and-check method is fine for a naive and straightforward method. If it makes it seem less arbitrary and luck-based, think of it as iterated process-of-elimination. $\endgroup$ – blue May 17 '14 at 17:51
  • 4
    $\begingroup$ It's likely that the calculator has efficient algorithms for calculating the natural exponential and logarithmic functions and it implements $\sqrt{x} = \exp \left( \frac{1}{2} \ln x \right)$. $\endgroup$ – Sammy Black May 17 '14 at 17:52
  • 1
    $\begingroup$ Every method for finding square roots is just a sophisticated guess-and-check method. $\endgroup$ – Jack M May 25 '14 at 17:04
4
$\begingroup$

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}$.

$\endgroup$
  • 1
    $\begingroup$ @Mhmd: This may be the easiest algorithm to understand, but it is just binary search and hence converges only linearly, thus it is never used in practice. Calculators probably use some form of Newton-Raphson, while arbitrary precision libraries will probably use a much faster algorithm to calculate $\ln$ and Newton-Raphson to compute $\exp$ from inverting $\ln$, and then use $\sqrt[n]{a} = e^\frac{\ln(a)}{n}$. $\endgroup$ – user21820 May 18 '14 at 8:47
  • 2
    $\begingroup$ @user21820 Read more carefully: this is far better than binary search and is in fact equivalent to Newton iteration on $x^2 - 2$. $\endgroup$ – Erick Wong May 18 '14 at 9:03
  • $\begingroup$ @ErickWong: You're right! I had read it correctly a few hours ago but misread it when I read it again just now. So sorry! $\endgroup$ – user21820 May 18 '14 at 9:13
3
$\begingroup$

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.

Newton's Method Illustration
(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. :(

$\endgroup$
  • 1
    $\begingroup$ Note that using Newton-Raphson is not so simple, and textbooks usually do not give the exact conditions for the quadratic convergence and show how to guarantee it in practice; see my answer. $\endgroup$ – user21820 May 18 '14 at 8:43
2
$\begingroup$

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}$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.