5
$\begingroup$

My motivation for this question is exploring beyond the ideas in Project Euler Problem 508. In that problem, it is helpful to know how to convert between a decimal number and a number in base $(-1+i)$. For example, Project Euler lists the following conversions:

$$ (0+0i)_{10} = (0)_{-1+i} \\ (-5+0i)_{10} = (11001101)_{-1+i} \\ (8+0i)_{10} = (111000000)_{-1+i} \\ (24-11i)_{10} = (110010110011)_{-1+i} \\ (11+24i)_{10} = (111010110001101)_{-1+i} $$

My questions (in order of increasing generality):

  • How to convert from real decimal to base $-1+i$?
  • How to convert from imaginary decimal to base $-1+i$?
  • How to convert from Gaussian integers (of the form $a+bi$ where $a,b$ are each in base-10) to base $-1+i$?
  • How to convert from Gaussian integers (of the form $a+bi$ where $a,b$ are each in base-10) to base $c+di$ (where $c,d$ are base-10 also)?

I am looking for the most basic algorithms just to simply understand how such conversions are possible. If the algorithm is not easy to describe, please illustrate the process(es) with some easy examples. Thank you!


Edit: Not sure why, but some comment/answer was removed when it contained the link to this helpful paper.

$\endgroup$
  • $\begingroup$ I saw the link as part of an answer which was deleted by the one who posted it. Please let me know how I could further help you with improving my answer below. (I did not use the mentioned paper. I tryed to figure out my algorith on my own.) $\endgroup$ – zoli Apr 1 '15 at 14:53
5
$\begingroup$

HINT:

Let's consider the case of the Gaussian integers of the form $n+im$ and let the base be $-1+i$.

In general, if one has a base and a number to expand in that base then the one will divide the number repeatedly by the base and will take notes of the remainders. I claim that in the case of the base $-1+i$ the remainder is $0$ or $1$ if the number to be expanded is a Gaussian integer.

So, take a Gaussian integer $n+im$ and divide it by the base chosen:

$$\frac{n+im}{-1+i}=\frac{(n+im)(-1-i)}{2}=\frac{m-n}{2}-i\frac{n+m}{2},$$ where the nominator and the denominator have been multiplied by $-1-i$ (the complex conjugate of the base).

If both $n$ and $m$ are even or both of them are odd then $m-n$ and $m+n$ both are even and the result of the division is a Gaussian integer, $$\frac{m-n}{2}-i\frac{n+m}{2}$$

and the remainder is $0$.

If only one of $n$ or $m$ is even (the other one is odd) then one can consider the following version of the quotient:

$$\frac{n+im}{-1+i}=\frac{m-n+1}{2}-i\frac{n+m-1}{2}-\frac{1}{2}(1+i).$$ In this case the result of the division is the following Gaussian integer:

$$\frac{m-n+1}{2}-i\frac{n+m-1}{2}$$ and the remainder is $1$. Indeed $$\big(-1+i\big)\big( \frac{m-n+1}{2}-i\frac{n+m-1}{2} \big)=n+im-1.$$

One can repeat this prescription with the resulting Gaussian integers until, as a result of the repeated divisions by $2$, the original number disappears and the sequence of the remainders stays...

Let's illustrate the algorithm by the example given in the OP: $$24-i11.$$

If $$(m-n)-i(n+m)=(24-(-11))-i(24+(-11)=-35-i13$$

(See the second pair of columns in the table below) was divisible by $2$ then the third pair of columns would contain the same without any modification and the remainder would be zero (See the column called Remainder). Since $-35-i13$ is not divisible by two, there is a modification according to the formula $$(m-n+1)-i(n+m-1)=-34-i12$$ and the remainder is $1$. The first red arrow points at the result of the first division. (Division by $2$ is performed now.) Then the procedural step detailed above will be repeated until the corresponding value in the third pair of columns has become $0+i0$.

$ \color{white}{bbi}$

If one multiplies the remainders by the different powers of the base $i-1$ and sums up the results then the result will be the complex number which was to be expanded:

$ \color{white}{bbbbbbbbb}$

Finally, we have $$(24-i11)_{10} =(110010110011)_{-1+i}.$$

I hope that this hint above will help the OP solve the other problems. This is not impossible since the skeleton of the method is the same as that of the one that we use in case of the simplest base conversions in "the every day life."

$\endgroup$
  • $\begingroup$ A simply fantastic answer! Thank you for your insight and a clear presentation of the process. $\endgroup$ – Xoque55 Apr 1 '15 at 16:20
1
$\begingroup$

The carry/borrow in base $-1+i$ is $\{1,2,2\}$ (all same sign). To convert decimal number $N$ into base $-1+i$ start with "digits" $...,0,0,0,N$ and apply the carry/borrow to the rightmost digit that is not $0$ or $1$ until all digits are within said range. If the input is a complex number, initialize the last digit with the sum of its real and imaginary parts, and the second-to-last digit with its imaginary part, i.e. $...,0,0,Im,Re+Im$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.