Комплексно-базовая система

В арифметике комплексно -основная система — это позиционная система счисления, которой основание — мнимое ( предложено Дональдом Кнутом в 1955 году) . ^[1]^[2]) или комплексное число (предложил С. Хмельник в 1964 г. ^[3] и Уолтер Ф. Пенни в 1965 году. ^[4]^[5]^[6]).

В общем

Позволять $D$ быть целостным доменом $\subset \mathbb {C}$ , и $|\cdot |$ ( архимедова ) абсолютная величина на нем.

Число $X\in D$ в позиционной системе счисления представляется как расширение

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

где

$\rho \in D$		это основание (или основание ) с $\|\rho \|>1$ ,
$\nu \in \mathbb {Z}$		показатель степени (позиция или место),
$x_{\nu }$		это цифры из конечного набора цифр $Z\subset D$ , обычно с $\|x_{\nu }\|<\|\rho \|.$

Мощность $R:=|Z|$ называется уровнем разложения .

Позиционная система счисления или система кодирования представляет собой пару

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

с основанием $\rho$ и набор цифр $Z$ , и запишем стандартный набор цифр с помощью $R$ цифры как

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

Желательными являются системы кодирования, обладающие признаками:

Каждое число в $D$ , э. г. целые числа $\mathbb {Z}$ , гауссовы целые числа $\mathbb {Z} [\mathrm {i} ]$ или целые числа $\mathbb {Z} [{\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}}]$ , однозначно представимо в виде конечного кода, возможно, со знаком ±.
Каждое число в области дробей $K:=\operatorname {Quot} (D)$ , что, возможно, завершается для метрики, заданной выражением $|\cdot |$ уступчивость $K:=\mathbb {R}$ или $K:=\mathbb {C}$ , представимо в виде бесконечного ряда $X$ который сходится под $|\cdot |$ для $\nu \to -\infty$ , а мера множества чисел с более чем одним представлением равна 0. Последнее требует, чтобы набор $Z$ быть минимальным, т.е. $R=|\rho |$ для действительных чисел и $R=|\rho |^{2}$ для комплексных чисел.

В реальных цифрах

В этих обозначениях наша стандартная схема десятичного кодирования обозначается

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

стандартная двоичная система

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

система негабинарная

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

и сбалансированная тройная система ^[2] является

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

Все эти системы кодирования имеют упомянутые особенности для $\mathbb {Z}$ и $\mathbb {R}$ , а последние два не требуют знака.

В комплексных числах

Хорошо известные позиционные системы счисления комплексных чисел включают следующие ( $\mathrm {i}$ мнимая единица ):

$\left\langle {\sqrt {R}},Z_{R}\right\rangle$ , например $\left\langle \pm \mathrm {i} {\sqrt {2}},Z_{2}\right\rangle$ ^[1] и

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

, ^[2] , четвертьвоображаемая база предложенная Дональдом Кнутом в 1955 году.

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

\left\langle {\sqrt {2}}e^{\pm {\tfrac {3\pi }{4}}\mathrm {i} }=-1\pm \mathrm {i} ,Z_{2}\right\rangle

^[3]^[5] (см. также раздел «База −1 ± i» ниже).

$\left\langle {\sqrt {R}}e^{\mathrm {i} \varphi },Z_{R}\right\rangle$ , где $\varphi =\pm \arccos {(-\beta /(2{\sqrt {R}}))}$ , $\beta <\min(R,2{\sqrt {R}})$ и $\beta _{}^{}$ — положительное целое число, которое может принимать несколько значений в заданный момент $R$ . ^[7] Для $\beta =1$ и $R=2$ это система

\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$ , где множество $A_{R}^{2}$ состоит из комплексных чисел $r_{\nu }=\alpha _{\nu }^{1}+\alpha _{\nu }^{2}\mathrm {i}$ и числа $\alpha _{\nu }^{}\in Z_{R}$ , например

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

^[8]

$\left\langle \rho =\rho _{2},Z_{2}\right\rangle$ , где $\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]

Двоичные системы

Двоичные системы кодирования комплексных чисел, т.е. системы с цифрами. $Z_{2}=\{0,1\}$ , представляют практический интерес. ^[9]Ниже перечислены некоторые системы кодирования. $\langle \rho ,Z_{2}\rangle$ (все это частные случаи описанных выше систем) и соотв. коды для (десятичных) чисел $-1, 2, -2, i$ .Стандартная двоичная (для которой требуется знак, первая строка) и «негабинарная» системы (вторая строка) также перечислены для сравнения. У них нет настоящего расширения для $i$ .

Некоторые основы и некоторые представления ^[10]
Радикс	–1 ←	2 ←	–2 ←	$я$ ←	Близнецы и тройни
2	–1	10	–10	$я$	1 ←	0. 1 = 1. 0
–2	11	110	10	$я$	⁠ 1 / 3 ⁠ ←	0. 01 = 1. 10
$\mathrm {i} {\sqrt {2}}$	101	10100	100	10.101010100... ^[11]	${\frac {1}{3}}+{\frac {1}{3}}\mathrm {i} {\sqrt {2}}$ ←	0. 0011 = 11. 1100
${\frac {-1+\mathrm {i} {\sqrt {7}}}{2}}$	111	1010	110	11.110001100... ^[11]	${\frac {3+\mathrm {i} {\sqrt {7}}}{4}}$ ←	1. 011 = 11. 101 = 11100. 110
$\rho _{2}$	101	10100	100	10	⁠ 1 / 3 ⁠ + ⁠ 1 / 3 ⁠ $i$ ←	0. 0011 = 11. 1100
–1+ $я$	11101	1100	11100	11	⁠ 1 / 5 ⁠ + ⁠ 3 / 5 ⁠ $i$ ←	0. 010 = 11. 001 = 1110. 100
2 $я$	103	2	102	10.2	⁠ 1 / 5 ⁠ + ⁠ 2 / 5 ⁠ $i$ ←	0. 0033 = 1. 3003 = 10. 0330 = 11. 3300

Как и во всех позиционных системах счисления с архимедовым абсолютным значением , существуют числа с множественным представлением . Примеры таких чисел приведены в правом столбце таблицы. Все они являются повторяющимися дробями , повторение которых отмечено горизонтальной чертой над ним.

Если набор цифр минимален, то набор таких чисел имеет меру 0. Так обстоит дело со всеми упомянутыми системами кодирования.

Почти бинарная четвертьмнимая система указана в нижней строке для целей сравнения. Там действительная и мнимая части чередуются.

База $-1 \pm я$

Комплексные числа с целой частью, все нули в $счисления i - 1.$ системе

Особый интерес представляют четвертьмнимая база (база $2 i$ ) и системы с базой $-1 \pm i,$ обсуждаемые ниже, обе из которых могут использоваться для конечного представления гауссовских целых чисел без знака.

Основание $-1 \pm i$ с использованием цифр $0$ и $1$ было предложено С. Хмельником в 1964 году. ^[3] и Уолтер Ф. Пенни в 1965 году. ^[4]^[6]

Связь с драконом-близнецом

Область округления целого числа, т. е. набора $S$ комплексных (нецелых) чисел, которые разделяют целую часть своего представления в этой системе, имеет в комплексной плоскости фрактальную форму: близнец-дракон (см. рисунок). Этот набор $S$ по определению, это все точки, которые можно записать как $\textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}$ с $x_{k}\in Z_{2}$ . $S$ можно разложить на 16 частей, соответствующих ${\tfrac {1}{4}}S$ . Обратите внимание, что если $S$ повернут против часовой стрелки на 135°, получим два соседних множества, конгруэнтных ${\tfrac {1}{\sqrt {2}}}S$ , потому что $(\mathrm {i} -1)S=S\cup (S+1)$ . Прямоугольник $R\subset S$ в центре пересекает оси координат против часовой стрелки в следующих точках: ${\tfrac {2}{15}}\gets 0.{\overline {00001100}}$ , ${\tfrac {1}{15}}\mathrm {i} \gets 0.{\overline {00000011}}$ , и $-{\tfrac {8}{15}}\gets 0.{\overline {11000000}}$ , и $-{\tfrac {4}{15}}\mathrm {i} \gets 0.{\overline {00110000}}$ . Таким образом, $S$ содержит все комплексные числа с абсолютным значением ≤ ⁠ 1 / 15 ⁠ . ^[12]

Как следствие, происходит инъекция комплексного прямоугольника

[-{\tfrac {8}{15}},{\tfrac {2}{15}}]\times [-{\tfrac {4}{15}},{\tfrac {1}{15}}]\mathrm {i}

в интервал $[0,1)$ действительных чисел путем отображения

\textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}\mapsto \sum _{k\geq 1}x_{k}b^{-k}

с $b>2$ . ^[13]

Кроме того, существуют два отображения

{\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}}

и

{\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}}

оба сюръективны , что приводит к сюръективному (таким образом, заполняющему пространство) отображению

[0,1)\qquad \to \qquad S

которая, однако, не является непрерывной и, следовательно, не является кривой заполняющей пространство , . Но очень близкий родственник, дракон Дэвиса-Кнута , представляет собой непрерывную кривую, заполняющую пространство.

См. также

Кривая дракона

Ссылки

↑ Перейти обратно: Перейти обратно: ^а ^б Кнут, DE (1960). «Воображаемая система счисления» . Коммуникации АКМ . 3 (4): 245–247. дои : 10.1145/367177.367233 . S2CID 16513137 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Кнут, Дональд (1998). «Позиционные системы счисления». Искусство компьютерного программирования . Том. 2 (3-е изд.). Бостон: Аддисон-Уэсли. п. 205. ИСБН 0-201-89684-2 . OCLC 48246681 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Хмельник С.И. (1964). «Специализированная цифровая машина для операций с комплексными числами». Вопросы радиоэлектроники (на русском языке) . XII (2).
↑ Перейти обратно: Перейти обратно: ^а ^б У. Пенни, «Двоичная» система комплексных чисел, JACM 12 (1965) 247–248.
↑ Перейти обратно: Перейти обратно: ^а ^б Джамиль, Т. (2002). «Сложная двоичная система счисления». Возможности IEEE . 20 (5): 39–41. дои : 10.1109/45.983342 .
↑ Перейти обратно: Перейти обратно: ^а ^б Дуда, Ярек (24 февраля 2008 г.). «Сложные системы счисления». arXiv : 0712.1309 [ math.DS ].
^ Хмельник, С.И. (1966). «Позиционное кодирование комплексных чисел». Вопросы радиоэлектроники (на русском языке) . XII (9).
↑ Перейти обратно: Перейти обратно: ^а ^б Хмельник, С.И. (2004). Кодирование комплексных чисел и векторов (на русском языке) (PDF) . Израиль: Математика в компьютере. ISBN 978-0-557-74692-7 .
↑ Перейти обратно: Перейти обратно: ^а ^б Хмельник, С.И. (2001). Метод и система обработки комплексных чисел . Патент США, US2003154226 (А1).
^ Уильям Дж. Гилберт, «Арифметика в комплексных базисах», математический журнал, том. 57, № 2, март 1984 г.
↑ Перейти обратно: Перейти обратно: ^а ^б бесконечная неповторяющаяся последовательность
^ Кнут 1998 стр.206
^ База $b=2$ нельзя взять, потому что оба, $\textstyle 2^{-1}=0.1_{\text{bin}}=0.5_{\text{dec}}$ и $\textstyle \sum _{k\geq 2}2^{-k}=0.0{\overline {1}}_{\text{bin}}=0.1_{\text{bin}}=0.5_{\text{dec}}$ . Однако, $\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}$ не равно $\textstyle \sum _{k\geq 2}(\mathrm {i} -1)^{-k}=0.1_{\text{dec}}+0.3_{\text{dec}}\mathrm {i}$ .

Внешние ссылки

« Системы счисления, использующие сложное основание », Ярек Дуда, демонстрационный проект Wolfram
« Граница периодических итерированных функциональных систем », Ярек Дуда, демонстрационный проект Wolfram
« Системы счисления в 3D », Ярек Дуда, демонстрационный проект Wolfram
« Большое введение в сложные системы счисления » с источниками Mathematica Ярека Дуды

[Knuth1-1] Перейти обратно: Перейти обратно: ^а ^б Кнут, DE (1960). «Воображаемая система счисления» . Коммуникации АКМ . 3 (4): 245–247. дои : 10.1145/367177.367233 . S2CID 16513137 .

[Knuth2-2] Перейти обратно: Перейти обратно: ^а ^б ^с Кнут, Дональд (1998). «Позиционные системы счисления». Искусство компьютерного программирования . Том. 2 (3-е изд.). Бостон: Аддисон-Уэсли. п. 205. ИСБН 0-201-89684-2 . OCLC 48246681 .

[Khmelnik1-3] Перейти обратно: Перейти обратно: ^а ^б ^с Хмельник С.И. (1964). «Специализированная цифровая машина для операций с комплексными числами». Вопросы радиоэлектроники (на русском языке) . XII (2).

[Penney0-4] Перейти обратно: Перейти обратно: ^а ^б У. Пенни, «Двоичная» система комплексных чисел, JACM 12 (1965) 247–248.

[Penney1-5] Перейти обратно: Перейти обратно: ^а ^б Джамиль, Т. (2002). «Сложная двоичная система счисления». Возможности IEEE . 20 (5): 39–41. дои : 10.1109/45.983342 .

[Penney2-6] Перейти обратно: Перейти обратно: ^а ^б Дуда, Ярек (24 февраля 2008 г.). «Сложные системы счисления». arXiv : 0712.1309 [ math.DS ].

[Khmelnik2-7] Хмельник, С.И. (1966). «Позиционное кодирование комплексных чисел». Вопросы радиоэлектроники (на русском языке) . XII (9).

[Khmelnik3-8] Перейти обратно: Перейти обратно: ^а ^б Хмельник, С.И. (2004). Кодирование комплексных чисел и векторов (на русском языке) (PDF) . Израиль: Математика в компьютере. ISBN 978-0-557-74692-7 .

[Khmelnik4-9] Перейти обратно: Перейти обратно: ^а ^б Хмельник, С.И. (2001). Метод и система обработки комплексных чисел . Патент США, US2003154226 (А1).

[Gilbert-10] Уильям Дж. Гилберт, «Арифметика в комплексных базисах», математический журнал, том. 57, № 2, март 1984 г.

[infinite-11] Перейти обратно: Перейти обратно: ^а ^б бесконечная неповторяющаяся последовательность

[12] Кнут 1998 стр.206

[13] База $b=2$ нельзя взять, потому что оба, $\textstyle 2^{-1}=0.1_{\text{bin}}=0.5_{\text{dec}}$ и $\textstyle \sum _{k\geq 2}2^{-k}=0.0{\overline {1}}_{\text{bin}}=0.1_{\text{bin}}=0.5_{\text{dec}}$ . Однако, $\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}$ не равно $\textstyle \sum _{k\geq 2}(\mathrm {i} -1)^{-k}=0.1_{\text{dec}}+0.3_{\text{dec}}\mathrm {i}$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]