Re: [math-fun] Converting numbers with complex bases
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
For i-1, there's a shortcut. The 4th power is -4. Convert your number to radix -4, using the digits {0,1,2,3}+i{0,1,2,3}. Then convert each digit separately, using a lookup table. Each digit has 4 spaces in the final representation with 0s & 1s. There will be some carries into higher digits, creating temporary 2s, which must be turned into 1100 and propagated to the left. (3 -> 1101). [challenge: prove termination] To convert an integer to radix -4, first convert to regular hex, then to base 4. To get to -4, add 303030...30 to the number (in radix 4), propagate any carries, then subtract 303030...30, creating negative digits in the alternating positions. Drop the signs, and reinterpret the digit string as radix -4. For complex integers, convert real & imaginary parts separately, then group corresponding real & complex digits together. Since -1 has a finite representation as 11101, you don't need a minus sign. A similar deal works for radix i+1, but you need a minus sign for half of the numbers. Wrt RWGs question about low order digits: In the common case where the |norm| of an algebraic number A is the smallest positive integer that is divisible by A, then the integers 0...|norm(A)|-1 are a complete set of residues mod A. If there's a division algorithm in the ring generated by A, and |norm(A)|>1, then the conversion method below will work, except at the end step: you may wind up in a loop of small numbers. This is what happens with radix 1+i, where -1 falls into a tiny loop. In this case, introducing a leading - sign fixes the problem. For more general bases like 1+cbrt2, I don't know what happens. Rich ---- Quoting Bill Gosper <billgosper@gmail.com>:
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* rcs@xmission.com <rcs@xmission.com> [Jul 13. 2011 11:12]:
[...]
To convert an integer to radix -4, first convert to regular hex, then to base 4. To get to -4, add 303030...30 to the number (in radix 4), propagate any carries, then subtract 303030...30, creating negative digits in the alternating positions. Drop the signs, and reinterpret the digit string as radix -4. [...]
Starting from (HAKMEM, item 128) for radix -2: static inline ulong bin2neg(ulong x) // binary --> radix(-2) { // mask in radix 2 is ...10101010 const ulong m = 0xaaaaaaaaaaaaaaaaUL; x += m; x ^= m; return x; } static inline ulong neg2bin(ulong x) // radix(-2) --> binary // inverse of bin2neg() { const ulong m = 0xaaaaaaaaaaaaaaaaUL; x ^= m; x -= m; return x; } ... and just replacing the masks ... static inline ulong bin_to_radm4(ulong x) // binary --> radix(-4) { // mask in binary is ...110011001100 // mask in radix 4 is ...30303030 const ulong m = 0xccccccccccccccccUL; x += m; x ^= m; return x; } static inline ulong radm4_to_bin(ulong x) // radix(-4) --> binary // inverse of bin_to_radm4() { const ulong m = 0xccccccccccccccccUL; x ^= m; x -= m; return x; } ... seems to work: (note radix-4 vectors are printed with least sgnificant digit left!) n: binary(n) radix(-4) 0: ........ ........ = [ 0 0 0 0 ] 1: .......1 .......1 = [ 1 0 0 0 ] 2: ......1. ......1. = [ 2 0 0 0 ] 3: ......11 ......11 = [ 3 0 0 0 ] 4: .....1.. ...111.. = [ 0 3 1 0 ] 5: .....1.1 ...111.1 = [ 1 3 1 0 ] 6: .....11. ...1111. = [ 2 3 1 0 ] 7: .....111 ...11111 = [ 3 3 1 0 ] 8: ....1... ...11... = [ 0 2 1 0 ] 9: ....1..1 ...11..1 = [ 1 2 1 0 ] 10: ....1.1. ...11.1. = [ 2 2 1 0 ] 11: ....1.11 ...11.11 = [ 3 2 1 0 ] 12: ....11.. ...1.1.. = [ 0 1 1 0 ] 13: ....11.1 ...1.1.1 = [ 1 1 1 0 ] 14: ....111. ...1.11. = [ 2 1 1 0 ] 15: ....1111 ...1.111 = [ 3 1 1 0 ] 16: ...1.... ...1.... = [ 0 0 1 0 ] 17: ...1...1 ...1...1 = [ 1 0 1 0 ] 18: ...1..1. ...1..1. = [ 2 0 1 0 ] 19: ...1..11 ...1..11 = [ 3 0 1 0 ] 20: ...1.1.. ..1.11.. = [ 0 3 2 0 ] 21: ...1.1.1 ..1.11.1 = [ 1 3 2 0 ] 22: ...1.11. ..1.111. = [ 2 3 2 0 ] 23: ...1.111 ..1.1111 = [ 3 3 2 0 ] 24: ...11... ..1.1... = [ 0 2 2 0 ] 25: ...11..1 ..1.1..1 = [ 1 2 2 0 ] 26: ...11.1. ..1.1.1. = [ 2 2 2 0 ] 27: ...11.11 ..1.1.11 = [ 3 2 2 0 ] 28: ...111.. ..1..1.. = [ 0 1 2 0 ] 29: ...111.1 ..1..1.1 = [ 1 1 2 0 ] 30: ...1111. ..1..11. = [ 2 1 2 0 ] 31: ...11111 ..1..111 = [ 3 1 2 0 ] Am I somehow wrong here? (my method seems overly simple when compared to your description).
Nice. I'd forgotten the HAKMEM item. Xoring with 3030...3030, radix 4, is the same as subtracting 30* and negating the digits -- it's the 3s complement (in the even-position digits). Rich ----- Quoting Joerg Arndt <arndt@jjj.de>:
* rcs@xmission.com <rcs@xmission.com> [Jul 13. 2011 11:12]:
[...]
To convert an integer to radix -4, first convert to regular hex, then to base 4. To get to -4, add 303030...30 to the number (in radix 4), propagate any carries, then subtract 303030...30, creating negative digits in the alternating positions. Drop the signs, and reinterpret the digit string as radix -4. [...]
Starting from (HAKMEM, item 128) for radix -2:
static inline ulong bin2neg(ulong x) // binary --> radix(-2) { // mask in radix 2 is ...10101010 const ulong m = 0xaaaaaaaaaaaaaaaaUL; x += m; x ^= m; return x; }
static inline ulong neg2bin(ulong x) // radix(-2) --> binary // inverse of bin2neg() { const ulong m = 0xaaaaaaaaaaaaaaaaUL; x ^= m; x -= m; return x; }
... and just replacing the masks ...
static inline ulong bin_to_radm4(ulong x) // binary --> radix(-4) { // mask in binary is ...110011001100 // mask in radix 4 is ...30303030 const ulong m = 0xccccccccccccccccUL; x += m; x ^= m; return x; }
static inline ulong radm4_to_bin(ulong x) // radix(-4) --> binary // inverse of bin_to_radm4() { const ulong m = 0xccccccccccccccccUL; x ^= m; x -= m; return x; }
... seems to work: (note radix-4 vectors are printed with least sgnificant digit left!)
n: binary(n) radix(-4) 0: ........ ........ = [ 0 0 0 0 ] 1: .......1 .......1 = [ 1 0 0 0 ] 2: ......1. ......1. = [ 2 0 0 0 ] 3: ......11 ......11 = [ 3 0 0 0 ] 4: .....1.. ...111.. = [ 0 3 1 0 ] 5: .....1.1 ...111.1 = [ 1 3 1 0 ] 6: .....11. ...1111. = [ 2 3 1 0 ] 7: .....111 ...11111 = [ 3 3 1 0 ] 8: ....1... ...11... = [ 0 2 1 0 ] 9: ....1..1 ...11..1 = [ 1 2 1 0 ] 10: ....1.1. ...11.1. = [ 2 2 1 0 ] 11: ....1.11 ...11.11 = [ 3 2 1 0 ] 12: ....11.. ...1.1.. = [ 0 1 1 0 ] 13: ....11.1 ...1.1.1 = [ 1 1 1 0 ] 14: ....111. ...1.11. = [ 2 1 1 0 ] 15: ....1111 ...1.111 = [ 3 1 1 0 ] 16: ...1.... ...1.... = [ 0 0 1 0 ] 17: ...1...1 ...1...1 = [ 1 0 1 0 ] 18: ...1..1. ...1..1. = [ 2 0 1 0 ] 19: ...1..11 ...1..11 = [ 3 0 1 0 ] 20: ...1.1.. ..1.11.. = [ 0 3 2 0 ] 21: ...1.1.1 ..1.11.1 = [ 1 3 2 0 ] 22: ...1.11. ..1.111. = [ 2 3 2 0 ] 23: ...1.111 ..1.1111 = [ 3 3 2 0 ] 24: ...11... ..1.1... = [ 0 2 2 0 ] 25: ...11..1 ..1.1..1 = [ 1 2 2 0 ] 26: ...11.1. ..1.1.1. = [ 2 2 2 0 ] 27: ...11.11 ..1.1.11 = [ 3 2 2 0 ] 28: ...111.. ..1..1.. = [ 0 1 2 0 ] 29: ...111.1 ..1..1.1 = [ 1 1 2 0 ] 30: ...1111. ..1..11. = [ 2 1 2 0 ] 31: ...11111 ..1..111 = [ 3 1 2 0 ]
Am I somehow wrong here? (my method seems overly simple when compared to your description).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I now finshed bit-level routines for the conversion to and from radix (-1+i) and 2*i, see http://www.jjj.de/fxt/demo/bits/#radix-2i (all demos whose names start radix-*). Hope this is of use. Blazing fast as always. Btw. Adding numbers in radix (-1+i) can be done by this very concise function: ulong add_radm1pi(ulong x, ulong y) // Add radix(-1+i) representations x and y. // Note that x + (x<<1) == x + (-1+i)*x == i*x { while ( y ) { ulong c = x & y; // positions with carries x ^= y; // positions without carries y = add_radm1pi(c<<2, c<<3); // add carries } return x; } Is there a more efficient way? cheers, jj * rcs@xmission.com <rcs@xmission.com> [Jul 13. 2011 12:12]:
For i-1, there's a shortcut. The 4th power is -4. Convert your number to radix -4, using the digits {0,1,2,3}+i{0,1,2,3}. Then convert each digit separately, using a lookup table. Each digit has 4 spaces in the final representation with 0s & 1s. There will be some carries into higher digits, creating temporary 2s, which must be turned into 1100 and propagated to the left. (3 -> 1101). [challenge: prove termination] To convert an integer to radix -4, first convert to regular hex, then to base 4. To get to -4, add 303030...30 to the number (in radix 4), propagate any carries, then subtract 303030...30, creating negative digits in the alternating positions. Drop the signs, and reinterpret the digit string as radix -4. For complex integers, convert real & imaginary parts separately, then group corresponding real & complex digits together. Since -1 has a finite representation as 11101, you don't need a minus sign. A similar deal works for radix i+1, but you need a minus sign for half of the numbers.
Wrt RWGs question about low order digits: In the common case where the |norm| of an algebraic number A is the smallest positive integer that is divisible by A, then the integers 0...|norm(A)|-1 are a complete set of residues mod A. If there's a division algorithm in the ring generated by A, and |norm(A)|>1, then the conversion method below will work, except at the end step: you may wind up in a loop of small numbers. This is what happens with radix 1+i, where -1 falls into a tiny loop. In this case, introducing a leading - sign fixes the problem. For more general bases like 1+cbrt2, I don't know what happens.
Rich
[...]
participants (3)
-
Bill Gosper -
Joerg Arndt -
rcs＠xmission.com