Positional numeral system
In
arithmetic , a complex-base system is a
positional numeral system whose
radix is an
imaginary (proposed by
Donald Knuth in 1955
[1]
[2] ) or
complex number (proposed by S. Khmelnik in 1964
[3] and Walter F. Penney in 1965
[4]
[5]
[6] ).
In general
Let
D
{\displaystyle D}
be an
integral domain
⊂
C
{\displaystyle \subset \mathbb {C} }
, and
|
⋅
|
{\displaystyle |\cdot |}
the
(Archimedean) absolute value on it.
A number
X
∈
D
{\displaystyle X\in D}
in a positional number system is represented as an expansion
X
=
±
∑
ν
x
ν
ρ
ν
,
{\displaystyle X=\pm \sum _{\nu }^{}x_{\nu }\rho ^{\nu },}
where
ρ
∈
D
{\displaystyle \rho \in D}
is the radix (or base ) with
|
ρ
|
>
1
{\displaystyle |\rho |>1}
,
ν
∈
Z
{\displaystyle \nu \in \mathbb {Z} }
is the exponent (position or place),
x
ν
{\displaystyle x_{\nu }}
are digits from the finite set of digits
Z
⊂
D
{\displaystyle Z\subset D}
, usually with
|
x
ν
|
<
|
ρ
|
.
{\displaystyle |x_{\nu }|<|\rho |.}
The
cardinality
R
:=
|
Z
|
{\displaystyle R:=|Z|}
is called the level of decomposition .
A positional number system or coding system is a pair
⟨
ρ
,
Z
⟩
{\displaystyle \left\langle \rho ,Z\right\rangle }
with radix
ρ
{\displaystyle \rho }
and set of digits
Z
{\displaystyle Z}
, and we write the standard set of digits with
R
{\displaystyle R}
digits as
Z
R
:=
{
0
,
1
,
2
,
…
,
R
−
1
}
.
{\displaystyle Z_{R}:=\{0,1,2,\dotsc ,{R-1}\}.}
Desirable are coding systems with the features:
Every number in
D
{\displaystyle D}
, e. g. the integers
Z
{\displaystyle \mathbb {Z} }
, the
Gaussian integers
Z
i
{\displaystyle \mathbb {Z} [\mathrm {i} ]}
or the integers
Z
−
1
+
i
7
2
{\displaystyle \mathbb {Z} [{\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}}]}
, is uniquely representable as a finite code, possibly with a
sign ±.
Every number in the
field of fractions
K
:=
Quot
(
D
)
{\displaystyle K:=\operatorname {Quot} (D)}
, which possibly is
completed for the
metric given by
|
⋅
|
{\displaystyle |\cdot |}
yielding
K
:=
R
{\displaystyle K:=\mathbb {R} }
or
K
:=
C
{\displaystyle K:=\mathbb {C} }
, is representable as an infinite series
X
{\displaystyle X}
which converges under
|
⋅
|
{\displaystyle |\cdot |}
for
ν
→
−
∞
{\displaystyle \nu \to -\infty }
, and the
measure of the set of numbers with more than one representation is 0. The latter requires that the set
Z
{\displaystyle Z}
be minimal, i.e.
R
=
|
ρ
|
{\displaystyle R=|\rho |}
for
real numbers and
R
=
|
ρ
|
2
{\displaystyle R=|\rho |^{2}}
for complex numbers.
In the real numbers
In this notation our standard decimal coding scheme is denoted by
⟨
10
,
Z
10
⟩
,
{\displaystyle \left\langle 10,Z_{10}\right\rangle ,}
the standard binary system is
⟨
2
,
Z
2
⟩
,
{\displaystyle \left\langle 2,Z_{2}\right\rangle ,}
the
negabinary system is
⟨
−
2
,
Z
2
⟩
,
{\displaystyle \left\langle -2,Z_{2}\right\rangle ,}
and the balanced ternary system
[2] is
⟨
3
,
{
−
1
,
0
,
1
}
⟩
.
{\displaystyle \left\langle 3,\{-1,0,1\}\right\rangle .}
All these coding systems have the mentioned features for
Z
{\displaystyle \mathbb {Z} }
and
R
{\displaystyle \mathbb {R} }
, and the last two do not require a sign.
In the complex numbers
Well-known positional number systems for the complex numbers include the following (
i
{\displaystyle \mathrm {i} }
being the
imaginary unit ):
⟨
R
,
Z
R
⟩
{\displaystyle \left\langle {\sqrt {R}},Z_{R}\right\rangle }
, e.g.
⟨
±
i
2
,
Z
2
⟩
{\displaystyle \left\langle \pm \mathrm {i} {\sqrt {2}},Z_{2}\right\rangle }
[1] and
⟨
±
2
i
,
Z
4
⟩
{\displaystyle \left\langle \pm 2\mathrm {i} ,Z_{4}\right\rangle }
,
[2] the
quater-imaginary base , proposed by
Donald Knuth in 1955.
⟨
2
e
±
π
2
i
=
±
i
2
,
Z
2
⟩
{\displaystyle \left\langle {\sqrt {2}}e^{\pm {\tfrac {\pi }{2}}\mathrm {i} }=\pm \mathrm {i} {\sqrt {2}},Z_{2}\right\rangle }
and
⟨
2
e
±
3
π
4
i
=
−
1
±
i
,
Z
2
⟩
{\displaystyle \left\langle {\sqrt {2}}e^{\pm {\tfrac {3\pi }{4}}\mathrm {i} }=-1\pm \mathrm {i} ,Z_{2}\right\rangle }
[3]
[5] (see also the section
Base −1 ± i below).
⟨
R
e
i
φ
,
Z
R
⟩
{\displaystyle \left\langle {\sqrt {R}}e^{\mathrm {i} \varphi },Z_{R}\right\rangle }
, where
φ
=
±
arccos
(
−
β
/
(
2
R
)
)
{\displaystyle \varphi =\pm \arccos {(-\beta /(2{\sqrt {R}}))}}
,
β
<
min
(
R
,
2
R
)
{\displaystyle \beta <\min(R,2{\sqrt {R}})}
and
β
{\displaystyle \beta _{}^{}}
is a positive integer that can take multiple values at a given
R
{\displaystyle R}
.
[7] For
β
=
1
{\displaystyle \beta =1}
and
R
=
2
{\displaystyle R=2}
this is the system
⟨
−
1
+
i
7
2
,
Z
2
⟩
.
{\displaystyle \left\langle {\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}},Z_{2}\right\rangle .}
⟨
2
e
π
3
i
,
A
4
:=
{
0
,
1
,
e
2
π
3
i
,
e
−
2
π
3
i
}
⟩
{\displaystyle \left\langle 2e^{{\tfrac {\pi }{3}}\mathrm {i} },A_{4}:=\left\{0,1,e^{{\tfrac {2\pi }{3}}\mathrm {i} },e^{-{\tfrac {2\pi }{3}}\mathrm {i} }\right\}\right\rangle }
.
[8]
⟨
−
R
,
A
R
2
⟩
{\displaystyle \left\langle -R,A_{R}^{2}\right\rangle }
, where the set
A
R
2
{\displaystyle A_{R}^{2}}
consists of complex numbers
r
ν
=
α
ν
1
+
α
ν
2
i
{\displaystyle r_{\nu }=\alpha _{\nu }^{1}+\alpha _{\nu }^{2}\mathrm {i} }
, and numbers
α
ν
∈
Z
R
{\displaystyle \alpha _{\nu }^{}\in Z_{R}}
, e.g.
⟨
−
2
,
{
0
,
1
,
i
,
1
+
i
}
⟩
.
{\displaystyle \left\langle -2,\{0,1,\mathrm {i} ,1+\mathrm {i} \}\right\rangle .}
[8]
⟨
ρ
=
ρ
2
,
Z
2
⟩
{\displaystyle \left\langle \rho =\rho _{2},Z_{2}\right\rangle }
, where
ρ
2
=
{
(
−
2
)
ν
2
if
ν
even,
(
−
2
)
ν
−
1
2
i
if
ν
odd.
{\displaystyle \rho _{2}={\begin{cases}(-2)^{\tfrac {\nu }{2}}&{\text{if }}\nu {\text{ even,}}\\(-2)^{\tfrac {\nu -1}{2}}\mathrm {i} &{\text{if }}\nu {\text{ odd.}}\end{cases}}}
[9]
Binary systems
Binary coding systems of complex numbers, i.e. systems with the digits
Z
2
=
{
0
,
1
}
{\displaystyle Z_{2}=\{0,1\}}
, are of practical interest.
[9]
Listed below are some coding systems
⟨
ρ
,
Z
2
⟩
{\displaystyle \langle \rho ,Z_{2}\rangle }
(all are special cases of the systems above) and resp. codes for the (decimal) numbers −1, 2, −2, i .
The standard binary (which requires a sign, first line) and the "negabinary" systems (second line) are also listed for comparison. They do not have a genuine expansion for i .
Some bases and some representations
[10]
Radix
–1 ←
2 ←
–2 ←
i ←
Twins and triplets
2
–1
10
–10
i
1 ←
0.1 = 1.0
–2
11
110
10
i
1 / 3 ←
0.01 = 1.10
i
2
{\displaystyle \mathrm {i} {\sqrt {2}}}
101
10100
100
10.101010100...
[11]
1
3
+
1
3
i
2
{\displaystyle {\frac {1}{3}}+{\frac {1}{3}}\mathrm {i} {\sqrt {2}}}
←
0.0011 = 11.1100
−
1
+
i
7
2
{\displaystyle {\frac {-1+\mathrm {i} {\sqrt {7}}}{2}}}
111
1010
110
11.110001100...
[11]
3
+
i
7
4
{\displaystyle {\frac {3+\mathrm {i} {\sqrt {7}}}{4}}}
←
1.011 = 11.101 = 11100.110
ρ
2
{\displaystyle \rho _{2}}
101
10100
100
10
1 / 3 + 1 / 3 i ←
0.0011 = 11.1100
–1+i
11101
1100
11100
11
1 / 5 + 3 / 5 i ←
0.010 = 11.001 = 1110.100
2i
103
2
102
10.2
1 / 5 + 2 / 5 i ←
0.0033 = 1.3003 = 10.0330 = 11.3300
As in all positional number systems with an
Archimedean absolute value , there are some numbers with
multiple representations . Examples of such numbers are shown in the right column of the table. All of them are
repeating fractions with the repetend marked by a horizontal line above it.
If the set of digits is minimal, the set of such numbers has a
measure of 0. This is the case with all the mentioned coding systems.
The almost binary quater-imaginary system is listed in the bottom line for comparison purposes. There, real and imaginary part interleave each other.
Base −1 ± i
The complex numbers with integer part all zeroes in the base i – 1 system
Of particular interest are the
quater-imaginary base (base 2i ) and the base −1 ± i systems discussed below, both of which can be used to finitely represent the
Gaussian integers without sign.
Base −1 ± i , using digits 0 and 1 , was proposed by S. Khmelnik in 1964
[3] and Walter F. Penney in 1965.
[4]
[6]
Connection to the twindragon
The rounding region of an integer – i.e., a set
S
{\displaystyle S}
of complex (non-integer) numbers that share the integer part of their representation in this system – has in the complex plane a fractal shape: the
twindragon (see figure). This set
S
{\displaystyle S}
is, by definition, all points that can be written as
∑
k
≥
1
x
k
(
i
−
1
)
−
k
{\displaystyle \textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}}
with
x
k
∈
Z
2
{\displaystyle x_{k}\in Z_{2}}
.
S
{\displaystyle S}
can be decomposed into 16 pieces congruent to
1
4
S
{\displaystyle {\tfrac {1}{4}}S}
. Notice that if
S
{\displaystyle S}
is rotated counterclockwise by 135°, we obtain two adjacent sets congruent to
1
2
S
{\displaystyle {\tfrac {1}{\sqrt {2}}}S}
, because
(
i
−
1
)
S
=
S
∪
(
S
+
1
)
{\displaystyle (\mathrm {i} -1)S=S\cup (S+1)}
. The rectangle
R
⊂
S
{\displaystyle R\subset S}
in the center intersects the coordinate axes counterclockwise at the following points:
2
15
←
0.
00001100
¯
{\displaystyle {\tfrac {2}{15}}\gets 0.{\overline {00001100}}}
,
1
15
i
←
0.
00000011
¯
{\displaystyle {\tfrac {1}{15}}\mathrm {i} \gets 0.{\overline {00000011}}}
, and
−
8
15
←
0.
11000000
¯
{\displaystyle -{\tfrac {8}{15}}\gets 0.{\overline {11000000}}}
, and
−
4
15
i
←
0.
00110000
¯
{\displaystyle -{\tfrac {4}{15}}\mathrm {i} \gets 0.{\overline {00110000}}}
. Thus,
S
{\displaystyle S}
contains all complex numbers with absolute value ≤ 1 / 15 .
[12]
As a consequence, there is an
injection of the complex rectangle
−
8
15
,
2
15
×
−
4
15
,
1
15
i
{\displaystyle [-{\tfrac {8}{15}},{\tfrac {2}{15}}]\times [-{\tfrac {4}{15}},{\tfrac {1}{15}}]\mathrm {i} }
into the
interval
0
,
1
)
{\displaystyle [0,1)}
of real numbers by mapping
∑
k
≥
1
x
k
(
i
−
1
)
−
k
↦
∑
k
≥
1
x
k
b
−
k
{\displaystyle \textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}\mapsto \sum _{k\geq 1}x_{k}b^{-k}}
with
b
>
2
{\displaystyle b>2}
.
[13]
Furthermore, there are the two mappings
Z
2
N
→
S
(
x
k
)
k
∈
N
↦
∑
k
≥
1
x
k
(
i
−
1
)
−
k
{\displaystyle {\begin{array}{lll}Z_{2}^{\mathbb {N} }&\to &S\\\left(x_{k}\right)_{k\in \mathbb {N} }&\mapsto &\sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}\end{array}}}
and
Z
2
N
→
0
,
1
)
(
x
k
)
k
∈
N
↦
∑
k
≥
1
x
k
2
−
k
{\displaystyle {\begin{array}{lll}Z_{2}^{\mathbb {N} }&\to &[0,1)\\\left(x_{k}\right)_{k\in \mathbb {N} }&\mapsto &\sum _{k\geq 1}x_{k}2^{-k}\end{array}}}
both
surjective , which give rise to a surjective (thus space-filling) mapping
0
,
1
)
→
S
{\displaystyle [0,1)\qquad \to \qquad S}
which, however, is not
continuous and thus not a
space-filling curve . But a very close relative, the
Davis-Knuth dragon , is continuous and a space-filling curve.
See also
References
^
a
b Knuth, D.E. (1960).
"An Imaginary Number System" . Communications of the ACM . 3 (4): 245–247.
doi :
10.1145/367177.367233 .
S2CID
16513137 .
^
a
b
c
Knuth, Donald (1998). "Positional Number Systems". The art of computer programming . Vol. 2 (3rd ed.). Boston: Addison-Wesley. p. 205.
ISBN
0-201-89684-2 .
OCLC
48246681 .
^
a
b
c Khmelnik, S.I. (1964). "Specialized digital computer for operations with complex numbers". Questions of Radio Electronics (In Russian) . XII (2).
^
a
b W. Penney, A "binary" system for complex numbers, JACM 12 (1965) 247-248.
^
a
b Jamil, T. (2002). "The complex binary number system". IEEE Potentials . 20 (5): 39–41.
doi :
10.1109/45.983342 .
^
a
b Duda, Jarek (2008-02-24). "Complex base numeral systems".
arXiv :
0712.1309 [
math.DS ].
^ Khmelnik, S.I. (1966). "Positional coding of complex numbers". Questions of Radio Electronics (In Russian) . XII (9).
^
a
b Khmelnik, S.I. (2004).
Coding of Complex Numbers and Vectors (in Russian) (PDF) . Israel: Mathematics in Computer.
ISBN
978-0-557-74692-7 .
^
a
b Khmelnik, S.I. (2001).
Method and system for processing complex numbers . Patent USA, US2003154226 (A1).
^
William J. Gilbert, "Arithmetic in Complex Bases" Mathematics Magazine Vol. 57, No. 2, March 1984
^
a
b infinite non-repeating sequence
^ Knuth 1998 p.206
^ Base
b
=
2
{\displaystyle b=2}
cannot be taken because both,
2
−
1
=
0.1
bin
=
0.5
dec
{\displaystyle \textstyle 2^{-1}=0.1_{\text{bin}}=0.5_{\text{dec}}}
and
∑
k
≥
2
2
−
k
=
0.0
1
¯
bin
=
0.1
bin
=
0.5
dec
{\displaystyle \textstyle \sum _{k\geq 2}2^{-k}=0.0{\overline {1}}_{\text{bin}}=0.1_{\text{bin}}=0.5_{\text{dec}}}
. However,
(
i
−
1
)
−
1
=
−
0.1
bin
−
0.1
bin
i
=
−
0.5
dec
−
0.5
dec
i
{\displaystyle \textstyle (\mathrm {i} -1)^{-1}=-0.1_{\text{bin}}-0.1_{\text{bin}}\mathrm {i} =-0.5_{\text{dec}}-0.5_{\text{dec}}\mathrm {i} }
is unequal to
∑
k
≥
2
(
i
−
1
)
−
k
=
0.1
dec
+
0.3
dec
i
{\displaystyle \textstyle \sum _{k\geq 2}(\mathrm {i} -1)^{-k}=0.1_{\text{dec}}+0.3_{\text{dec}}\mathrm {i} }
.
External links