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
[...]