23
$\begingroup$

Suppose that we don't know logarithm, then how we would able to calculate $\sqrt x$, where $x$ is a real number? More generally, is there any algorithm to calculate $\sqrt [ n ]{ x } $ without using logarithm? More simple techniques would be nice.

Here is a simple technique used to approximate square roots by Persian author Hassan be al-Hossein:

For example: $\sqrt {78}\approx 8\frac { 14 }{ 17 } $ , where $8$ is the nearest integer root of $78$, $14 = 78 - 8^2$, $17 = 2 \times 8 + 1$.

if $n=2^k$ we can use the method above.

For example, for $k=2$ Lets calculate $\sqrt [ 4 ]{ 136 } $: $$\sqrt [ 4 ]{ 136 } =\sqrt { \sqrt { 136 } } \approx \sqrt { 11\frac { 136-{ 11 }^{ 2 } }{ 11\times 2+1 } } =\sqrt { 11\frac { 15 }{ 23 } } \\ \sqrt { 11\frac { 15 }{ 23 } } \approx 3\frac { 11\frac { 15 }{ 23 } -{ 3 }^{ 2 } }{ 3\times 2+1 } =\frac { 544 }{ 161 } =3.38\\$$ The exact result is$$ \sqrt [ 4 ]{ 136 } =3.4149\cdots$$ The method approximates well, but it is working for only $n=2^k$ as I know.

$\endgroup$

13 Answers 13

44
$\begingroup$

For $y=\sqrt{x}$ there is a simple method: $$y = 1 \qquad \text{initialize} \\ y = (x/y+y)/2 \qquad \text{ repeat until convergence} $$ It can be modified for roots of higher orders.

$\endgroup$
  • $\begingroup$ That is a very smart method. $\endgroup$ – newzad Oct 24 '13 at 10:44
  • $\begingroup$ Is this the Babylonian method? $\endgroup$ – Tim Seguine Oct 24 '13 at 12:13
  • 3
    $\begingroup$ @Tim: hmm, I've learnt this method as a young guy from my father - I liked it much because of its simplicitiness and straightforwardness. I've never looked for a name of it. I guess it should most likely be the Newton in disguise. $\endgroup$ – Gottfried Helms Oct 24 '13 at 13:42
  • 7
    $\begingroup$ Heron's method. And sure, it is a special case of Newton. I would not start with $1$, though, one can at least get the number of digits approximately right. $\endgroup$ – Carsten S Oct 24 '13 at 19:48
  • 2
    $\begingroup$ For roots of other orders, e.g., $y=\sqrt[k]{x}$, use $y=(x/y^{k-1}+(k-1)y)/k$ $\endgroup$ – Shushan Wen Nov 17 '15 at 16:02
21
$\begingroup$

There is an old-fashioned digit-by-digit method that I learned when I was at school. The theory of it is explained here with a base 10 example here, and many old arithmetic books give more practical details for actually carrying out the calculations in a sensible manner.

I have a very old arithmetic textbook which does something similar for cube roots, but it gets more tedious, and I have never seen anything for 5th roots.

$\endgroup$
  • 2
    $\begingroup$ This method is effective for young students. +1 $\endgroup$ – mrs Oct 24 '13 at 10:41
  • 5
    $\begingroup$ @BabakS. I have taught it to young students (many times), but I am not sure that many of them enjoyed it ... $\endgroup$ – Old John Oct 24 '13 at 10:54
  • 1
    $\begingroup$ Yes, exactly but somehow I prefer to teach old-fashioned approaches to them. Sometimes, I feel these methods are more effective than the similar ways in Maths. Thanks for sharing it us. $\endgroup$ – mrs Oct 24 '13 at 11:02
  • 1
    $\begingroup$ I implemented the scaffold method for square and cube roots in QuickDraw GX. They are pretty simple in binary. (+1) $\endgroup$ – robjohn Oct 24 '13 at 18:56
6
$\begingroup$

$$f(x)=\sqrt [ n ]{ x }\Rightarrow f'(x)=\frac {x^{(1/n-1)}}{n}$$ $$f'(x_0)\approx\frac{f(x_0+h)-f(x_0)}{h}$$ $$\Rightarrow f(x_0+h)\approx f'(x_0)h+f(x_0)$$ Suppose you want to calculate $f(x)=\sqrt [ 3 ]{ x }$ at $x=7 $ then take $h=-1$ and $x_0=8$ $$f(7)\approx f'(8)(-1)+f(8)\approx-\frac{1}{12}+2\approx\frac{23}{12}$$

$\endgroup$
6
$\begingroup$

The continued fraction method works like this: Suppose $x = a^2 + b$, where $a = \lfloor \sqrt x \rfloor$. Then

$$ \begin{align} x &= \sqrt{a^2 + b}\\ x-a &= \sqrt{a^2 + b} - a\\ \frac{1}{x-a} &= \frac{1}{\sqrt{a^2 + b} - a}\\ &= \frac{1}{\sqrt{a^2 + b} - a}\frac{\sqrt{a^2 + b} + a}{\sqrt{a^2 + b} + a}\\ &= \frac{\sqrt{a^2 + b} + a}{b}\\ &= \frac{x + a}{b} \end{align} $$

Substitute, and get:

$$ \begin{align} x &= a + (x-a)\\ &= a + \frac{b}{a+x}\\ %= a + \frac{b}{2a+\frac{b}{a+x}}\\ x &= a+\cfrac{b}{2a+\cfrac{b}{2a+\cfrac{b}{2a + \dots}}} \end{align} $$

Now, this is not a simple continued fraction. However, if one divides the numerator and denominator of $\frac{b}{2a+x}$ by $b$, then one can eventually get a periodic simple continued fraction, and one approximates by the convergents. The above expression turns out to be faster.

$\endgroup$
  • $\begingroup$ I wonder how quickly this converges compared to Newton's method. $\endgroup$ – Max Oct 24 '13 at 21:50
  • $\begingroup$ This should be slower than Newton's method for square roots. With Newton, $\epsilon_{n+1}\approx k\epsilon_n^2$. $\endgroup$ – Eric Jablow Oct 24 '13 at 22:44
  • $\begingroup$ If this turns into an odd method I remember seeing once, there turns out to be a simple way to step quadratically through the sequence. i.e. after $n$ steps, you are looking at $\epsilon_{2^n}$, not $\epsilon_n$. $\endgroup$ – Hurkyl Dec 22 '13 at 7:38
  • $\begingroup$ @Hurkyl: I don't know what method you're referring to, but there is a simple way to accelerate the convergence of this sequence directly, since the numerator and denominator of its convergents are described by recurrence relations and hence the $k$-th convergent is expressible as the corresponding matrix raised to the $k$-th power and then multiplied by some matrix corresponding to the initial values of the recurrences. The matrix exponentiation can be done by repeated squaring. $\endgroup$ – user21820 May 18 '14 at 10:59
5
$\begingroup$

If $x$ is an integer, then you can find the continued fraction expansion of $\sqrt x$ and get very close approximations with no division involved. If you want 6-place accuracy, for instance, continue till you get a convergent with denominator $>1000$.

$\endgroup$
  • 4
    $\begingroup$ I did not understand. Can you please explain a little bit? $\endgroup$ – newzad Oct 24 '13 at 17:23
  • $\begingroup$ The response of @EricJablow gives one good way to do it. It does help to know something about Continued Fractions beforehand. $\endgroup$ – Lubin Oct 25 '13 at 0:27
  • $\begingroup$ A simple continued fraction for a number, one where each of the leading terms in the denominators is $1$, provides the best rational approximations to the number itself. $\endgroup$ – Eric Jablow Oct 25 '13 at 2:29
  • $\begingroup$ @EricJablow, right, and that’s why I wanted to get the method to the attention of OP. Not as fast as Newton, but I think the fact that you don’t need to do any division is an advantage in hand computation. $\endgroup$ – Lubin Oct 25 '13 at 13:42
3
$\begingroup$

To get $\sqrt[n]{a}$ solve the equation $x^n = a$, e.g. with Newton's method.

$\endgroup$
3
$\begingroup$

You can binary search the answer of the nth root of $x$.

Set $A$ = number you know it's below the nth root and $B$ = one you know is higher then calculate $A+B/2$ if $((A+B)/2)^n \neq x$ then set $B = (A+B)/2$ and repeat (you can always choose $A = 0$ and $B = x$ or $A = 0$ and $B = 1$ if x < 1).

$\endgroup$
2
$\begingroup$

The method by hand, is to use the method of long division with changing divisor. You can do this without a calculator, and works for all numbers.

The trick relies on $(x+d)^2 = x^2 + 2xd + d^2$. One has $x$ as a multiple of 10, and $x^2$ is the bit already subtracted, so you subtract at the next instance $(2x+d).d$. The answer is doubled, and an underscore after it, eg for 78, we have 16._ * _ is less than (78-64).

This is a worked example, with commentry, of the finding of the square root by long division with changing divisor. The new digit is set in brackets here: normally one might write an underscore.

Note digit-paring to assist in finding the estimate of the next place. The place directly after the six is a zero, which means you go (0)(x) at that point.

The pairing of digits must be so that the radix or decimal point falls between a pair. So 1 44 . is paired with the odd digit at the front.

            8 .  8   3   1   7   6  0  9 
          ----------------
         ) 78   00
 (8)       64              8^2 is the largest under 78
           --
  16(8)    14   00         16_ is 2*8, find _ that 16_ * _ is less than 1400
           13   44         _ = 8
           -------
                56  00      difference 56, bring down a pair of zeros.
  176(3)        52  89      176 is twice 88,  176x * x gives x=3
                -------
                 3  11  00       difference, bring down two zeros.
  1 76 6(1)      1  76  61       2 would be too big   
                -----------
                 1  34  39  00     difference, bring down two more zeros
  17 66 2(7)     1  23  62  89     We see that 7 comes to be the next digit.
                 --------------
                    10  76  11  00
  1 76 65 4(6)      10  59  72  44    Here we begin to round by discarding places.
                   ---------------    That is we we just multiply d * x.
                        16  57  56
   17 66 54 ..                         too big, return a 0
    1 76 65 [4]         15  89  49     9
$\endgroup$
1
$\begingroup$

To compute $\sqrt{5}$, for example, you can find a solution to $x^2 - 5 = 0$ using Newton's method.

$\endgroup$
1
$\begingroup$

You can use Taylor expansion of function $(1+x)^{\frac{1}{n}}$

$$(1+x)^{\frac{1}{n}} = \sum_{k=0}^{\infty}x^k(-1)^k {{1/n}\choose{k}} = \sum_{k=0}^{\infty} \frac{x^k(-1)^k}{k!}(1/n)(1/n-1)(1/n-2)\ldots(1/n-(k-1)) = \sum_{k=0}^{\infty} \frac{x^k}{k!n^k}(n-1)(2n-1)\ldots((k-1)n-1)$$

It is simple to calculate the sum. For each $k$ you can use the values of sum for $k-1$

$\endgroup$
  • 1
    $\begingroup$ The series is convergent only for $|x|<1$, but it is easy to transform the problem so that you’re in this range. $\endgroup$ – Lubin Oct 24 '13 at 17:03
0
$\begingroup$

$$\sqrt[3]{x}=1+\frac{x-1}{3}-\frac{2(x-1)^2}{9(2!)}+\sum_{n=1}^\infty (-1)^{n-1} \frac{(2+3n)(2+3(n-1))(x-1) ^n)}{3n(n!)}$$

$\endgroup$
0
$\begingroup$

Every positive number $x$ can be always written as the sum of two other numbers (or the difference).

Say that one of the two is a perfect square $n^2$, then we can always say that

$$x = n^2 + q$$

Where $q$ is the obvious remainder. Since we can also adopt the difference convention, it's better to write

$$x = n^2 \pm q$$

When to choose the plus or the minus? Well the rule is that the smaller is $q$, the better.

After that, we can use the following approximation:

$$\sqrt{x} = \sqrt{n^2 \pm q} \approx n \pm \frac{q}{2n}$$

Example

Let's calculate $\sqrt{40}$. Either we choose $40 = 36 + 4$ or $40 = 49 - 9$. The first one is better of course, hence

$$\sqrt{40} = \sqrt{36 + 4} \approx 6 + \frac{4}{12} = 6 + \frac{1}{3} = 6.\bar 3$$

Notice that the real value is

$$\sqrt{40} = 6.324(...)$$

$\endgroup$
0
$\begingroup$

First some general theory.

Let the real number $S \gt 0$ and the integer $k \gt 1$ be given. We want to calculate $\sqrt[k]{S}$.

For any integer $m \ge 0$ there is a maximum integer $M$ satisfying

$\tag 1 M^k \le 10^{km} \, S$

Let $n = m + 1$, and again let $N$ be the maximum integer satisfying

$\tag 2 N^k \le 10^{kn} \, S$

It is always true that $N \lt 10M + 10$.

It follows from the above theory that we can employ a digit-by-digit calculation for $\sqrt[k]{S}$.

Example: Calculate $\sqrt[4]{136}$.

We naturally start off by using $\text{(1)}$ with $m = 0$, and we get

$\quad 3^4 \lt 136$

So the answer is between $3$ and $4$ and the only question is how many digits we want to calculate.

With $m = 1$ we ask

Is $31^4 \lt 1360000$? Yes.
Is $32^4 \lt 1360000$? Yes.
Is $33^4 \lt 1360000$? Yes.
Is $34^4 \lt 1360000$? Yes.
Is $35^4 \lt 1360000$? NO.

With $m = 2$ we ask

Is $341^4 \lt 13600000000$? Yes.
Is $342^4 \lt 13600000000$? NO.

With $m = 3$ we ask

Is $3411^4 \lt 136000000000000$? Yes.
Is $3412^4 \lt 136000000000000$? Yes.
Is $3413^4 \lt 136000000000000$? Yes.
Is $3414^4 \lt 136000000000000$? Yes.
Is $3415^4 \lt 136000000000000$? NO.

So with $3$ digits after the decimal we get $\sqrt[4]{136} \approx 3.414$.

Now to go thru all the arithmetic you'll no doubt have to get organized and try to minimize the number of times you take (big) numbers to the $4^{th}$ power.

After all this work we can assert that exact value is closer to $3.41$ than $3.42$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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