Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Okay, I know this is very basic question. I learned 2 methods in school. But now, I forget one.

Here is a simple method that I know.

  1. Find the prime divisors of the number
  2. Omit the half of numbers that have been appeared even times
  3. multiply the rest

For example you want to find square root of 36. You find the divisors. They are 2x2x3x3. In step 2 they appeared as 2x3. That is 6. Problem is this method works when the square root is an integer number. It doesn't work for numbers that doesn't have integer square root. Like 38.

So my question is how can I find the square root of any arbitrary number using pen and paper?

share|improve this question
7  
3  
I learned this in school, and the teacher even said we wouldn't need to remember it because of calculators. He was right. Now I wonder if finding integrals is the same today. –  xpda Dec 11 '11 at 16:13
add comment

5 Answers

up vote 31 down vote accepted

You can use the identity $(x+c)^2 = x^2 + 2xc + c^2$ to arrive at a "long-division" like method. Let me show you how it is done for 3838 before giving the algorithm.

  1. Start with 3838
  2. Write the digits in groups of 2, so write 3838 as 38,38.
  3. For the "highest placed group of 2", find the biggest square number less than it. In this case, $6^2 = 36 < 38 < 49 = 7^2$. So you write down 6, and subtract 36 from the first group. You then get
  4. 2,38 = 38,38 - 36,00.
  5. Take the 6 you wrote down before, multiply it by 20 (so you get 120). Now find the largest multiple of $6\times 20$ that is less than 238. You'll see that it is 1. So you write down 1 (so your number is now 61). Subtract from 238 120 to get 118.
  6. Subtract from 118 the number $1 = 1^2$ to get 117. Now add two more digits to it (to form 117.00). Take 61, multiply it by 20, you get 1220. Find the largest multiple of 1220 less than 11700, which would be $1220 \times 9 = 10980$. So write down 9, and your number is 61.9, and subtract from 11700 the number 10980 to get 720. Subtract from 720 the number $9^2 = 81$ to get 639.

So you've arrived at, at this point, $3838 = (61.9)^2 + 6.39$. And you can continue the process indefinitely.

How does this work? Given a number $A$, you want to find its square root in base-10 representation. Suppose your square root looks like $$ a_{100}a_{10}a_1.a_{0.1}a_{0.0.1}\ldots $$ when expanded as a string of digits. Then you find the biggest $a_{100}$ such that $$ (a_{100}\times 100)^2 \leq A $$ (similar to how you do long division). Then to make solve for the next digit, you use that $$ (a_{100} \times 100 + a_{10}\times 10)^2 \leq A $$ (since you are truncating the decimal expansion, which makes the number smaller). So you solve for the best $a_{10}$ such that $$ (a_{100})^2\times 100^2 + \left[ 20 \times (a_{100}\times a_{10}) + (a_{10})^2\right] \times 100 + \leq A $$ The above expression shows why in the first step you want to group the digits in twos: in some sense we are thinking of $A$ as in base-100, the "square" of base-10.

At every step you use the identity $(x+c)^2 = x^2 + 2xc + c^2$ to compute the next digit correction to the square root.


Another method, as the Babylonians did it, was recently detailed by John Baez at his blog, which uses the "equality case" of the arithmetic-mean-geometric-mean inequality to power the iteration.

share|improve this answer
add comment

The best method I know of is the recursive series:$$x_1=b\;\;\;\;\;\;\;\;\;x_{n+1}=\frac{1}{2}\left(x_n+\frac{b}{x_n}\right)$$ It converges very rapidly to $\sqrt{b}$ - for example for b = 3, it is accurate to 7 decimal places after only 4 terms. The long division might not be very easy to carry out strictly with pencil and paper, but it is doable.

share|improve this answer
    
Shouldn't you have an equals sign or assignment operator somewhere in that right expression? –  Puddingfox Dec 11 '11 at 22:09
    
Yup, slipped one key to left. Thanks! –  Drew Christianson Dec 11 '11 at 22:12
    
This answer seems like the simplest one and the one I would be most likely to use when I don't have a calculator handy. –  Puddingfox Dec 11 '11 at 22:19
    
Yea, certainly seems the most practical. I first saw it on exam question beginning "you're on a desert island with only a 4-fucntion calculator and need to calculate $\sqrt{13}$ –  Drew Christianson Dec 11 '11 at 22:25
    
What does this mean? $$x_{n}$$ and $$x_{n+1}$$ –  David Jan 26 '12 at 20:13
show 1 more comment

If your number is close enough to a perfect square, you can use the expansion $$ \sqrt{1+x} = 1 + \frac{1}{2}x - \frac{1}{8}x^2 +- \cdots + (-1)^{n-1}\frac{(2n-3)!!}{2\cdot(2n)!!}x^n+\cdots $$ where $$ (2n)!! = (2n)(2n-2)\cdots4\cdot2,\quad(2n+1)!!=(2n+1)(2n-1)\cdots3\cdot1. $$

A famous physist R. Feynman is said to have used this formula and beat an abacus.

share|improve this answer
    
Exactly. Thanks. –  Pteromys Dec 12 '11 at 0:37
1  
@Pteromys: Feynman actually computed the cube root of $1729$, which is nearly $12$. –  Ganesh Dec 12 '11 at 0:53
    
He'd obviously read Hardy. –  Chris Taylor Dec 15 '11 at 21:27
    
So $\sqrt{37}=1+18-162+-...$? –  Michael Hoppe Jan 31 at 14:05
    
@MichaelHoppe I mean, $\sqrt{36 + 1} = 6\sqrt{1 + 1/36} = 1 + 1/72 -+ \dots$. –  Pteromys Feb 1 at 2:48
show 2 more comments

This comes from Euler's method in approximating solutions to differential equations. This begins with the fundamental notion that the derivative of f(x)=$x^.5$ is equal to f'(x)=$.5x^{-.5}$. So now it is possible to approximate roots. Take the root of 38. The nearest perfect square is 36. so to approximate the square root of 38, you want to take the square root of 36 and then add $2*.5x^{-.5}$. This gives you $6+1/6$ or 6.166666 repeating, which is a pretty good approximation. If you have more specific questions, just ask.

share|improve this answer
add comment

The general form of Newton's Method for zero-finding is \begin{equation*} x_{k+1} := x_k - \frac{f(x_k)}{f'(x_k)} \end{equation*} The Reciprocal Square Root Newton algorithm is obtained by setting $f(x) = \frac{1}{x^2-a}$ and we get \begin{equation*} x_{k+1} := x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{1/x_k^2-a}{-2/x_k^3}=x_k + \frac{1}{2}x_k(1-ax^2_k). \end{equation*} The sequence $\{x_0,x_1, \ldots, x_k, \ldots\}$ converges quadratically, for all $x_0 >0$, to a fixed point $x$. That is \begin{equation*} x = x + \frac{1}{2}x(1-ax^2), \end{equation*} which has two solutions, $x = 0$, and $x = 1/\sqrt{a}$.

We compute $x_{k+1}$ in two steps:

  1. $e_k := 1-a\star x_k\star x_k $
  2. $x_{k+1} := x_k + e_k\star x_k/2$

Here, $e_k$ is the relative error in $x^2_k,$ i.e., $(1/a-x^2_k)/(1/a)=(1-ax^2_k),$ and $e_kx_k/2$ is the correction term.

The most important aspect of this algorithm is that no divisions are required. The division by 2 can be done by bit-shifting. Calculating $x_{k+1}$ requires 3 Mults and 2 Adds. One final multiplication, $a\star x_k$, is done to calculate $\sqrt{a}$.

If a suitable starting value for $x_0$ is chosen, then this algorithm converges to full IEEE double precision in about 5 iterations. An algorithm similar to this is used by Intel in their Itanium processor, whose basic arithmetic operation is the fused multiply-add (FMA) instruction, $z = ax+y$. All other operations are performed using this FMA instruction. For historical reasons, Intel shies away from long division.

See Peter Markstein, IA-64 and Elementary Functions, Prentice-Hall, 2000

Additional Information

The Reciprocal Newton algorithm is obtained by setting $f(x) = \frac{1}{x-a}$ and we get \begin{equation*} x_{k+1} := x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{1/x_k-a}{-1/x_k^2}=x_k + x_k(1-ax_k). \end{equation*}

We compute $x_{k+1}$ in two steps:

  1. $e_k := 1-a\star x_k $
  2. $x_{k+1} := x_k + e_k\star x_k/2$

Here, $e_k$ is the relative error in $x^2_k,$ i.e., $(1/a-x_k)/(1/a)=(1-ax_k),$ and $e_kx_k/2$ is the correction term. Each of these two steps is calculated by a single FMA instruction. The division, $z = y/x$, is calculated as $y\star\frac{1}{x}$. Note how similar this algorithm is to the reciprocal square root algorithm.

Choosing a starting value $x_0$ for the Reciprocal Algorithm is a delicate matter. It can be shown that the domain of convergence is $ 0 < x_0 < \frac{2}{a}$, but this begs the question: what is $\frac{2}{a}$? This is getting into deep water, so I'll leave the answer to Peter Markstein above.

share|improve this answer
add comment

protected by T. Bongers Jan 12 at 19:51

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.