View Single Post
Old 2009-01-16, 12:05   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by only_human View Post
This isn't quite mathematics
False modesty. Of course it's mathematics!

Quote:
  • write a binary number
  • pick another binary number and write it vertically starting with every "1" in the first number
  • every space not explicitly written in this rectangle contains a 0
... and if you were to do standard binary long multiplication, you'd find that you would write the same sequences of 0s and 1s one after the other in each intermediate row (before the final sum), except that the rows would occur in the opposite order, and each row would be shifted left one place from the row above it.

Quote:
The pattern written in this representation will have a total value equal to the product of the row value times the column value.
Multiplication!

Quote:
when added using the positional values for each "1" as listed below.

The positional values in this represent:
Code:
28 27 26 25 24
27 26 25 24 23
26 25 24 23 22
25 24 23 22 21
24 23 22 21 20
The most significant bit is in the top left corner. The least significant bit is in the bottom right corner.
... and if you flip that matrix vertically, then shift each row one place to the left from the row above it, you find that the powers of 2 would match up exactly with the value of each bit in the long-multiplication intermediate rows, like this:

Code:
            24 23 22 21 20
         25 24 23 22 21
      26 25 24 23 22
   27 26 25 24 23
28 27 26 25 24
So, the 232 looks like:

Code:
    10111
  x 10111
---------
    10111
   10111
  10111
 00000
10111
---------
Now, notice that in your powers-of-2 matrix, each power is repeated along an upper-right to lower-left diagonal, the same number of times that that power of 2 can occur in the intermediate lines of the long division. That is, the 20 occurs just once, and in the long multiplication it occurs only as the rightmost bit of the top intermediate row. The 21 occurs twice on the next higher diagonal, and in the long multiplication it occurs as both the next-to-last bit of the top intermediate row and the last bit of the second intermediate row, which are in the same vertical column there. And so on.

Each diagonal in your powers-of-2 matrix corresponds to a vertical column across the intermediate lines of a standard long multiplication. The number of powers-of-2 added up along a diagonal of your matrix is the same as the number of powers-of-2 added up in the corresponding column of the intermediate lines of long multiplication.

But your bit-products matrix is more compact than long multiplication's intermediate lines with their shifted rows and their unused spaces at upper left and lower right, as can be seen above.

Last fiddled with by cheesehead on 2009-01-16 at 12:13
cheesehead is offline   Reply With Quote