7
$\begingroup$

If no calculator is allowed, and we want to find the square root of a square number if it is large and analyzing to prime factors is hard, how can one proceed? For example, what to do if the number is a square of a large prime number like 5329?

What are methods to perform this and what are pedagogical reasons to prefer one over the other?

$\endgroup$
  • 1
    $\begingroup$ I agree with @BenjaminDickman. This question is more for MSE. I wonder if it could be rewritten to explore any didactical issues or motivations. $\endgroup$ – Pablo B. Nov 14 '14 at 21:32
  • $\begingroup$ well friends it is just by luck that I wrote the number to be 5329 .. the concept remains the same .. how to find the root of large numers .. I really voted for matin for the link he supplies. thank you all $\endgroup$ – Abdallah Abusharekh Nov 14 '14 at 21:37
  • $\begingroup$ Related: hsm.stackexchange.com/q/56/72 $\endgroup$ – Joel Reyes Noche Nov 14 '14 at 23:39
  • 1
    $\begingroup$ Following the (justified) remarks by @PabloB. and Benjamin Dickman I made explicit the educational aspect in the question, which is already present in some of the answers. $\endgroup$ – quid Nov 15 '14 at 13:26
  • $\begingroup$ There're many methods on wikipedia page. $\endgroup$ – Ruslan Nov 15 '14 at 20:59
14
$\begingroup$

You can use (basically) Newton's method.

Take $x_0>0$, and define $$x_{k+1} = \frac{1}{2} (x_k + \frac{n}{x_k}).$$ The seqeunce converges to $\sqrt{n}$.

And if one starts with $x_0= n$ one has, as soon as $|x_{k+1} - x_k|< 1$, that $\lfloor x_{k+1} \rfloor = \lfloor\sqrt{n} \rfloor$.

But the above is not very feasible for computing by hand, and there is better variant, if you just want to do this for perfect squares or test if something is a perfect square, or more generally compute $\lfloor\sqrt{n} \rfloor$. (It seems this is the case for you.)

You can do $$x_{k+1} = \left \lfloor \frac{1}{2} (x_k + \lfloor \frac{n}{x_k} \rfloor) \right \rfloor$$ only doing arithemtic with integers (including euclidean division). This will converge to $\lfloor\sqrt{n} \rfloor$ in a finite number of iterations.

See Integer Square Root on Wikipedia for further references.

I think this could be an interesting method to teach, as one can provide a good geometric motivation for it.

$\endgroup$
9
$\begingroup$

There is an algorithm to calculate square roots with paper and pencil (like the long division algorithm). See How to calculate a square root without a calculator.

$\endgroup$
  • $\begingroup$ I learned this in grade school. :-) $\endgroup$ – Joseph O'Rourke Nov 15 '14 at 21:13
  • $\begingroup$ @JosephO'Rourke, I learned this in primary school! $\endgroup$ – Martín-Blas Pérez Pinilla Nov 19 '14 at 10:08
3
$\begingroup$

A fancy way, for those who know a little calculus, is to linearize $f(x)=\sqrt{x}$ at some point near the number you want to square root. This can only be done when you can think of a square rootable number that isn't too far away, so it's not going to work if you're trying to square root a super huge number, but if you can think of one, it's very doable by hand, and very quick. It also has the added benefit of giving you a rational approximation, if that's something you want.

For example, to compute $\sqrt{2}$, we first have to come up with some other number that is reasonably close to $2$ which we do know how to square root. The first thing that comes to mind is $9/4$ (though there are many other choices that are even more accurate, e.g. such as $49/25$). We linearize $\sqrt{x}$ at $9/4$: $$\left.\frac{d}{dx}\sqrt{x}\right|_{x=9/4}=\left.\frac{1}{2\sqrt{x}}\right|_{x=9/4}=\frac{1}{2\sqrt{9/4}}=\frac{1}{3}$$ $$\mathcal{L}_{9/4}(x)=f^\prime\left(\frac{1}{3}\right)\left(x-\frac{9}{4}\right)+f\left(\frac{9}{4}\right)=\frac{1}{3}\left(x-\frac{9}{4}\right)+\frac{3}{2}$$ Now, we plug $2$ in there. $$\mathcal{L}_{9/4}(2)=\frac{1}{3}\left(2-\frac{9}{4}\right)+\frac{3}{2}=\frac{17}{12}$$ From here, if you want decimals, you can simply use long division. Numerically, $17/12$ comes out to be $1.41667$, while the actual value of $\sqrt{2}$ is $1.41421\ldots$. That's pretty close, and likely close enough to do the job for many on the fly calculations.

$\endgroup$
  • $\begingroup$ An easy nearby perfect square is always obtainable as the next-lowest or next-highest power of 10 (whichever has an even number of zeros). If you know your powers of two, you can do better using the next-lowest or next-highest power of two. $\endgroup$ – R.. Nov 15 '14 at 17:07
3
$\begingroup$

Use log tables and the identity $x^\alpha = e^{\alpha \log x}$.

From an educational point of view, that gives evidence of the usefulness of logarithms (you can calculate any power of $x$ using just a log table and multiplication) and teaches about transforming between problems. It also allows all roots to be calculated by the same method.

$\endgroup$
2
$\begingroup$

An intuitive approach to find the square root of A is to draw a square with the number (A) in the middle as the area, and the sides labeled x and y. We know that x times y equal A, and x is the square root of A when x = y. Begin with a rough estimate of x and calculate y as A/x. Now replace x with the average of the original x and y, and repeat.

For example, let's find the square root of 200. As a rough guess, let's begin with x = 15. Solve for y = 200/15 = 13.333. The new value for x, call it x1 = (15 + 13.333)/2 = 14.167. Now the new value y1 = 200/14.167 = 14.117. The square root of 200 is between 14.167 and 14.117. The average is 14.142. If we use x2 = 14.142, then y2 = 200/14.142 = 14.142, verifying that we have the square root of 200 with five significant digits.

This approach has the advantage of showing what a square root is visually, which can give a problem more meaning. The process makes intuitive sense, and it does not require mathematics beyond division.

$\endgroup$
0
$\begingroup$

Here is the method I used to solve the original poster's problem in about three seconds:

Square root (5329):

Steps 1a-d estimate the answer, to one significant figure, with the correct order of magnitude:

1a) Start with an estimated answer of 1.

1b) Find the order of magnitude of the answer. Make a copy of the argument (5329). Shift the decimal of the copy of the argument by two places at a time, to get a number between 1 and 100. Shift the decimal of the estimated answer by one place at a time, in the opposite direction. For example, 53.29 and 10.

1c) Assume that the student knows the squares of the integers between 0 and 10 by heart. What is the closest such square? For example, 49.

1d) Multiply the estimated answer by the square root of the closest square. For example, square root (49) = 7, so the new estimated answer is 70.

Step 2 checks the estimate:

2) Square the current estimated answer. For example, 70 * 70 = 4900.

Steps 3a-d refine the estimate using uses (a+b)^2 = a^2 + 2*a*b + b^2. This is a special case of Newton's method:

3a) Subtract the value found in step 2 from the original argument, to yield a remainder. For example, 5329 - 4900 = 429. Keep track of the sign.

3b) Make a copy of the estimated answer. Multiply the copy by 2, to yield a double estimate. For example, 70 * 2 = 140.

3c) Divide the remainder by the double estimate, to yield an adjustment. Round off as convenient. Keep track of the sign. For example, 429 / 140 ~ 3.

3d) Add the adjustment to the estimate (not the double estimate). We kept track of the sign, so that we could correctly choose whether to add or subtract. For example, 70 + 3 = 73. For subsequent calculations, this value replaces estimate.

Repeat steps 2 - 3 until the answer is close enough. For example, 4900 + 420 + 3*3 = 5329, so the square root of 5329 is 73.

Some advantages of this method:

  • I can do it in my head.

  • It only requires keeping track of a few numbers.

  • It quickly produces an estimated answer.

  • It is a special case of Newton's method.

  • Each time through the loop, the student can round off the adjustment to a convenient decimal or fraction.

  • Every iteration, the student checks their work.

Three worked examples:

       Argu-   Estimated   Found                Double     Adjust-  
Step   ment      Answer    So Far  Remainder    Estimate    ment     Notes  
 1a    5329        1  
 1b               10                                                 53.29  
 1c                                                                  7*7=49  
 1d               70
 2     5329       70       4900  
 3a    5329       70       4900       429  
 3b    5329       70       4900       429        140  
 3c    5329       70       4900       429        140          3
 2     5329       73       5329                                 73*73=4900+420+9
Done!

       Argu-   Estimated   Found                Double     Adjust-  
Step   ment      Answer    So Far  Remainder    Estimate    ment     Notes  
 1a     739        1  
 1b               10                                                  7.39  
 1c                                                                  3*3= 9   
 1d               30  
 2      739       30        900
 3      739       30        900       -161        60        -3
 2-3    739       27        729         10        54         0.2
 2-3    739       27.2      739.84      -0.84     54.4      -0.015
 2-3    739       27.185    739.024225  -0.024225 54.37     -0.0005
 2-3    739       27.1845   738.99704025          54.369     0.00005
 2      739       27.18455  738.9997587025
 ...Stop when satisfied...  

       Argu-   Estimated   Found                Double     Adjust-  
Step   ment      Answer    So Far  Remainder    Estimate    ment     Notes  
 1a    4285        1  
 1b               10                                                 42.85  
 1c                                                                  6*6=36   
 1d               60  
 2-3   4285       60       3600       685       120         5
 2-3   4285       65       4225        60       130         0.4
 2-3   4285       65.4     4277.16      7.84    130.8       0.06
 2-3   4285       65.46    4285.0116   -0.0116  130.92     -0.0001
 2-3   4285       65.4599  4284.99850801        130.9198    0.00001
 2     4285       65.45991 4284.9998171081
 ...Stop when satisfied...  
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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