24
$\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$
10
  • 3
    $\begingroup$ How about the bisection method? $\endgroup$ Commented Oct 24, 2013 at 10:37
  • 2
    $\begingroup$ @bluesh34 or Newton method. But I am looking more primitive techniques. I should say so. $\endgroup$ Commented Oct 24, 2013 at 10:39
  • 6
    $\begingroup$ 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. $\endgroup$ Commented Oct 24, 2013 at 11:00
  • 1
    $\begingroup$ On a slight tangent, there is a remarkably efficient way of approximating inverse square roots described here: en.wikipedia.org/wiki/0x5f3759df $\endgroup$ Commented Oct 24, 2013 at 12:37
  • $\begingroup$ See also: math.stackexchange.com/questions/222364/… $\endgroup$ Commented Oct 24, 2013 at 15:13

15 Answers 15

Reset to default
42
$\begingroup$

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.

$\endgroup$
8
  • 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$ Commented Oct 24, 2013 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$ Commented Oct 24, 2013 at 19:48
  • 3
    $\begingroup$ For roots of other orders, e.g., $y=\sqrt[k]{x}$, use $y=(x/y^{k-1}+(k-1)y)/k$ $\endgroup$ Commented Nov 17, 2015 at 16:02
  • 1
    $\begingroup$ @GottfriedHelms I made a post about finding sqrt 2 that uses ideas from tommy and yourself kinda. I linked your paper. sorry if this comment is a bit unwanted here. $\endgroup$ Commented Mar 26, 2023 at 23:10
  • 1
    $\begingroup$ @Mick - thanks for notification! (And nice to see that the essay on the beautiful "dream-of-a-sequence" has found some interested reader!) $\endgroup$ Commented Mar 27, 2023 at 8:01
22
$\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$
4
  • 2
    $\begingroup$ This method is effective for young students. +1 $\endgroup$ Commented Oct 24, 2013 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$ Commented Oct 24, 2013 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$ Commented Oct 24, 2013 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$ Commented Oct 24, 2013 at 18:56
7
$\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$
2
  • $\begingroup$ Less accurate than usually required for numbers 'far' from perfect nth powers. Works exceptionally well for, say, 4th root of 17. $\endgroup$ Commented Aug 29, 2022 at 11:11
  • $\begingroup$ This directly because in the definition of derivative, h tends to 0 in the limit. $\endgroup$ Commented Aug 29, 2022 at 11:14
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$
4
  • $\begingroup$ I wonder how quickly this converges compared to Newton's method. $\endgroup$ Commented Oct 24, 2013 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$ Commented Oct 24, 2013 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$ Commented Dec 22, 2013 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$ Commented May 18, 2014 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
  • 4
    $\begingroup$ I did not understand. Can you please explain a little bit? $\endgroup$ Commented Oct 24, 2013 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$ Commented Oct 25, 2013 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$ Commented Oct 25, 2013 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$ Commented Oct 25, 2013 at 13:42
4
$\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$
3
$\begingroup$

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

$\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
  • 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$ Commented Oct 24, 2013 at 17:03
1
$\begingroup$

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!

$\endgroup$
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
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$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.