Andy Latto> On Tue, Jul 12, 2011 at 11:22 AM, Kerry Mitchell < lkmitch@gmail.com>
wrote:
Hi,
Using the digits {0, 1} and the complex base -1+i, it's straightforward to show that 1010 = 1+3i. �Is there an easy way to go backward? �That is, given a complex number in the form a+bi, recover its "binary" representation? �I'm immediately interested in the case for bases -1+i and -1-i (digits {0, 1}), but also interested in the general case.
The standard procedure for converting a number to another base works fine. If we want to express a number N in base B, divide N by B, finding Q and R such that
(*) N = B.Q + R
where R is a digit. Then find the base-B representation of Q, and add an R on the end. If (*) always has a solution, then any number can be represented in that base with that digit set. If the solution of (*) is always unique, the representation is unique.
Andy
Hey, that's pretty neat. (1+3i)/(i-1) =1-2i comes out integral, so the low digit is 0. But (1-2i)/(i-1) = i/2-3/2, so you have no choice but 1, which you subtract with the assurance of an integer quotient. The process *must* converge to 0 for all Gaussian integers! Out[65]= 69 + 105 I In[66]:= {%, % - 1}/(I - 1) Out[66]= {18 - 87 I, 37/2 - (173 I)/2} In[67]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[67]= {-(105/2) + (69 I)/2, -52 + 35 I} In[68]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[68]= {87/2 + (17 I)/2, 44 + 9 I} In[69]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[69]= {-(35/2) - (53 I)/2, -17 - 26 I} . . . Out[76]= {3, 7/2 + I/2} In[77]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[77]= {-(3/2) - (3 I)/2, -1 - I} In[78]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[78]= {I, 1/2 + (3 I)/2} In[79]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[79]= {1/2 - I/2, 1} In[80]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[80]= {-(1/2) - I/2, 0} So, reading backwards, the [[2]] branches mean 1 and the [[1]] branches mean 0, and 69+105i = {1,0,1,0,...,1,1,0}. When there are more than two possible digits, can we simply try subtracting them all and have exactly one quotient come out even? Converting pure fractions might be trickier. After Knuth Vol 2, the B=i-1 figure is http://gosper.org/basei-1.png . How do you choose Q and R? R=0 in the red and yellow region, 1 in the blue and green region. Or we could regard this as the base (i-1)^2 region divided into four R, 01,00,11,10 top to bottom. In ordinary base conversion, this is the easier case--just multiply by the base and take floor. But what is floor here? Note that the problem extends to *real* bases with complex digits. Inscribe http://www.tweedledum.com/rwg/rad2Image4.gif in the unit circle and rotate pi/3. This is the subset of the complex plane representable base 2 with digits 0 and the three cube roots of 1. Throw a dart toward 0 and the first digit depends on which subregion it's in. If it's in a white area (are you sure?), you'll need a minus sign. Julian and I noticed that the boundary of the overall region is six Sierpinski gaskets around a hexagon, pointing alternately inward and outward. Julian found its Fourier series. --rwg