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

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

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

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

Answer 4

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 5

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

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 7

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 8

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 9

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 10

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 11

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