gayde@iwu1b.UUCP (Peter Gayde) (01/27/84)
I saw this recently in GAMES magazine. I didn't believe it at first,
but after many attempts I could only sit back and wonder why it works.
1. Take ANY two numbers: say, 116 and 3011.
2. Halve the first number again and again, discarding any fractional
remainder, until you reach 1. Thus: 116, 58, 29, 14, 7, 3, 1.
3. Double the second number as many times as you halved the first.
Thus: 3011, 6022, 12044, 24088, 48176, 96352, 192704.
4. Write these series alongside each other, and cross out every even
number in the HALVES column and its partner in the DOUBLES column.
Thus, as shown below, the even numbers in the HALVES column (116,
58 and 14) are crossed out along with their companions in the
DOUBLES column (3011, 6022 and 24088) REGARDLESS OF WHETHER THESE
ARE EVEN OR ODD.
HALVES DOUBLES
116 xxx 3011
58 xxx 6022
29 12044
14 xxx 24088
7 48176
3 96352
1 192704
5. Add the numbers that remain in the DOUBLES COLUMN ONLY. The
resulting sum will be equal to the product of the two numbers you
started with.
12044 + 48176 + 96352 + 192704 = 349276 = 116 x 3011 !!!!!!!
Does anyone have any inkling as to why this works?
--
Peter Gayde ihnp4!{iwu1b,ihuxp}!gayde
AT&T Technologies
Naperville, IL
(312) 979-7186halle1@houxz.UUCP (J.HALLE) (01/27/84)
Convert the original halved number into binary. Stare for a few minutes. The answer should become clear.
wjhe@hlexa.UUCP (01/27/84)
By repeatedly halving (dividing by two), you are essentially constructing
the binary representation of the number from right to left (0-th power
of 2 to 6-th power of 2), with even numbers in the HALVES column
corresponding to 0 and odd to 1: 116 = 1110100 (base 2). The doubling
in the right hand column corresponds to multiplying the original number
by the corresponding power of 2. Therefore, adding the non-xxx-ed
entries in DOUBLES is really just multiplying 3011 by the term by term
binary representation of 116:
116*3011 = (2**6 + 2**5 + 2**4 + 2**2)*3011
Bill Hery
ATT Bell Labs, Short Hils
201-564-3352kenner@cmcl2.UUCP (01/28/84)
#R:iwu1b:-11400:cmcl2:8200001:000:109 cmcl2!kenner Jan 27 18:54:00 1984 Essentially what you are doing is a long multiplication with one operand in BINARY and the other in decimal.
darrelj@sdcrdcf.UUCP (Darrel VanBuer) (01/28/84)
This halving and doubling, then cross-out evens, add what's left to
multiply is done billions of times every day by computers around the
world. (It's much more obvious if you write the numbers in binary, then
it looks just like old long multiplication you learned in school, only for
binary).
You can also use this successive halving to convert a number to
binary, cross outs are 0s, numbers left are 1s and most significant bit
comes last in operations.
--
Darrel J. Van Buer, PhD
System Development Corp.
2500 Colorado Ave
Santa Monica, CA 90406
(213)820-4111 x5449
...{allegra,burdvax,cbosgd,hplabs,ihnp4,sdccsu3,trw-unix}!sdcrdcf!darrelj
VANBUER@USC-ECL.ARPAjames@umcp-cs.UUCP (01/29/84)
Yes, it works. Think of it this way: you start with two numbers, whose product you are going to construct. I'll call these numbers A and B. A*B is "A groups of B". If A is even, that is "A/2 groups of 2B", so you can see that anytime you halve the left number and double the right number, their product is equal to the product of the numbers immediately above them (in your columns). This means you should scratch out the numbers above them IN THIS CASE, WHEN the previous A was even! When the left number is odd, A * B == (A-1)/2 * 2B + B, so you need that extra B immediately above the new 2B in the DOUBLES column, to allow for the remainder you ignored when halving A. --Jim
hopp@nbs-amrf.UUCP (01/29/84)
Subject: Re: Math for Smart Alecks
Newsgroups: net.math
Reference: <114@iwu1b.UUCP>
I saw this recently in GAMES magazine. I didn't believe it at first,
but after many attempts I could only sit back and wonder why it works.
1. Take ANY two numbers: say, 116 and 3011.
2. Halve the first number again and again, discarding any fractional
remainder, until you reach 1. Thus: 116, 58, 29, 14, 7, 3, 1.
3. Double the second number as many times as you halved the first.
Thus: 3011, 6022, 12044, 24088, 48176, 96352, 192704.
4. Write these series alongside each other, and cross out every even
number in the HALVES column and its partner in the DOUBLES column.
Thus, as shown below, the even numbers in the HALVES column (116,
58 and 14) are crossed out along with their companions in the
DOUBLES column (3011, 6022 and 24088) REGARDLESS OF WHETHER THESE
ARE EVEN OR ODD.
HALVES DOUBLES
116 xxx 3011
58 xxx 6022
29 12044
14 xxx 24088
7 48176
3 96352
1 192704
5. Add the numbers that remain in the DOUBLES COLUMN ONLY. The
resulting sum will be equal to the product of the two numbers you
started with.
12044 + 48176 + 96352 + 192704 = 349276 = 116 x 3011 !!!!!!!
Does anyone have any inkling as to why this works?
Yes. This works because it is the standard algorithm for doing multiplication
in binary representation.
To see this, consider first the usual algorithm for deriving the binary
representation of a number (say, 116). You start with the number and
continually halve it until you get zero. While halving it, write the
remainder of each division to the left of the number. The binary rep. is
then read off from bottom to top:
Remainder Halves
--------- ------
0 116
0 58
1 29
0 14
1 7
1 3
1 1
0
^
|
\---- Binary rep. of 116 is 1110100.
Now consider the longhand multiplication of two numbers in binary (say,
116 x 3011):
101111000011 (= 3011)
x 1110100 (= 116)
------------
0
0
101111000011
0
101111000011
101111000011
101111000011
------------------
1010101010001011100 (= 349276 = 116 x 3011)
Note that each time there is a 1 in the rep. of 116, the rep. of 3011 is
added in after being shifted left the appropriate amount. Since each one-
digit shift left in binary represents a doubling of the number, the product
can be obtained by doubling 3011 and adding those multiples corresponding
to rows where there is a 1 in the rep. of 116. Since these are just the
rows with odd submultiples of 116, the algorithm in the game follows easily.
Ted Hopp seismo!rlgvax!cvl!umcp-cs!nbs-amrf!hopp
National Bureau of Standards
Metrology A127
Washington, DC 20234
301/921-2461rehmi@umcp-cs.UUCP (01/30/84)
That is the standard binary multiplication shift_and_add algorithm.
In odd trappings.
-rehmi
--
By the fork, spoon, and exec of The Basfour...
Arpa: rehmi@{maryland,umd-csd} /* currently reliable */
CsNet: rehmi.umcp-cs@csnet-relay
Uucp:...!harpo!seismo!umcp-cs!rehmi
...!{allegra,brl-bmd}!umcp-cs!rehmirjnoe@ihlts.UUCP (Roger Noe @ N41:48:31, W88:07:13) (01/30/84)
>This halving and doubling, then cross-out evens, add what's left to >multiply is done billions of times every day by computers around the >world. > Darrel J. Van Buer, PhD Well, I don't know. I hate to be picky, but I really don't think there are very many computers that still do shift-and-add for multiplication. At the very LEAST, I hope they use Booth's unmodified algorithm. Roger Noe ihnp4!ihlts!rjnoe
dave@fluke.UUCP (Dave Van Ess) (01/30/84)
I'd like to expand a little farther on Terry Ligocki's explaination of
the "Smart Aleck Multiplication" algorithym. Terry is correct in saying that
it is just a binary shift and add routine. What makes this routine special
is that the operations on each of the number are independent of each other.
The first number need only to be divided by 2 and have oddness determined,
while the second number is only doubled and totaled. This independence frees
the two numbers from having the same base. As an example the following
operation would not be difficult.
ff * 19 = 4845
hex bcd bcd
All that is needed is, a halfing routine for the first number ( shift right ), a
way of determining oddness in the first number ( the zero bit ), a way of
determining a zero for the first number, and a bcd adding routine for the second
number. Below is the algorithym stated for the general case.
X * Y = Z
a b b
Zb= 0b
while ( Xa != 0a ) {
if ( Xa is odd ) {
Zb = Zb + Yb
}
Xa = Xa / 2a
Yb = Yb + Yb
}
This algorithym can be useful where some value needs to have it's base changed
but also needs to be normalized.
Dave Van Ess
John Fluke Mfg. Co.
Everett Wacarl@sdcsvax.UUCP (Carl Lowenstein) (02/06/84)
Surely, as a computer user, you have heard of the binary system. The algorithm cited multiplies two numbers as if they were expressed in base-two notation, while displaying them in base ten.