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: \begin{align} y &= 1 &&\text{initialize} \\ y &=\frac {(\frac{x}{y}+y)}{2} & &\text{repeat until convergence} \end{align} 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

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 7

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

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

Calculate $\sqrt [ 4 ]{ 136 }$ using interpololation.

$3^4 = 81$
$4^4 = 256$
$256 - 81 = 175$
$136-81 = 55$

$\sqrt [ 4 ]{ 136 } \approx 3 + \frac{55}{175}$

We started with rough estimations, but now we're going to tenths:

$34^4 = 1336336$
$35^4 = 1500625$
$1500625 - 1336336 = 164289$
$1360000 - 1336336 = 23664$

$\sqrt [ 4 ]{ 136 } \approx 3.4 + \frac{23664}{164289} \times 10^{-1} \approx 3.4144$

If we want the error to be no more than $10^{-3}$ then at this point we can check

$\tag 1 3414^4 = 135848255916816$ $\tag 2 3415^4 = 136007491950625$

and confidently state that

$$\tag 3 3.414 \lt \sqrt [ 4 ]{ 136 } \lt 3.415$$

But what if $\text{(1)}$ and $\text{(2)}$ had not straddled $136$? That would be more than upsetting!

Answer 12

$$\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 13

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 14

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

Answer 15

Use my method: The natural algorithm

See the computational representation of the algorithm

Let $N$ be the number that we want to calculate its square root.

The square root of $N$ is calculated in two stages:

The first stage: finding the nearest real root of $N$:

We make $n=N$

1. We subtract from $n$ the terms of $2x-1$ starting from $x=1$
   • While $n>0$, we make $x=x+1$, and we proceed the substraction.
   • When $n=0$, this stage stops and the number $N$ has a real square root of $x$.
   • When $n<0$, this stage stops, the nearest real square root is $x-1$, and we continue the second stage to find the numbers after the comma.

The second stage: Finding the numbers after the comma:

Let $x$ be the nearest real square root of $N$

Let $b=N-x^2$

The following process is repeated for the number of digits we want to find after the comma:

We divide this process into 3 steps

1. Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a hundred

2. Step 2: We assume $s=x$,

3. Step 3: We subtract $2s+1$ from $b$

   • If the result of $b$ is greater than zero:
     • we add to $s$ one, and continue from step 3.
   • If the result of $b$ is less than zero:
     • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$
     • In the space after the comma, we write the number $i$
     • We get to b the quotient of $2s+1$
     • We add to $x$ the number of subtractions $i$,
     • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

---

E.g.

A number with a real square root

$N=64; \sqrt[2]N=?$

We make $n=N$

1. We subtract from n the terms of $2x-1$ starting from $x=1$

$x=1: n=64-(2x-1)=64-1=63$

$x=2: n=63-(4-1)=63-3=60$

$x=3: n=60-5=55$

$x=4: n=55-7=48$

$x=5: n=48-9=39$

$x=6: n=39-11=28$

$x=7: n=28-13=15$

$x=8: n=15-15=0$

• this stage stops and the number $N$ has a real square root of $x$.

$\sqrt[2]N=x; \sqrt[2]64=8$

---

E.g.

A number with an unreal square root

$N=122; \sqrt[2]N=?$

We make $n=N$

1. We subtract from n the terms of $2x-1$ starting from $x=1$:

$x=1: n=122-(2x-1 )=122-1=121$

$x=2:n=121-(4-1)=121-3=118$

$x=3:n=118-5=113$

$...$

$x=10:n=41-19=22$

$x=11:n=22-21=1$

$x=12:n=1-23=-22$

• This stage stops, the nearest real square root is $x-1$, and we continue the second stage to find the numbers after the comma.

$$\sqrt[2]N=x-1; \sqrt[2]122≈12-1≈11$$

Let $x$ be the nearest real square root of $N$: $$x=11$$

Let $b=N-x^2$: $$b=N-x^2=122-121=1$$

1- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a hundred: $$x=x×10=110$$ $$b=b×100=100$$

2- Step 2: We assume $s=x$: $$s=110$$

3- Step 3: We subtract $2s+1$ from $b$

$b=b-(2s+1)=100-221=-121$

• As the result of $b$ is less than zero:
  • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=0$$
  • In the space after the comma, we write the number $i$: $$\sqrt[2]122≈11.0$$
  • We get to $b$ the quotient of $2s+1$: $$b=100$$
  • We add to $x$ the number of substractions $i$: $$x=x+0=110$$
  • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

4- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a hundred: $$x=x×10=1100$$ $$b=b×100=10000$$

5- Step 2: We assume $s=x$: $$s=1100$$

6- Step 3: We subtract $2s+1$ from $b$:

$b=b-(2s+1 )=10000-2201=7799…(i=1)$

• If the result of $b$ is greater than zero:
  • we add to $s$ one, and continue from step 3

$s=s+1=1101: b=b-(2s+1)=7799-2203=5596…(i=2)$

$s=1102: b=5596-2205=3391…(i=3)$

$s=1103: b=3391-2207=1184…(i=4)$

$s=1104: b=1184-2209=-1025$

• As the result of $b$ is less than zero:

  • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=4$$

  • In the space after the comma, we write the number $i$: $$\sqrt[2]122≈11.04$$

  • We get to b the quotient of $2s+1$: $$b=1184$$

  We add to $x$ the number of substractions $i$: $$x=x+4=1104$$

  • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

7- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a hundred: $$x=x×10=11040$$ $$b=b×100=118400$$ 8- Step 2: We assume $s=x$: $$s=11040$$

9- Step 3: We subtract $2s+1$ from $b$:

$b=b-(2s+1)=118400-22081=96319…(i=1)$

• If the result of $b$ is greater than zero:
  • we add to $s$ one, and continue from step 3

$s=s+1=11041: b=b-(2s+1)=96319-22083=74236…(i=2)$

$s=s+1=11042: b=b-(2s+1)=74236-22085=52151…(i=3)$

$s=s+1=11043: b=b-(2s+1)=52151-22087=30064…(i=4)$

$s=s+1=11044: b=b-(2s+1)=30064-22089=7975…(i=5)$

$s=s+1=11045: b=b-(2s+1)=7975-22091=-14116$

• As the result of $b$ is less than zero:

  • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=5$$

  • In the space after the comma, we write the number $i$: $$\sqrt[2]122≈11.045$$

  • We get to $b$ the quotient of $2s+1$: $$b=7975$$

  • We add to $x$ the number of substractions $i$: $$x=x+1=11045$$

  • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

…

---

The answer to this question, based on the natural algorithm:

Let $N$ be the number you're calculating its square root,

Let $n$ be the limited unreal square root of N,

Let $i$ be the index of the digit you're trying to find after the comma ,

Put $$b=(N-n^2)(10^i)^2$$

Put $$s=n×10^i$$

• substract from $b$ the result of $2s+1$
  • while $b>0$ add to $s$ one and continue the substraction.
  • when $b<0$: the operation stops and the digit is the number of substractions, not counting the time that produced $b<0$

---

Computational representation of the algorithm in JavaScript:

https://codepen.io/am_trouzine/pen/ExoPmmy

Nth root calculation:

https://m.youtube.com/watch?v=uEpv6_4ZBG4&feature=youtu.be

My notes:

https://github.com/am-trouzine/Arithmetic-algorithms-in-different-numeral-systems/blob/master/Arithmetic%20algorithms%20in%20different%20numeral%20systems.pdf