Re: Decimals

Roland Hutchinson:
Which square root method did you learn?...the one that
resembled long division, or...

Chuck Riggs:
My classmates and I were taught the laborious one in grade
school...

James Silverton:
I never thought that "long division" method was hard work. I think it's
based on a power series approximation...

No, it's based on the same principle as long division, only the
hidden algebraic expression that you never actually see yourself
evaluating is based on (10A+B)^2 instead of (10A+B). You can do
higher roots the same way, using (10A+B)^n, although the amount
of computation increases considerably.

Here (copyedited a bit) is how I wrote this up for another newsgroup
on another occasion:

-----------------------------------------------------------------------------

Consider what you're doing when you do long division. At each stage
you work with what we might call a "local dividend" D, which is
initially the left-hand part of the real dividend. If the divisor
is d, you then find the largest digit x such that r >= 0, where
r = D - x*d. You then compute the next local dividend as 10*r + n,
where n is the next digit of the real dividend. The successive
digits x make up the quotient.

Well, finding a square root on paper works almost the same way.
For greater parallelism with long division I'll call the number whose
square root you want to find the "pseudo-dividend". You split this
into pairs of digits leftward and rightward from the decimal point.
The first "local dividend" D is just the leftmost such group of
digits, e.g. 4 for 47612 (with an odd number of digits) but 47 for
476121 (with an even number).

At each step, let s be the string of digits already found for
the square root. Now find the largest digit x so that r >= 0,
where r = D - x*(20*s + x). In other words, instead of a fixed
divisor d, you use the amount 20*s+x: call that a pseudo-divisor.
It is convenient to think of this as 2*s with the digit x appended.
(Note that on the first step, no digits have been found, so s is
0 and x is just the integer part of sqrt(D).)

Then form the next "local dividend" as 100*r + N, where N is the
next TWO digits of the pseudo-dividend. Then continue until you
have enough digits (stopping if it comes out evenly on the last
digit, of course).

Worked example: sqrt(696223.36) = 834.4. The numbers written down
the left-hand side are the pseudo-divisors 20*s+x.

8 3 4. 4
+------------
8 | 69 62 23.36
64
-------
163 5 62
4 89
--------
1664 73 23
66 56
---------
16684 6 67 36
6 67 36
---------

To go over the third step explicitly, s, the digits obtained so far
in the square root, is 83. Double that to make 166; now consider
1660*0, 1661*1, 1662*2 ... 1669*9. Here 1664*4 = 6656, which is
<= 7323, but 1665*5 = 8325, which is too big. So the next digit is 4.
Write down the 6656, form r = 7323 - 6656 = 667, bring down 36 from
the original number (pseudo-dividend) to make 66736, the next local
dividend, and continnue on to the fourth step. The fourth step
happens to be the last, because 834.4 is the exact square root.

What's actually going on here, if you think about it, is that
you're obtaining the square root by resolving 696223.36 into a sum
of terms like this:

(800^2) + (830^2 - 800^2) + (834^2 - 830^2) + (834.4^2 - 834^2).

Note that each term is the difference between a better approximation and
the sum after the previous term. The 4 terms here work out to

640000 + 48900 + 6656 + 667.36

and you can see those numbers, with the trailing zeroes removed, in the
long-form calculation.


You can also do higher Nth roots by this method, though it's likely to
be significantly more work than other methods. I wouldn't have attempted
the example below if I didn't have a computer to evaluate the expressions
as I typed them in! You use groups of N digits instead of pairs, and the
general form of the pseudo-divisor becomes ((10*s+x)^N - (10*s)^N)/x.

Note that for N > 2 you'll actually have to work out the pseudo-divisors
in full, or at least the dominant terms, rather than just doing 2*s and
appending x; that's where the major work comes in.

Here's an example with N = 4 (which could be done more easily with
successive square roots). The expression for the pseudo-divisor
works out to 4000*s^3 + 600*s^2*x + 40*s*x^2 + x^3, or perhaps
more conveniently, 4*(10*s)^3 + 6*(10*s)^2*x + 4*(10*s)*x^2 + x^3.
We'll do the 4th root of 4294967296, a number that some of you may
recognize.

2 5 6
+-------------
8 | 42 9496 7296
16
-------
46125 26 9496
23 0625
------------
64786216 3 8871 7296
3 8871 7296
-----------

In the second step, the digit 5 was obtained by evaluating
(4000*2^3 + 600*2^2*5 + 40*2*5^2 + 5^3 = 46125) * 5 = 230625
and (4000*2^3 + 600*2^2*6 + 40*2*6^2 + 6^3 = 49496) * 6 = 296976

or if you prefer, the equivalent:
(4*20^3 + 6*20^2*5 + 4*20*5^2 + 5^3 = 46125) * 5 = 230625
and (4*20^3 + 6*20^2*6 + 4*20*6^2 + 6^3 = 49496) * 6 = 296976

The second result is too large,and the first isn't, so 5 is the
choice. The rest of the working is similar.

Again, what's really going on here is that we're expressing
4294967296 as

(200^4) + (250^4 - 200^4) + (256^4 - 250^4),

which is just 1600000000 + 2306250000 + 388717296.
--
Mark Brader "I already checked, and there are 2147483647
Toronto natural numbers (I made a simple Java program
msb@xxxxxxx to count them)." -- Risto Lankinen

My text in this article is in the public domain.
.

Relevant Pages

  • Re: irrational number continuum
    ... do not prove the existence of denumerable sequences. ... square root od 2 in order to do useful calculations with that "notion" ... in a finite number of digits" (either in the case of dec. rep. of 1/3 ... I don't always compute with only approximations. ...
    (sci.logic)
  • Re: Newbie question(s)...
    ... > It is not true that the digits in an irrational numbers are ... is the square root of 3 in base 2... ... have zero mean XOR the plaintext and key, ...
    (sci.crypt)
  • Re: Special factorization method sought
    ... The user specifies the number of decimal digits desired, ... After that number-of-digits and high-order prefix is ... close as to make factorization by square root method practical. ... close, for the range of the first prime, instead of taking the full ...
    (sci.crypt)
  • Re: Pi with bad calculator
    ... little piece of grocery store calculator whose ... extravagance doesn't go beyond a mere square root ... allowing you to get 7 digits of precision through memorisation of a mere ... It does need the square root button. ...
    (sci.physics)
Loading