* Andy Latto <andy.latto@pobox.com> [Jul 13. 2011 08:00]:

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

Here is a pari/gp to and from given radix (and digit set): to_rdx(n, rx, dg)= /* convert n into radix rx expansion using digits given in dg[] */ { local(d, t, v, ct); ct = 66; v = vector(ct); /* vector of digits, must be long enough */ while ( n != 0, for (j=1, #dg, d = dg[j]; t = (n-d)/rx; dt = denominator(t); print(" :: [n,d,t,den,?]=",[n, d, t, dt, if(dt==1," ****","")]); /* prt */ if ( dt == 1, v[ct] = d; ct -= 1; n = t; break(); ); if ( j==#dg, error(" radix rx and digit set dg[] are not compatible") ); ); ); v = vector(#v-ct, k, v[#v-k+1]); /* shift digits */ return(v); } /* ----- */ from_rdx(v, rx, dg)= /* inverse of to_rdx() */ { return( sum(j=1, #v, v[j] * rx^(j-1) ) ); } For example, with n = 69 + 105*I, rx = -1 + I, and dg= [0, 1] we get: ? v=to_rdx(n,rx,dg) :: [n,d,t,den,?]=[69 + 105*I, 0, 18 - 87*I, 1, " ****"] :: [n,d,t,den,?]=[18 - 87*I, 0, -105/2 + 69/2*I, 2, ""] :: [n,d,t,den,?]=[18 - 87*I, 1, -52 + 35*I, 1, " ****"] :: [n,d,t,den,?]=[-52 + 35*I, 0, 87/2 + 17/2*I, 2, ""] :: [n,d,t,den,?]=[-52 + 35*I, 1, 44 + 9*I, 1, " ****"] :: [n,d,t,den,?]=[44 + 9*I, 0, -35/2 - 53/2*I, 2, ""] :: [n,d,t,den,?]=[44 + 9*I, 1, -17 - 26*I, 1, " ****"] :: [n,d,t,den,?]=[-17 - 26*I, 0, -9/2 + 43/2*I, 2, ""] :: [n,d,t,den,?]=[-17 - 26*I, 1, -4 + 22*I, 1, " ****"] :: [n,d,t,den,?]=[-4 + 22*I, 0, 13 - 9*I, 1, " ****"] :: [n,d,t,den,?]=[13 - 9*I, 0, -11 - 2*I, 1, " ****"] :: [n,d,t,den,?]=[-11 - 2*I, 0, 9/2 + 13/2*I, 2, ""] :: [n,d,t,den,?]=[-11 - 2*I, 1, 5 + 7*I, 1, " ****"] :: [n,d,t,den,?]=[5 + 7*I, 0, 1 - 6*I, 1, " ****"] :: [n,d,t,den,?]=[1 - 6*I, 0, -7/2 + 5/2*I, 2, ""] :: [n,d,t,den,?]=[1 - 6*I, 1, -3 + 3*I, 1, " ****"] :: [n,d,t,den,?]=[-3 + 3*I, 0, 3, 1, " ****"] :: [n,d,t,den,?]=[3, 0, -3/2 - 3/2*I, 2, ""] :: [n,d,t,den,?]=[3, 1, -1 - I, 1, " ****"] :: [n,d,t,den,?]=[-1 - I, 0, I, 1, " ****"] :: [n,d,t,den,?]=[I, 0, 1/2 - 1/2*I, 2, ""] :: [n,d,t,den,?]=[I, 1, 1, 1, " ****"] :: [n,d,t,den,?]=[1, 0, -1/2 - 1/2*I, 2, ""] :: [n,d,t,den,?]=[1, 1, 0, 1, " ****"] [0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1] /* Most significant digit is on the _right_ */ ? m=from_rdx(v,rx,dg) 69 + 105*I I tested (sloppily) several rx and dg[]: \\ ------- for real numbers (Start): rx=+3; dg=[0,1,-1]; rx=-3; dg=[0,1,-1]; rx=+2; dg=[0,1]; \\ positive real numbers only \\rx=+2; dg=[0,-1]; \\ negative real numbers only rx=+2*I; dg=[0,1,-1,I]; \\ real numbers only rx=-2; dg=[0,1]; rx=-2; dg=[0,-1]; \\rx=+2*I; dg=[0,1,2,3]; \\ Fail, ... \\ need to convert imag and real parts separately (neg. quart. rep.) \\ by using the following: rx=-4; dg=[0,1,2,3]; \\ ------- for real numbers (End). rx=+I-2; dg=[0,1,2,3,4]; rx=+I-2; dg=[0,1,2,-1,-2]; rx=-I-2; dg=[0,1,2,-1,-2]; rx=-I-2; dg=[0,1,2,3,4]; \\rx=-I+2; dg=[0,1,2,3,-2]; \\ Fail \\rx=-I+2; dg=[0,1,2,-1,3]; \\ Fail \\rx=-I+2; dg=[0,-1,-2,-3,-4]; \\ Fail \\rx=+I+2; dg=[0,-1,-2,-3,-4]; \\ Fail rx=-I+1; dg=[0,+1]; \\rx=-I+1; dg=[0,-1]; \\ Fail ?? rx=-I-1; dg=[0,+1]; rx=-I-1; dg=[0,-1]; rx=+I+1; dg=[0,-1]; \\rx=+I+1; dg=[0,+1]; \\ Fail ?? rx=+I-1; dg=[0,-1]; rx=+I-1; dg=[0,+1]; regards, jj