15
$\begingroup$

So I've been working on a simple base-conversion program, and having given it the ability to convert from decimal to any base $> 1$ or $< 0$, as well as the $p$-adic (bijective, I think?) bases, I decided to tackle imaginary systems.

Unfortunately, I can't seem to understand any of the articles I find about them. The Wikipedia article on quater-imaginary is fairly comprehensible (I feel like I could write an algorithm for converting between decimal and it), but there are a couple of things I don't quite understand (why there are 4 digits, for example).

The article on complex bases is a bit more dense. This is mostly because I know very little of the notation used (and trying to Google it proves difficult, since they tend to be symbols more than words). I think I could extrapolate pure imaginary bases from quater-imaginary (once I've a fuller understanding of it), but I have no idea how to work complex bases at all.

So I guess my question is: Does anyone have any good resources on how complex number systems work? (That is to say, algorithms for converting between decimal and them, why some of the seemingly arbitrary decisions (like the number of digits) were made, et cetera). Not necessarily in simple terms, but at least presented in such a way that I could Google or otherwise find the meaning of any of the things I didn't immediately understand without too much trouble. (I'd rather be spending my time trying to learn about something than trying to search for information about it).

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Complex_base_systems $\endgroup$ – Bill Cook Nov 5 '11 at 1:35
  • 1
    $\begingroup$ You've tried reading Knuth's original article? $\endgroup$ – J. M. is a poor mathematician Nov 5 '11 at 1:43
  • $\begingroup$ FWIW: conversion to decimal is always an easy task: you can use Horner's algorithm in general, and digit-grouping for bases that are prime powers. $\endgroup$ – J. M. is a poor mathematician Nov 5 '11 at 1:45
  • $\begingroup$ I've wanted to look into his article, but it doesn't appear to be freely available, and I'd prefer not to have to spend anything if it can be helped. And yeah, decimal->base_n conversions are the things I've been having the most trouble with. $\endgroup$ – Jef Nov 5 '11 at 2:07
  • $\begingroup$ You might have luck getting a copy at a nearby (university) library. $\endgroup$ – J. M. is a poor mathematician Nov 5 '11 at 16:37
3
$\begingroup$

Almost four years and no answers? I can't give you a complete answer, but I guess under the theory of better late than never I will try to address as many as your points as I can. Though it's possible that by now you have gotten a better answer through another source.

Does anyone have any good resources on how complex number systems work?

Yeah. Go to Wikipedia and scroll all the way to the bottom, to find the external links. The Gilbert paper looks very good and transparent, and it's available as a PDF. Your local university library might have a copy of Knuth's monumental 3-volume book.

there are a couple of things I don't quite understand (why there are 4 digits, for example).

This is a very interesting question in its own right. I think that first you need to understand "negabases" (numeral systems with a negative number as the base), but before that, I will review some very basic basics of positive integer bases.

You already know, at least on an intuitive level, the basic principle of power series numeral systems with a positive integer as the base. Given a base $b$ and a positive integer $n$ represented by the string of $\mathcal{L}$ digits $\{d_{\mathcal{L} - 1}, d_{\mathcal{L} - 2}, \ldots d_1, d_0 \}$, the string of digits is essentially a shorthand for $$n = \sum_{i = 0}^{\mathcal{L} - 1} d_ib^i$$. Of course this basic principle also works when $b$ is almost anything other than a positive integer greater than 1.

I could be wrong on this next point, but I think that there are only three numbers that are completely unworkable as bases for a power series positional numeral system, namely $-1$, 0 and 1. I think that for a base $b$ to be "workable" for this purpose, the following needs to be true: if $\alpha$ and $\beta$ are distinct integers drawn from $\mathbb{Z}$, then $b^\alpha$ and $b^\beta$ are distinct numbers.

With $b = -1$, $\alpha$ and $\beta$ can be distinct but if they're of the same parity, then $b^\alpha = b^\beta$, and with $b = 1$ they can have different parities. It should be obvious that 0 is completely useless as a base. Other than that, I guess any number whatsoever can work as a base. Of course some bases have more practical value than others. For example, quite a few people think we'd all be better off replacing 10 with 12 as our main number base, but I've never heard anyone say the same for $\sqrt[3]{1729}$.

With complete confidence I can tell you that there are only two digits you must absolutely have in every power series positional numeral system: 0 and 1. You have to have 0 to signify the absence of a specific power of the base. Whether you need any more digits depends on the choice of base. Given an integer $b > 2$, you also need a digit for $b - 1$; in fact you need to be able to represent the integers from 0 to $b - 1$ with a single digit.

It is this need for digits from 2 to $b - 1$ when $b > 2$ that leads to some frustrated expectations when the base is not a positive integer. For example, for $b = 4$, you need digits for 0, 1, 2, 3. You don't need a digit for 4 because that's represented as 10. What digits do you need for "negaquartal," with $b = -4$? Digits for $-1$, $-2$, $-3$? Actually, no (though I suppose that if I really wanted to, I could try to work out a system using such digits; I have not wanted to).

In a philosophical sense, systems with positive bases are incapable of representing negative numbers. Sure, we have the negation operator, but in a sense that is actually a shorthand for "$0 -$." Which is to say that, e.g., $-7$ doesn't represent negative seven, that it actually represents $0 - 7$. It is this perceived shortcoming that negabases address: they can represent negative numbers without the need for a negation operator.

For negaquartal, you need digits for 0, 1, 2, 3. The numbers $-1$, $-2$, $-3$ are not single-digit numbers in this system. But you can't use 10 for 4 because now that means $-4$. So positive 4 is represented as 130, and in general, for $\alpha$ odd, the negaquartal representation of $4^\alpha$ is 13 followed by $\alpha$ 0s; this is tantamount to $4^{\alpha + 1} - 3(4^\alpha)$. The negaquartal representation of $4^\alpha$ with $\alpha$ even is the same as with positive quartal. As for $-3$, that's 11, which means $-4 + 1$.

To represent complex numbers, both positive bases and negative bases have to separate the real part from the imaginary part. That's where complex number bases come in. Quater-imaginary, as you know, has $b = 2i$. As you may have already realied, $2i$ is the principal square root of $-4$. So the way it works out is that to obtain the quater-imaginary representation of a purely real integer, be it negative or positive, you can just take the negaquartal representation and riffle in some zeroes. Thus, $-3$ is 11 in negaquartal and 101 in quater-imaginary. I know I've been longwinded on this one without fully answering your question, but if you've read this far and you understand why quater-imaginary uses 4 digits, I'm happy.

$\endgroup$
3
+200
$\begingroup$

I have worked on complex based systems ~2005 (also inspired me to asymmetric numeral systems in 2006) - just found this question and can clarify something if needed.

Some my materials: paper, slides, 3 interactive demonstrations, fractal Haar wavelets.

So basically it is just standard positional numeral system, but with complex base: you represent a complex number as $\sum_i a_i z^i$, where $a_i \in \{0,\ldots,n-1\}$. In 1D we have just base $z=\pm n$, in 2D we need $|z|^2=n$, in 3D $|z|^3=n$ and so on, but additionally the argument needs also to fulfill some conditions. I had a hypothesis (still unproven?) that only periodic cases worked well (subjection to $\mathbb{C}$, injection in all but a zero measure set): such that $z^2\in \mathbb{Z}z+\mathbb{Z}$. There is still infinite number of such cases - you can find their complete classification in my materials, also analytically found properties: area of fractional part (which is fractal), Hausdorff dimension of its boundary, circumference and area of convex hull.

The simplest nontrivial cases are $z=1\pm i$, which can be easily drawn on a graph-ruled notebook, e.g:

enter image description here

Regarding conversion, see slide 11, it is useful to write e.g. $2-2z+z^2=0$ for $z=1-i$ as $(2,-2,1)_z=0$. This way to convert e.g. $-4$ to complex base:

$$(-3)_z\to^{+2} (1,-4,2)_z \to^{+2} (1,0,-2,2)_z \to^{+1} (1,0,0,0,1)_z $$

getting $-3=1+z^4$. Note that digit direction is reversed here: from the least to the most significant digit.

$\endgroup$
3
$\begingroup$

I've also wanted to write a base conversion program, but as I got deeper into research about it, I ended up in unknown territory. As far as I know, conversion to any complex base is not yet doable. So I’ll summarize what I have. I’ve sat on this for far too long because I couldn’t figure out what to do with it so I just finally threw it up on arXiv, which you can view here.

So here is how to convert to an imaginary base. But before you can convert to an imaginary base, you’ll need to know how to convert to a negative base. Why? because even powers of imaginary values can be negative values. For a negative integer base $b$, it’ll use the same amount of digits as its positive base, which is ${0, 1, ..., |b|-1}$. Conversion here is done as the following:

To convert a number $N$ to base $B$ where $B$ is an integer less than $1$, $N$ is repeatedly divided by $B$ until $N$ becomes $0$ with the digit being the modulus* of $B$ to $N$. The division here must be floor division. In the event that $N$ mod $B$ is negative, $1$ is added to $N$ and $B$ (being negative) is subtracted from the digit.

*The sign of the modulus when working with negative values is that of the divisor (the base), and not all programming languages follow this rule.

But that only gets you negative integer bases. Then in 2009, Shunji Ito and Taizo Sadahiro published a method that uses any real value that’s less than $-1$ as a base. I also explain it in a completely different manner as such:

The digit set for real negative bases is defined as $\{0,\: 1, \:..., \lceil |B| \rceil-1\}$. It is defined for $-B < -1$ (where B is positive) and N must fall between $^{-B}/_{B+1}$ and $^{1}/_{B+1}$. These two values are defined as $l_B$ and $r_B$. In the event that N does not fall within this range, N is divided by a suitable power of B (denoted as p) so that it will fit and the algorithm is started at that power. The transformation function is defined as $T_B (x)= -Bx-\left \lfloor -Bx-l_b \right \rfloor$. This function is called recursively such that $T_B^0 (x)=x$ , $T_B^1 (x)=T_B (x)$, $T_B^2 (x)= T_B (T_B (x))$ and so on. Thus the digits are found using

$$ N = \sum_{\substack{i=-\infty\\j=0}}^{\substack{i=p-1 \\ j=\infty }} d_{i}B^{i} \text{ with } d_{i}=\left \lfloor -B T_{B}^{j}(x)-l_B \right \rfloor \text{ where } x= ^{N}/_{(-B)^{p}} \text{ such that } x \in \left[ l_B,\: r_B\right) $$

Where $i$ decreases by 1 and $j$ increases by 1 for each iteration. In the event that one of the $d_i$’s is equal to B, 1 is subtracted from the $d_i$ and a 0 is inserted in after it.

Here’s a Python implementation of it:

from math import floor
def to_nb(num, base, prec=-15):
    "converts a real from base 10 to negative base (base < -1)"

    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    newval = ""

    if base >= -1 or base < -len(digits):
        raise ValueError('invalid base')

    P = 0; base = abs(base)  # ref. defines method for -base where base > 0
    lb, rb, X = -base / (base+1.), 1 / (base+1.), num

    while not lb <= X < rb:
        P += 1
        X = num / (-base) ** P

    def T(x): return -base * x - floor( -base * x - lb)

    while P >= prec:  # conversion step
        d = int(floor(-base*X - lb))
        X = T(X)
        if P == 0 and '.' not in newval:  # add radix point
            newval = newval + '.'
        if d == base:  # if this happens, you do this (see Ito ref.)
            newval = newval + digits[d-1]+ digits[0]
        else:
            newval = newval + digits[d]
        P -= 1
    return newval

(This is now a Python module and is on Github)

Now, an imaginary base requires more digits/characters to represent itself than a negative base. It’ll need up to its square. I picture a complex number as two dimensional and so it needs a square amount of digits to cover the area. I don't have a deep abstracted mathematical answer for this though, Donald Knuth simply states that base $2 i$ uses four digits and I merely join and extend his work with Ito and Sadahiro’s. Otherwise, base $2 i$ will need four digits, base $3 i$ will need nine, $\pi i$ will need ten, $12 i$ will need $144$ digits, etc.

So, to convert a complex number to base $b i$ where $|b| > 1$, convert the real part to base $b^2$. Then, take the imaginary part and divide that by the base, then convert that to base $b^2$. So if your value is $227.65625 + 10.859375 i$ and the base you’re converting to is $4 i$, convert $227.65625 $ to base$ -16$ and convert $10.859375 / 4 = 2.71484375$ to base $-16$; you’re left with the real part being $124.68$ and the imaginary part being $3.57$.

Now the final step is to interweave these together such that the real part takes the even power positions of $i$ and the imaginary part takes the odd power positions of $i$, adding zeros in between as needed. So the real part $124.68$ becomes $\color{red}1\color{red}0\color{red}2\color{red}0\color{red}4.\color{red}0\color{red}6\color{red}0\color{red}8$ and the imaginary part $3.57$ becomes $\color{DarkGreen}0\color{DarkGreen}3\color{DarkGreen}0.\color{DarkGreen}5\color{DarkGreen}0\color{DarkGreen}7$ and interweaving them we get $\color{red}1\color{DarkGreen}0\color{red}2\color{DarkGreen}3\color{red}4.\color{DarkGreen}5\color{red}6\color{DarkGreen}7\color{red}8$. Thus $227.65625 + 10.859375 i$ is $10234.5678$ in base $4 i$.

As for complex bases, I’ve only come across $i-1$ as a base but not really anything else when I was researching it. So I would say complex bases are unknown seas. I can say that $-10.2-9.6i$ in base $3i-1$ is $217.2$, but I don’t know how to do the conversion from base ten to that base (I made up a number, claimed it was base $3i-1$, converted to base ten using definition of base).

From playing around in it, I suspect that any complex base where the real part is $0$ or less, can represent any number without a sign or $i$, similar to how a negative base doesn’t need a sign to represent negative values or an imaginary base doesn’t need a sign or $i$ to represent a complex value. But for complex bases where the real part is greater than $0$, it’s a different story – they might need the negative sign or even the $i$ in order to work. I’m unlikely to crack that, but would love to see it when or if someone does.

As a fun check, convert the following decimal value to base $-6 i$. If done correctly, you’ll have something readable: $-891888796340-307744356378i$


References:
Imaginary Number Bases
Beta-Expansions With Negative Bases
An Imaginary Number System

(other things I’ve written about number bases)

$\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.