Root (EXACT Square Root Algorithm)
philnovi
the patience to use it to.
To view this file properly, convert it/view it with a 'non-proportional'
font (eg Courier New in Windows).
This method was formerly taught in primary school, but the algorithm seems
to be 'getting lost' today!!!
----------------------------------------------------------------------------
--------------------------------------------------------------------------
To find the square root of any number to any number of digits:
****************************************************************************
(This algorithm looks like long division, but a bit more tedious)
Write down the number:
1234567890.
Starting at the decimal point and working to the left, separate the number
into groups of two:
12 34 56 78 90.
leave lots of room to the left:
12 34 56 78 90
Add some notation (pretend these added lines are solid):
________________
| 12 34 56 78 90
1. What is the largest number squared that will subtract from the first
group?
(It is obviously 3 here)
Square this number and perform the subtraction:
3
________________
| 12 34 56 78 90
-9
___
3
(This sequence of digits above the bar will be referred to as the 'top
row'.)
2. Drop down the next group of two digits:
3
________________
| 12 34 56 78 90
| -9
| ___
| 3 34
3. Double the top row and bring this doubled value down to the left,
(we'll call this the left row) leaving a placeholder for a less significant
digit:
3
________________
| 12 34 56 78 90
| -9
| ___
6_| 3 34
4. Now, we need to find the one digit such that the product of this digit
and
the current left row with this digit appended is just less than the result
of
the last subtraction. Put this digit in the placehoder and append it to the
top row.
( i.e. in this particular case, the digit is 5, since 5*65<334, but
6*66>334)
Perform this multiplication and subtraction:
So we now have:
35
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
3 25
____
9
5. Loop starting at step 2 until you have achieved the desired precision.
(continuing the process so you can see the result develop:)
35
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
Step 2: 9 56
35
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
Step 3: 70_| 9 56
Step 4: Next digit is 1 since 1*701<956, but 2*702>956)
351
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
701| 9 56
| 7 01
| ____
| 2 55
continuing on:
351
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
701| 9 56
| 7 01
| ____
702_| 25578
3513
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
701| 9 56
| 7 01
| ____
7023| 25578
21069
_____
4509
3513
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
701| 9 56
| 7 01
| ____
7023| 25578
| 21069
| _____
7026_| 450990
35136
________________
| 12 34 56 78 90
| -9
| ___
65| 3 34
| 3 25
| ____
701| 9 56
| 7 01
| ____
7023| 25578
| 21069
| _____
70266| 450990
421596
______
29394.00
so, at this point, to an approximation, sqrt(1234567890) is 35136.
You are only limited by your patience as to how many digits you require.
Thomas Chrapkiewicz 06ap98
----------------------------------------------------------------------------
--------------------------------------------------------------------------
User wrote in message ...
>
>Does anyone know how to go about doing a square root or cube root
>calculation?
>
>If I gave you a number (no calculators), and a blank piece of paper,
>can you describe the steps one by one how you go about calculating
>the cube or square root? (or any root for that matter).
>
>I also assume I can say... I want it to a precision of 80 decimal points.
>You would go about using your method and you would come up with
>80 decimal points (or less if it rounds off perfectly).
>
>Where can I find procedures on doing this? Is there a very simply
>way to do this? using basic operators (no log sin cos, etc).
>
>Thank you.
>
>Thank you.
>
>
>
Ken Cox
> This method was formerly taught in primary school, but the algorithm seems
> to be 'getting lost' today!!!
For fun, you might want to look what happens when you follow it in
binary. The operations become surprisingly simple.
--
Ken Cox k...@research.bell-labs.com
Gareth McCaughan
> This method for square roots is EXACT for the number of digits that you have
> the patience to use it to.
[SNIP]
It might be worth mentioning that this algorithm works especially
nicely in binary.
If you can do division efficiently, another possibility is to use
Newton's method (though I think this particular application of it
goes back to before Newton): start with any half-decent guess at
the square root and iterate x -> (x+a/x)/2 where a is the thing
whose square root you want.
--
Gareth McCaughan Dept. of Pure Mathematics & Math. Statistics,
Gareth.M...@pobox.com Cambridge University, England.
John Popelish
>
> Thomas Chrapkiewicz wrote:
>
> > This method for square roots is EXACT for the number of digits that you have
> > the patience to use it to.
>
> It might be worth mentioning that this algorithm works especially
> nicely in binary.
>
> If you can do division efficiently, another possibility is to use
> Newton's method (though I think this particular application of it
> goes back to before Newton): start with any half-decent guess at
> the square root and iterate x -> (x+a/x)/2 where a is the thing
> whose square root you want.
AsI recall, I once coded a fast Newton's method square root algorithm
that minimized the number of iterations required by referring to a 256
entry lookup table of guesses, and used the most significant 8 bits as
pointer. There was a little more to it than that, but a good guess can
shorten things considerably.
John Popelish
Randy Poe
philnovi wrote:
>
> This method for square roots is EXACT for the number of digits that you have
> the patience to use it to.
[snip a nice description of the method]
Yep, that's the method I learned. And I believe I saw an
analysis once that shows how it is equivalent to Newton-Raphson,
and how an analogous method can be developed for cube roots.
But on second thought, I'm not sure I believe that connection,
since Newton provably doubles the number of bits of accuracy
at each iteration, and this method converges more slowly.
- Randy
Jack Silver
is one, I haven't run across it yet.
Paul Schlyter
Jack Silver <jsilver...@pti-nj.com> wrote:
> There ought to be a web site or book devoted to these algorithms. If there
> is one, I haven't run across it yet.
--
----------------------------------------------------------------
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pau...@saaf.se paul.s...@ausys.se pa...@inorbit.com
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
philnovi
top soon!
What other types of stuff should be there? Please let me know your
thoughts!
Jack Silver wrote in message <7mf9a5$2g7f$1...@earth.superlink.net>...
John Savard
>Yep, that's the method I learned. And I believe I saw an
>analysis once that shows how it is equivalent to Newton-Raphson,
>and how an analogous method can be developed for cube roots.
I'm not sure I believe that it's that similar to Newton-Raphson
either, but certainly an analogous one for cube roots is possible.
This method is based on the fact that (a+b)^2 = a^2 + 2ab + b^2; the
fact that (a+b)^3 = a^3 + 3a^2b + 3a(b^2) + b^3 leads trivially to the
method for cube roots...
1. 2 5 9
--------------------
2.000 000 000 000
1
--------------------
1 000
6
12
8
--------------------
272 000
216 0
9 00
125
--------------------
56 875 000
25 312 5
303 75
729
--------------------
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
Paul J Gans
>philnovi wrote:
>>
>> This method for square roots is EXACT for the number of digits that you have
>> the patience to use it to.
>[snip a nice description of the method]
>Yep, that's the method I learned. And I believe I saw an
>analysis once that shows how it is equivalent to Newton-Raphson,
>and how an analogous method can be developed for cube roots.
>But on second thought, I'm not sure I believe that connection,
>since Newton provably doubles the number of bits of accuracy
>at each iteration, and this method converges more slowly.
I believe that the method is, in fact, a numerical way
of completing the square.
---- Paul J. Gans [ga...@panix.com]