20090116, 08:53  #1 
"Gang aft agley"
Sep 2002
3754_{10} Posts 
2d binary representation
This isn't quite mathematics but is a bit pretty.
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 The positional values in this represent: Code:
2^{8} 2^{7} 2^{6} 2^{5} 2^{4} 2^{7} 2^{6} 2^{5} 2^{4} 2^{3} 2^{6} 2^{5} 2^{4} 2^{3} 2^{2} 2^{5} 2^{4} 2^{3} 2^{2} 2^{1} 2^{4} 2^{3} 2^{2} 2^{1} 2^{0} Code:
& 10111 1 10111 0 00000 1 10111 1 10111 1 10111 With regards to squares (values that total up to n^{2}  not merely square sized portions on paper), the pattern on its' edges is also found on its' main diagonal (topleft to bottomright diagonal); once a square is drawn, smaller valid squares are contained within it on the the topleft to bottomright 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 nonzero 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 20090116 at 09:17 Reason: note: correct ambiguity about squares 
20090116, 12:05  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
False modesty. Of course it's mathematics!
Quote:
Quote:
Quote:
Code:
2^{4} 2^{3} 2^{2} 2^{1} 2^{0} 2^{5} 2^{4} 2^{3} 2^{2} 2^{1} 2^{6} 2^{5} 2^{4} 2^{3} 2^{2} 2^{7} 2^{6} 2^{5} 2^{4} 2^{3} 2^{8} 2^{7} 2^{6} 2^{5} 2^{4} Code:
10111 x 10111  10111 10111 10111 00000 10111  Each diagonal in your powersof2 matrix corresponds to a vertical column across the intermediate lines of a standard long multiplication. The number of powersof2 added up along a diagonal of your matrix is the same as the number of powersof2 added up in the corresponding column of the intermediate lines of long multiplication. But your bitproducts 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 20090116 at 12:13 

20090116, 12:40  #3  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
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 2d 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 (2^{n}+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 20090116 at 13:36 

20090116, 17:35  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:
Quote:


20090116, 20:40  #5  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
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:
Last fiddled with by only_human on 20090116 at 21:02 

20090118, 13:08  #6  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
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·2^{0} 1·2^{0} + 2·2^{1} + 1·2^{2} 1·2^{0} + 2·2^{1} + 3·2^{2} + 2·2^{3} + 1·2^{4} 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 15^{3} with this number of bits per magnitude: 1·2^{0} + 3·2^{1} + 6·2^{2} + 10·2^{3} +12·2^{4}+ 12·2^{5} + 10·2^{6} + 6·2^{7} + 3·2^{8} + 1·2^{9} 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:
Code:
* x1 x2 y1 A E y2 D B Last fiddled with by only_human on 20090118 at 13:51 Reason: make more concise 

20090221, 01:49  #7 
"Gang aft agley"
Sep 2002
2×1,877 Posts 
"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 2D 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 2D 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 2D 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 2D representation with the mostsignificant digit in the topleft corner and the leastsignificant digit in the bottomright 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 2D 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 2D representations of a flip over this diagonal axis the source and destination digits have equal magnitude positions. (more later) 
20090221, 08:02  #8 
"Gang aft agley"
Sep 2002
3754_{10} Posts 
"Third Base" (Chapter 10 of GROUP THEORY IN THE BEDROOM, and Other Mathematical Diversions by Brian Hayes (2008 pp 179200, 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/thirdbase/, 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. 190193 or 3rd ed. pp. 207209. Last fiddled with by only_human on 20090221 at 08:06 
20090221, 20:01  #9 
"Gang aft agley"
Sep 2002
2×1,877 Posts 
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 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 5^{2} 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 5^{2} pattern. 111 111 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 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 Code:
101 101 101 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 20090221 at 20:30 
20090223, 00:11  #10  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
very long binary representation to decimal  davar55  Programming  24  20141207 00:19 
Representation by quadratic forms  Raman  Math  0  20130104 00:29 
Square numbers and binary representation  ET_  Miscellaneous Math  40  20100606 12:55 
Representation of integer as sum of squares  kpatsak  Math  4  20071029 17:53 
Binary representation prime number of 1's.  TTn  15k Search  0  20041218 21:10 