View Single Post
Old 2009-01-16, 12:40   #3
only_human's Avatar
"Gang aft agley"
Sep 2002

2·1,877 Posts

Originally Posted by cheesehead View Post

... 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:

            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:

  x 10111
This was actually my starting point. I took values generated from a multiply routine and decided to defer all the adds until later (maybe never) and then look at how I could represent the values on paper to develop some type of feel for the numbers. I inverted the vertical order of the values so that I could write them in the most familiar form rather than least significant bits first.

Of course the fact that the pattern is also a valid Boolean table is also a direct result of how a multiply is done. As Wikipedia says: computers in base 2 (where multiplying by the single digit of the multiplier reduces to a simple series of logical AND operations).

I have recently reread Wolframs "A New Kind of Science" and with all the Cellular Automata in it I wanted to develop a feel for binary patterns on paper and possibly to assign a more arithmetic meaning to them.

By looking at bits on paper and assigning them this positional value to them I hope to also develop a feel for when they can not be put into the form of a rectangle of a composite number (therefore prime).

I also wanted to fiddle with patterns that are fully filled with a result. The fact that in absolute value hex FF x FF = FE01 leaves me feeling a bit vaguely dissatisfied. I hope by having a representation method that can be fully filled as this one would be for that result might make patterns a bit more meaningful to me. In this 2-d representation, FF x FF would occupy an 8 bit by 8 bit square full of ones. Of course that is devoting 64 bits for a value that could be held in 16 bits in an ordinary product result.

This representation allows other quick visualizations. For example any number (2n+1)2 is represented as a square box of 0s with the four corners set as 1s. Multiplying that with any pattern is directly accomplished with placing a copy of the other pattern down with a bottom right corner where each of the the 1s is. As long as there is no overlap that is the correct result.
I like this form of representation because I can directly read the two factors of any rectangle in the rows and columns. In the ordinary representation of longhand binary multiplication they are there but harder to read because of the shift to keep the magnitudes aligned for addition.

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