mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2009-01-16, 08:53   #1
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default 2-d binary representation

This isn't quite mathematics but is a bit pretty.
  • 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
The pattern written in this representation will have a total value equal to the product of the row value times the column value.

Taking a number, e.g. 23 in base ten is "10111" in binary and and using it both horizontally and vertically creates this:
Code:
10111
00000
10111
10111
10111
These bits add up to 23 squared 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. This is faithful to ordinary binary representation in that any bit to the left (or up) is more significant than any bit to the right (or below). I think of writing binary numbers this way as a canonical representation because the rows can be generated from a traditional binary multiply routine (without doing any adding and with trailing 0s that are only implicitly here by position) and also because it is a valid Boolean truth table:
Code:
& 10111
1 10111
0 00000
1 10111
1 10111
1 10111
These 2-d canonical representations are products of 2 factors found along rows and columns. When the factors are equal, the result is a representation of a square. I started to think about this representation as an attempt develop a little intuition about numbers. These 2-d patterns can be quickly be drawn. They can be extended into 3-d representations easily enough with three factors directly readable on the edges of length, width, and height.

With regards to squares (values that total up to n2 -- not merely square sized portions on paper), the pattern on its' edges is also found on its' main diagonal (top-left to bottom-right diagonal); once a square is drawn, smaller valid squares are contained within it on the the top-left to bottom-right diagonal if they include either the most significant bit or the least significant bit and contain a "1" in the opposite corner. These smaller squares, like the original square, consistently have a single pattern in all non-zero rows and columns. Alas, if one of these smaller squares is directly erased, what is left behind is no longer a canonical representation of a product.

What does all this twiddling around allow me to see? Initially not much; however it lets me draw a rectangle around a random bunch of 1s and 0s and ask myself if it can be rearranged into a canonical representation of a product. Looking at the positional representation, several locations have the same value. Two "1"s in a less significant valued position can be moved up or left if they are combined into a single "1", etc. Also, the maximum value containable is equal to the product of maximum value containable along its' edges (one edge per dimension of course)

Last fiddled with by only_human on 2009-01-16 at 09:17 Reason: note: correct ambiguity about squares
only_human is offline   Reply With Quote
Old 2009-01-16, 12:05   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 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
Old 2009-01-16, 12:40   #3
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default

Quote:
Originally Posted by cheesehead View Post
Multiplication!

... 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
---------
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). http://en.wikipedia.org/wiki/Multiplication_algorithm

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
Old 2009-01-16, 17:35   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by only_human View Post
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.
I've read it, too. (Well, part way through -- then I browsed.) The trap Wolfram seems to have fallen into (based on my reading and the comments of others) was getting so wrapped up in his own interpretation of his patterns that he neglected to adequately check back with others' results, before publishing, to find out whether he had reinvented the wheelbarrow.

Quote:
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.
Does 99 x 99 = 9801 or any other (b-1) x (b-1) = b2 - 2b + 1 leave you dissatisfied?

Quote:
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.
... because your representation shows all the intermediate steps before the final summation, whereas the product shows only what's left after the summation.
cheesehead is offline   Reply With Quote
Old 2009-01-16, 20:40   #5
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Does 99 x 99 = 9801 or any other (b-1) x (b-1) = b2 - 2b + 1 leave you dissatisfied?
Yes. I understand the reason involved.
I am aware that the total discussion is merely exploring a representation system (and about as obvious of one as possible) and not any direct intrinsic property of numbers themselves. I picked the one that allows numbers to be written in the most familiar way of m.s.b. to l.s.b. of traditional reading order. That is why I said that it is not really mathematics. This is also why I picked this particular subforum to place the thread.

Quote:
... because your representation shows all the intermediate steps before the final summation, whereas the product shows only what's left after the summation.
Yes. Essentially I just tried to be a little more compact than plopping down N grains of rice to represent N. No calculation is done. No adding. No carries. I merely organized it such that a product can be written with one factor along each of its dimensional borders. That allows reading the factors on the edges in a glance. Of course the factors must be known to draw it that way. But it suggests drawing a border around a mess of 1s and 0s and asking oneself if any manipulation of the interior can move the bits such that it can be turned into what I called the canonical form (with factors along the borders and the entire content a valid Boolean "And" table as is intrinsic to the implied binary long multiplication). This is intended to develop a feel about numbers themselves. There are obvious mathematical rules about how to move the 1s around such as that they double or combine when moving to adjacent magnitude positions.

Last fiddled with by only_human on 2009-01-16 at 21:02
only_human is offline   Reply With Quote
Old 2009-01-18, 13:08   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

Ok, now that this thread has sat here for a couple of days, here are some things that I am a bit more tentative about and really are excursions in using 2D binary patterns as a starting point to think about things.

Bits of equal magnitude are found on the diagonals from bottom left to top right. In a 2D square shaped region, there is one more bit available to each higher magnitude until the diagonals start decreasing in length:
1·20
1·20 + 2·21 + 1·22
1·20 + 2·21 + 3·22 + 2·23 + 1·24
etc.

On 3D representations, absent what happens at the boundary when coefficients begin decreasing, the coefficients seem to be triangular numbers (the coefficient found after first two entries in a row of Pascal's triangle). With a cube that has 4 bits per side, the maximum representable value is 153 with this number of bits per magnitude:
1·20 + 3·21 + 6·22 + 10·23 +12·24+ 12·25 + 10·26 + 6·27 + 3·28 + 1·29

Looking at http://en.wikipedia.org/wiki/Multiplication_algorithm, these 2D representations resemble the section labeled "Lattice Multiplication" except each grid point represents 1 bit by 1 bit binary multiply thus no space for a carry is needed for that digit in the binary version of Napier's Bones. Of course plenty of carries are needed when adding up the bits along the diagonals.

Looking at a 2D rectangle and the above link for Karatsuba multiplication:
Quote:
For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems may employ Karatsuba multiplication, which was discovered in 1960 (published in 1962). The heart of Karatsuba's method lies in the observation that two-digit multiplication can be done with only three rather than the four multiplications classically required. Suppose we want to multiply two 2-digit numbers: x1x2· y1y2:

1. compute x1 · y1, call the result A
2. compute x2 · y2, call the result B
3. compute (x1 + x2) · (y1 + y2), call the result C
4. compute C − A − B,call the result "K"; this number is equal to x1 · y2 + x2 · y1.
5. compute A · 100 + K · 10 + B
Step 5 above was of course written for base ten. Looking at a 2D pattern that I have been calling canonical (a result of a long form multiply but without any of the partial products added but rather simply placed in magnitude positions as described in my first message in the thread), we can break the 2D pattern into 4 regions. The top left region, in isolation corresponds to result A. The bottom right region, corresponds to result B. Region D is x1 · y2, E is x2 · y1. D + E = K. The shifting of step 5 has already been done by the placement of the regions on the 2D grid. None of the optimization of Karatsuba multiplication has been done, I merely am pointing out what each region corresponds to.

Code:
*  x1 x2
y1| A E
y2| D B
Another thing I am thinking is since no adds or carries are done at the point that these 2D representations are plopped down on paper, maybe the representation has use for thinking about coefficients of polynomials products instead of mere numerical products.

Last fiddled with by only_human on 2009-01-18 at 13:51 Reason: make more concise
only_human is offline   Reply With Quote
Old 2009-02-21, 01:49   #7
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

"Step 5 above was of course written for base ten." in the previous message is incorrect. Step 5 is valid for any positive integer base.

The primary reason to in use base 2 for these 2-D representations is so that they could be written with factors on the edges. Also, as explained by Cheesehead and me, each position can correspond to a single digit multiply of multiplier and multiplicand in the fully expanded long multiplication of two factors.

Part of what possibly makes this an intelligible way to represent numbers is that the single binary digit multiplies do not generate carries. (So a 2-D pattern that is the result of a long multiply can be written with a single digit result for each single digit multiply-- deferring all adds to later, or never)

There is a base 3 representation of numbers that also does not generate carries as a result of a single digit multiply: Balanced ternary

Each digit in balanced ternary can be -1, 0, or 1

Rather than representing -1 by using a bar over or under a '1' I am going to use an underscore by itself. I am using these 2-D representations as a way to think about numbers and by using the underscore by itself I gain a small convenience in writing the number and thinking about it. The reason is that if I take a 2-D representation with the most-significant digit in the top-left corner and the least-significant digit in the bottom-right corner, I can visualize holding those two corners and flipping the number over that diagonal axis. Mentally I allow myself to think of the '_' symbols becoming '1's and vice versa. The aggregate value of the pattern changes sign when this is done. If the flipped pattern is added to the original pattern, the result is 0. Flipping the 2-D binary patterns mentioned earlier in the thread in a similar manner does not change the value of the pattern because the flipped 1s are kept as 1s (no symbol change is considered) and in all cases of 2-D representations of a flip over this diagonal axis the source and destination digits have equal magnitude positions.

(more later)
only_human is offline   Reply With Quote
Old 2009-02-21, 08:02   #8
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

1110101010102 Posts
Default

"Third Base" (Chapter 10 of GROUP THEORY IN THE BEDROOM, and Other Mathematical Diversions by Brian Hayes (2008 pp 179-200, Hill and Wang)) is on Base 3 number systems and Thue sequences, originally written by him in his "Computer Science" column for American Scientist: http://www.americanscientist.org/issues/pub/third-base/, with an added afterthought on Thomas Fowler's balanced ternary calculating machine (1840!). Also added are thoughts on use of ternary in taxonomic classification trees and the Thue sequence actually studied by Axel Thue rather than the one Brian Hayes initially had illustrated in the American Scientist. Both sequences use the same substitution scheme: 0->12, 1->102, 2->0.

The scheme originally illustrated in the American Scientist starts with these stages 0,12,1020,10212012, etc. Each following stage is twice as long as the previous stage. The book's Chapter 10 afterward sequence starts with the symbol '1' and looks like this: 1, 102, 102120, 102120102012. It has the additional property that each stage is a prefix to the following stage (and the lengths double per stage but starting from a length of 3 in the 2nd stage rather than a length of 2 in that stage of the other sequence).

Knuth talks about balanced ternary in The Art of Computer Programming. Vol. 2, Seminumerical Algorithms 2nd ed. pp. 190-193 or 3rd ed. pp. 207-209.

Last fiddled with by only_human on 2009-02-21 at 08:06
only_human is offline   Reply With Quote
Old 2009-02-21, 20:01   #9
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Balanced ternary seems frustratingly close to a useful alternative to binary in these two dimensional patterns that I am examining. One problem is symbols; if I use either a vinculum (overscore) or an underscore to represent -1, the mark is close to vertically adjacent symbols. The first 5 positive numbers squared using underscored '1's:
Code:
                        111
       11    10    11   111
  1    11    00    11   111
Adjacent underscore symbols without accompanying '1's are adequate on grid paper scratchings but run together horizontally in computer fonts. Using the minus sign collides with its' ordinary usage in subtraction.

The factors of a product are on the pattern edges. Looking at the second square above, the top and left edges represent the value two, but the bottom and right edges hold the value negative two. The basic situation is that the corners share a symbol between the two factors being multiplied. So for these 2D patterns, one factor may end in a symbol that is used for the start of the other factor; also viable is that both numbers share a most significant symbol in a corner as in the representation of 2 squared above. In that number two is "11" and the factors are found on the top and left sides (note negative two is found on the bottom and right sides). There is no representation for some negative products. If you look at 52 above, the sides represent 5 (top or left) or -5 (bottom or right). Negating the entire pattern does make a pattern that sums correctly to -25 but it is an invalid pattern for a product (the center symbol is not correctly a product of the corresponding edge factor symbols. This is expected as no squared integer results in a negative product. Using red for the -1 valued symbols:
Code:
111 This invalid pattern but was made by negating the symbols in the 52 pattern.
111
111
Here is a cheat sheet of all the 3 symbol values:
Code:
-13,-12,-11,-10, -9, -8, -7, -6, -5, -4, -3, -2, -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13
111,110,111,101,100,101,111,110,111, 11, 10, 11,  1,  0,  1, 11, 10, 11,111,110,111,101,100,101,111,110,111
One problem with using colored symbols is difficulty with casual cut & paste editing.

Lets try to examine the 2D pattern for 5 x -8.
Laying out these patterns I choose to place the negative 8 at the top and the 5 on the right side:
Code:
101
?01
101
The center symbol could be determined by the single digit multiply of the middle symbols on the top and right edges. However it can also be determined (as can the bottom edge middle symbol) by knowing that any symbol multiplied by 0 is 0; thus zeros on edges make 0 filled rows or columns. The bottom left corner symbol is determined by multiplying the top left and bottom right symbols. Knowing that the 5 x -8 pattern must total -40, and that the defined locations total -67, I know that the left edge middle symbol must be a '1' to represent 27.
Code:
101
101
101
The end result is that the top and right side represent 5 x -8 as can be seen by direct inspection of the edge. The left and bottom represent -5 x 8. This is consistent mathematically and each interior symbol of the pattern is determined by using the edges as if they were the borders of a multiplication table.
The crucial thing is that a corner represents the most significant bit in one of the factors and also the least significant bit in the other factor or its' negation.

Does this restriction of sharing a digit between factors or their negation on the corners prevent some products from being drawn in these 2D patterns? I haven't checked yet, it should be easy enough to examine but this message is already long and I am taking a break.

Other people are welcome to post in this thread. In general I interpret silence as either kindness, a lack of interest, or that I haven't said much worthy of a reply. In all these cases I do appreciate not having been taken too hard to task for my possibly vacuous musings.

Last fiddled with by only_human on 2009-02-21 at 20:30
only_human is offline   Reply With Quote
Old 2009-02-23, 00:11   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by only_human View Post
One problem is symbols; if I use either a vinculum (overscore) or an underscore to represent -1, the mark is close to vertically adjacent symbols.
I agree that negative digit representation is a problem. It could be that we need to invent an entirely new symbol -- something evocative of both "1' and "-", but not identical to any existing symbol (at least, outside of Wingdings :). Or maybe it could be a struck-through "1" = 1. (We'd depend on context to distinguish that from a "1" that had been struck-through to indicate deletion of that digit.)

Quote:
Other people are welcome to post in this thread. In general I interpret silence as either kindness, a lack of interest, or that I haven't said much worthy of a reply.
In my case, I've been skipping this particular subforum ("Miscell ...") for a while. Now that I see your latest work, I'll need some time to contemplate it before saying anything useful.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
very long binary representation to decimal davar55 Programming 24 2014-12-07 00:19
Representation by quadratic forms Raman Math 0 2013-01-04 00:29
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Representation of integer as sum of squares kpatsak Math 4 2007-10-29 17:53
Binary representation prime number of 1's. TTn 15k Search 0 2004-12-18 21:10

All times are UTC. The time now is 04:36.

Sun May 31 04:36:32 UTC 2020 up 67 days, 2:09, 1 user, load averages: 1.41, 1.65, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.