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

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.

• How about the bisection method? – George Tomlinson Oct 24 '13 at 10:37
• @bluesh34 or Newton method. But I am looking more primitive techniques. I should say so. – newzad Oct 24 '13 at 10:39
• Define primitive. Newton's method in this case is as simple as it gets. See also en.wikipedia.org/wiki/Methods_of_computing_square_roots. – lhf Oct 24 '13 at 11:00
• On a slight tangent, there is a remarkably efficient way of approximating inverse square roots described here: en.wikipedia.org/wiki/0x5f3759df – squeamish ossifrage Oct 24 '13 at 12:37
• – LarsH Oct 24 '13 at 15:13

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.

• That is a very smart method. – newzad Oct 24 '13 at 10:44
• Is this the Babylonian method? – Tim Seguine Oct 24 '13 at 12:13
• @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. – Gottfried Helms Oct 24 '13 at 13:42
• 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. – Carsten S Oct 24 '13 at 19:48
• For roots of other orders, e.g., $y=\sqrt[k]{x}$, use $y=(x/y^{k-1}+(k-1)y)/k$ – Shushan Wen Nov 17 '15 at 16:02

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.

• This method is effective for young students. +1 – mrs Oct 24 '13 at 10:41
• @BabakS. I have taught it to young students (many times), but I am not sure that many of them enjoyed it ... – Old John Oct 24 '13 at 10:54
• 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. – mrs Oct 24 '13 at 11:02
• I implemented the scaffold method for square and cube roots in QuickDraw GX. They are pretty simple in binary. (+1) – robjohn Oct 24 '13 at 18:56

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

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.

• I wonder how quickly this converges compared to Newton's method. – Max Oct 24 '13 at 21:50
• This should be slower than Newton's method for square roots. With Newton, $\epsilon_{n+1}\approx k\epsilon_n^2$. – Eric Jablow Oct 24 '13 at 22:44
• 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$. – user14972 Dec 22 '13 at 7:38
• @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. – user21820 May 18 '14 at 10:59

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

• I did not understand. Can you please explain a little bit? – newzad Oct 24 '13 at 17:23
• The response of @EricJablow gives one good way to do it. It does help to know something about Continued Fractions beforehand. – Lubin Oct 25 '13 at 0:27
• 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. – Eric Jablow Oct 25 '13 at 2:29
• @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. – Lubin Oct 25 '13 at 13:42

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

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

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          15  89  49     9


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

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$

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

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!

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

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

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