Complex-base system

Numeral systems

Hindu–Arabic numeral system
Western Arabic Eastern Arabic Bengali Gurmukhi Indian Sinhala Tamil Balinese Burmese Dzongkha Javanese Khmer Lao Mongolian Thai
East Asian
Chinese Suzhou Hokkien Japanese Korean Vietnamese Counting rods
Alphabetic
Abjad Armenian Āryabhaṭa Cyrillic Ge'ez Georgian Greek Hebrew Roman
Former
Aegean Attic Babylonian Brahmi Egyptian Etruscan Inuit Kharosthi Mayan Muisca Quipu Prehistoric
Positional systems by base
2 3 4 5 6 8 10 12 16 20 60
Non-standard positional numeral systems
Bijective numeration (1) Signed-digit representation (Balanced ternary) factorial negative Complex-base system (2i) Non-integer representation (φ) mixed
List of numeral systems

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$ be an integral domain $\subset \mathbb{C}$ , and $|\cdot |$ the (Archimedean) absolute value on it.

A number $X\in D$ in a positional number system is represented as an expansion

X=\pm \sum _{\nu }^{}x_{\nu }\rho ^{\nu },

where

$\rho$		is the radix (or base) $\in D$ with $\|\rho \|>1$ ,
$\nu$		is the exponent (position or place) $\in \mathbb{Z }$ ,
$x_{\nu }$		are digits from the finite set of digits $Z\subset D$ , usually with $\|x_{\nu }\|<\|\rho \|.$

The cardinality $R:=|Z|$ is called the level of decomposition.

A positional number system or coding system is a pair

\left\langle \rho ,Z\right\rangle

with radix $\rho$ and set of digits $Z$ , and we write the standard set of digits with $R$ digits as

Z_{R}:=\{0,1,2,\dotsc ,{R-1}\}.

Desirable are coding systems with the features:

Every number in $D$ , e. g. the integers $\mathbb {Z}$ , the Gaussian integers $\mathbb{Z } [{\mathrm i}]$ or the integers $\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:={\mathsf {Quot}}(D)$ , which possibly is completed for the metric given by $|\cdot |$ yielding $K:=\mathbb{R}$ or $K:=\mathbb{C}$ , is representable as an infinite series $X$ which converges under $|\cdot |$ for $\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$ be minimal, i. e. $R=|\rho |$ for real resp. $R=|\rho |^{2}$ for complex numbers.

In the real numbers

In this notation our standard decimal coding scheme is denoted by

\left\langle 10,Z_{10}\right\rangle ,

the standard binary system is

\left\langle 2,Z_{2}\right\rangle ,

the negabinary system is

\left\langle -2,Z_{2}\right\rangle ,

and the balanced ternary system^[2] is

\left\langle 3,\{-1,0,1\}\right\rangle .

All these coding systems have the mentioned features for $\mathbb {Z}$ and $\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 ( $\mathrm i$ being the imaginary unit):

$\left\langle {\sqrt {R}},Z_{R}\right\rangle$ , e. g. $\left\langle \pm {\mathrm i}{\sqrt {2}},Z_{2}\right\rangle$ ^[1] and

\left\langle \pm 2{\mathrm i},Z_{4}\right\rangle

,^[2] the quater-imaginary base, proposed by Donald Knuth in 1955.

$\left\langle {\sqrt {2}}e^{{\pm {\tfrac {\pi }2}{\mathrm i}}}=\pm {\mathrm i}{\sqrt {2}},Z_{2}\right\rangle$ and

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

$\left\langle {\sqrt {R}}e^{{{\mathrm i}}}\varphi ,Z_{R}\right\rangle$ , where $\varphi =\pm \arccos {(-\beta /(2{\sqrt {R}}))}$ , $\beta <\min(R,2{\sqrt {R}})$ and $\beta _{{}}^{{}}$ is a positive integer that can take multiple values at a given $R$ .^[7] For $\beta =1$ and $R=2$ this is the system

\left\langle {\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}},Z_{2}\right\rangle .

$\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]
$\left\langle -R,A_{R}^{2}\right\rangle$ , where the set $A_{R}^{2}$ consists of complex numbers $r_{\nu }=\alpha _{\nu }^{1}+\alpha _{\nu }^{2}{\mathrm i}$ , and numbers $\alpha _{\nu }^{{}}\in Z_{R}$ , e. g.

\left\langle -2,\{0,1,\mathrm {i} ,1+\mathrm {i} \}\right\rangle .

^[8]

$\left\langle \rho =\rho _{2},Z_{2}\right\rangle$ , where $\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\}$ , are of practical interest.^[9] Listed below are some coding systems $\langle \rho ,Z_{2}\rangle$ (all are special cases of the systems above) and codes for the numbers $-1, 2, -2, i$ . The standard binary (which requires a sign) and the "negabinary" systems 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$	¹⁄₃ ← 0.01 = 1.10
$i$ √2	101	10100	100	10.101010100…^[11]	¹⁄₃+¹⁄₃ $i$ √2 ← 0.0011 = 11.1100
–1+ $i$	11101	1100	11100	11	¹⁄₅+³⁄₅ $i$ ← 0.010 = 11.001 = 1110.100
(–1+ $i$ √7) ⁄₂	111	1010	110	11.110001100…^[11]	(3+ $i$ √7) ⁄₄ ← 1.011 = 11.101 = 11100.110
ρ₂	101	10100	100	10	¹⁄₃+¹⁄₃ $i$ ← 0.0011 = 11.1100
2 $i$	103	2	102	10.2	¹⁄₅+²⁄₅ $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 shown in the bottom line for comparison purposes.

Base $-1 \pm i$

The complex numbers with integer part all zeroes in the base

i -1

system

Of particular interest are the quater-imaginary base (base $2 i$ ) and the base $-1 \pm i$ systems discussed below, both of which can be used to finitely represent the Gaussian integers without sign.

Base $-1 \pm i$ , using digits $0$ and $1$ , was proposed by S. Khmelnik in 1964^[3] and Walter F. Penney in 1965.^[4]^[6] The rounding region of an integer – i.e., a set $S$ of complex (non-integer) numbers that share the integer part of their representation in this system – has a fractal shape: the twindragon (see figure). This set $S$ is, by definition, all points that can be written as $\textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}$ with $x_{k}\in \{0,1\}$ . The rectangle in the center intersects the coordinate axes counterclockwise at the following points: ${\tfrac {2}{15}}\gets 0.{\overline {00001100}}$ , ${\tfrac {1}{15}}\mathrm {i} \gets 0.{\overline {00000011}}$ , and $-{\tfrac {8}{15}}\gets 0.{\overline {11000000}}$ , and $-{\tfrac {4}{15}}\mathrm {i} \gets 0.{\overline {00110000}}$ . $S$ can be decomposed into 16 pieces congruent to ${\tfrac {1}{4}}S$ . Notice that if $S$ is rotated counterclockwise by 135°, we obtain two adjacent sets congruent to ${\tfrac {1}{\sqrt {2}}}S$ , because $(\mathrm {i} -1)S=S\cup (S+1)$ . Most importantly, $S$ contains all complex numbers that are of sufficiently small magnitude.^[12] Thus, there is an injection of the complex rectangle $[-{\tfrac {8}{15}},{\tfrac {2}{15}}]\times [-{\tfrac {4}{15}},{\tfrac {1}{15}}]\mathrm {i}$ into the interval $[0,1)$ of real numbers by mapping $\textstyle \sum _{k>0}x_{k}(\mathrm {i} -1)^{-k}\mapsto \sum _{k>0}x_{k}3^{-k}$ (hereby base $2$ cannot be taken because of $-{\tfrac {2}{5}}-{\tfrac {1}{5}}\mathrm {i} \gets 0.{\overline {1}}\neq 1$ ).

References

1 2 Knuth, D.E. (1960). "An Imaginary Number System". Communication of the ACM-3 (4).
1 2 3 Knuth, Donald (1998). "Positional Number Systems". The art of computer programming. Volume 2 (3rd ed.). Boston: Addison-Wesley. p. 205. ISBN 0-201-89684-2. OCLC 48246681.
1 2 3 Khmelnik, S.I. (1964). "Specialized digital computer for operations with complex numbers". Questions of Radio Electronics (in Russian). XII (2).
1 2 W. Penney, A "binary" system for complex numbers, JACM 12 (1965) 247-248.
1 2 Jamil, T. (2002). "The complex binary number system". IEEE Potentials. 20 (5): 39–41. doi:10.1109/45.983342.
1 2 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).
1 2 Khmelnik, S.I. (2004 (see also here)). Coding of Complex Numbers and Vectors (in Russian). «Mathematics in Computers», Israel, ISBN 978-0-557-74692-7. Check date values in: |date= (help)
1 2 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
1 2 infinite non-repeating sequence
↑ Knuth 1998 p.206

External links

"Number Systems Using a Complex Base" by Jarek Duda, the Wolfram Demonstrations Project
"The Boundary of Periodic Iterated Function Systems" by Jarek Duda, the Wolfram Demonstrations Project
"Number Systems in 3D" by Jarek Duda, the Wolfram Demonstrations Project

This article is issued from Wikipedia - version of the 7/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.