Is there any simple method to calculate $\sqrt x$ without using logarithm

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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).

Answer 8

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

Answer 9

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

Answer 10

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$

Answer 11

$$\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!)}$$

Answer 12

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(...)$$

Answer 13

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