Четвертьмнимая база

Четверо -мнимая система счисления — это система счисления , впервые предложенная Дональдом Кнутом в 1960 году. В отличие от стандартных систем счисления, которые используют целое число (например, 10 в десятичной системе счисления или 2 в двоичной системе счисления) в качестве основы , она использует мнимое число 2. я (эквивалент ${\sqrt {-4}}$) в качестве его основы. Он способен ( почти ) однозначно представлять каждое комплексное число, используя только цифры 0, 1, 2 и 3. Числа меньше нуля, которые обычно обозначаются знаком минус, могут быть представлены в виде цепочек цифр в четверть-мнимом числе; например, число -1 представлено как «103» в четвертьмнимной записи.

Разложение четвертичного мнимого

В позиционной системе с базой $b$,

$\ldots d_{3}d_{2}d_{1}d_{0}.d_{-1}d_{-2}d_{-3}\ldots$

представляет $\dots +d_{3}\cdot b^{3}+d_{2}\cdot b^{2}+d_{1}\cdot b+d_{0}+d_{-1}\cdot b^{-1}+d_{-2}\cdot b^{-2}+d_{-3}\cdot b^{-3}\dots$

В этой системе счисления $b=2i$,

и потому что $(2i)^{2}=-4$, всю серию степеней можно разделить на две разные серии, так что это упрощает ${\begin{aligned}&{}[\dots +d_{4}\cdot (-4)^{2}+d_{2}\cdot (-4)^{1}+d_{0}+d_{-2}\cdot (-4)^{-1}+\dots ]\end{aligned}}$ для четных цифр (цифры, которые упрощаются до значения цифры, умноженной на степень -4), и ${\begin{aligned}2i\cdot [\dots +d_{3}\cdot (-4)^{1}+d_{1}+d_{-1}\cdot (-4)^{-1}+d_{-3}\cdot (-4)^{-2}+\dots ]\end{aligned}}$ для тех цифр, которые еще имеют мнимый множитель. Сложение этих двух серий вместе дает общее значение числа.

Из-за разделения этих двух рядов действительная и мнимая части комплексных чисел легко выражаются по основанию -4 как $\ldots d_{4}d_{2}d_{0}.d_{-2}\ldots$ и $2\cdot (\ldots d_{5}d_{3}d_{1}.d_{-1}d_{-3}\ldots )$ соответственно.

Преобразование из четверть-мнимого

Степени 2 я

к	( 2и ) к
−5	− я /32
−4	1/16
−3	я /8
−2	−1/4
−1	− я /2
0	1
1	22я
2	−4
3	-8 я
4	16
5	32 я
6	−64
7	−128 я
8	256

Чтобы преобразовать строку цифр из четвертичной мнимой системы в десятичную систему, можно использовать стандартную формулу для позиционных систем счисления. Это говорит о том, что строка цифр $\ldots d_{3}d_{2}d_{1}d_{0}$ в системе счисления b можно преобразовать в десятичное число по формуле

$\cdots +d_{3}\cdot b^{3}+d_{2}\cdot b^{2}+d_{1}\cdot b+d_{0}$

Для четвертьмнимой системы $b=2i$.

Кроме того, для данной строки $d$ в форме $d_{w-1},d_{w-2},\dots d_{0}$, формулу ниже можно использовать для заданной длины строки $w$ в базе $b$

$Q2D_{w}{\vec {d}}\equiv \sum _{k=0}^{w-1}d_{k}\cdot b^{k}$

Пример

Чтобы преобразовать строку $1101_{2i}$ в десятичное число, заполните формулу выше:

$1\cdot (2i)^{3}+1\cdot (2i)^{2}+0\cdot (2i)^{1}+1\cdot (2i)^{0}=-8i-4+0+1=-3-8i$

Другой, более длинный пример: $1030003_{2i}$ в базе 10 есть

$1\cdot (2i)^{6}+3\cdot (2i)^{4}+3\cdot (2i)^{0}=-64+3\cdot 16+3=-13$

Преобразование в четверть-мнимое

Также возможно преобразовать десятичное число в число в четвертичной мнимой системе. Каждое комплексное число (любое число вида a + bi ) имеет четвертьмнимое представление. Большинство чисел имеют уникальное четырехмнимое представление, но так же, как 1 имеет два представления 1 = 0,9 в десятичной записи, поэтому из-за 0,0001 _{2 i} = 1/15 ​ число , 1/5 0003 3 имеет два четвертьмнимых представления: 0. 2 _{i =} · 1 / 15 = 1 / 5 = 1 + 3· –4/15 ​ 1,0300 = ​ _{2 i} .

Чтобы преобразовать произвольное комплексное число в четверть-мнимое, достаточно разбить число на действительную и мнимую составляющие, преобразовать каждую из них отдельно, а затем сложить результаты, перемежая цифры. Например, поскольку −1+4 i равно −1 плюс 4 i , четвертичное мнимое представление −1+4 i представляет собой четвертичное мнимое представление −1 (а именно, 103) плюс четвертичное мнимое представление числа 4 i (а именно, 20), что дает окончательный результат −1+4 i = 123 _{2 i} .

Чтобы найти четвертьмнимое представление мнимого компонента, достаточно умножить этот компонент на 2 i , что дает действительное число; затем найдите четверть-мнимое представление этого действительного числа и, наконец, сдвиньте представление на одно место вправо (таким образом разделив на 2 i ). Например, четвертьмнимное представление 6 i вычисляется путем умножения 6 i × 2 i = −12, что выражается как 300 _{2 i} , а затем сдвига на одну позицию вправо, что дает: 6 i = 30 _{2 i} .

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

Пример: Действительное число

В качестве примера целого числа мы можем попытаться найти четверть-мнимый аналог десятичного числа 7 (или 7 _10, поскольку основание десятичной системы равно 10). Поскольку трудно точно предсказать, какой длины будет строка цифр для данного десятичного числа, можно с уверенностью предположить, что строка довольно большая. В этом случае можно выбрать строку из шести цифр. Если первоначальное предположение о размере строки в конечном итоге оказывается недостаточным, можно использовать строку большего размера.

Чтобы найти представление, сначала выпишите общую формулу и сгруппируйте члены:

${\begin{aligned}7_{10}&=d_{0}+d_{1}\cdot b+d_{2}\cdot b^{2}+d_{3}\cdot b^{3}+d_{4}\cdot b^{4}+d_{5}\cdot b^{5}\\&=d_{0}+2id_{1}-4d_{2}-8id_{3}+16d_{4}+32id_{5}\\&=d_{0}-4d_{2}+16d_{4}+i(2d_{1}-8d_{3}+32d_{5})\\\end{aligned}}$

Поскольку 7 — действительное число, допускается сделать вывод, что d ₁ , d ₃ и d ₅ должны быть равны нулю. значения коэффициентов d ₀ , d ₂ и d ₄ Теперь необходимо найти . Поскольку d ₀ - 4 d ₂ + 16 d ₄ = 7 и поскольку - по природе четвертьмнимой системы - коэффициенты могут быть только 0, 1, 2 или 3, значение коэффициентов можно найти. Возможная конфигурация может быть следующей: d ₀ = 3, d ₂ = 3 и d ₄ = 1. Эта конфигурация дает результирующую строку цифр для 7 ₁₀ .

$7_{10}=010303_{2i}=10303_{2i}.$

Пример: мнимое число

Нахождение четвертьмнимного представления чисто мнимого целого числа ∈ i Z аналогично описанному выше методу для вещественного числа. Например, чтобы найти представление 6 i , можно воспользоваться общей формулой. Тогда все коэффициенты вещественной части должны быть равны нулю, а комплексная часть должна составлять 6. Однако для 6 i легко увидеть, взглянув на формулу, что если d ₁ = 3 и все остальные коэффициенты равны нулю, мы получаем искомое струна для 6 i . То есть:

${\begin{aligned}6i_{10}=30_{2i}\end{aligned}}$

Другой метод конвертации

Для действительных чисел четвертичное мнимое представление такое же, как и отрицательное четвертичное (основание -4). Комплексное число x + iy можно преобразовать в четвертичное мнимое, преобразовав x и y /2 по отдельности в отрицательное четвертичное число. Если и x, и y — конечные двоичные дроби, мы можем использовать следующий алгоритм, используя повторное евклидово деление :

Например: 35+23i=121003,2 _2i

                35                                 23i/2i=11.5    11=12−0.5
            35÷(−4)=−8, remainder 3                12/(−4)=−3, remainder 0         (−0.5)×(−4)=2
            −8÷(−4)= 2, remainder 0                −3/(−4)= 1, remainder 1
             2÷(−4)= 0, remainder 2                 1/(−4)= 0, remainder 1
               20003                    +              101000                         +  0.2 = 121003.2
                         32i+16×2−8i−4×0+2i×0+1×3−2×i/2=35+23i

Основание точки "."

точка счисления В десятичной системе используется обычная . (точка), обозначающая разделение между целой и дробной частью числа. В четвертьмнимой системе также можно использовать точку счисления. Для цифровой строки $\dots d_{5}d_{4}d_{3}d_{2}d_{1}d_{0}.d_{-1}d_{-2}d_{-3}\dots$ точка счисления отмечает разделение между неотрицательными и отрицательными степенями b . Используя точку счисления, общая формула принимает вид:

$d_{5}b^{5}+d_{4}b^{4}+d_{3}b^{3}+d_{2}b^{2}+d_{1}b+d_{0}+d_{-1}b^{-1}+d_{-2}b^{-2}+d_{-3}b^{-3}$

или

${\begin{aligned}32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+{\frac {1}{2i}}d_{-1}+{\frac {1}{-4}}d_{-2}+{\frac {1}{-8i}}d_{-3}\\=32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}-{\frac {i}{2}}d_{-1}-{\frac {1}{4}}d_{-2}+{\frac {i}{8}}d_{-3}\end{aligned}}$

Пример

четвертьмнимое представление комплексной единицы i Если необходимо найти , формулы без точки счисления будет недостаточно. Поэтому следует использовать приведенную выше формулу. Следовательно:

${\begin{aligned}i&=32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+{\frac {1}{2i}}d_{-1}+{\frac {1}{-4}}d_{-2}+{\frac {1}{-8i}}d_{-3}\\&=i(32d_{5}-8d_{3}+2d_{1}-{\frac {1}{2}}d_{-1}+{\frac {1}{8}}d_{-3})+16d_{4}-4d_{2}+d_{0}-{\frac {1}{4}}d_{-2}\\\end{aligned}}$

для некоторых коэффициентов d _k . Тогда, поскольку действительная часть должна быть равна нулю: d ₄ = d ₂ = d ₀ = d ₋₂ = 0. Что касается мнимой части, если d ₅ = d ₃ = d ₋₃ = 0 и когда d ₁ = 1 и d ₋₁ = 2, можно найти строку цифр. Используя приведенные выше коэффициенты в строке цифр, результат:

$i=10.2_{2i}.$

Сложение и вычитание

можно складывать и вычитать В четвертьмнимой системе числа. При этом следует помнить два основных правила:

1. Если число превышает 3, вычтите 4 и «перенесите» −1 на две позиции влево.
2. Всякий раз, когда число падает ниже 0, прибавляйте 4 и «переносите» +1 на две позиции влево.

Или кратко: «Если вы прибавляете четыре, переносите +1 . Если вы вычитаете четыре, переносите −1 ». Это противоположность обычному длинному сложению, при котором «перенос» в текущем столбце требует добавления 1 к следующему столбцу слева, а «заимствование» требует вычитания. В четверть-мнимой арифметике «перенос» вычитает из следующего столбца, а «заимствование» добавляет .

Пример: Дополнение

Ниже приведены два примера сложения в четвертьмнимой системе:

   1 − 2i                1031          
   1 − 2i                1031          
   ------ +      <=>     ---- +       
   2 − 4i                1022          


   3 − 4i                1023
   1 − 8i                1001
   ------ +      <=>    ----- +
   4 −12i               12320

В первом примере мы начинаем с добавления двух единиц в первом столбце («столбец единиц»), давая 2. Затем мы добавляем две тройки во второй столбец («столбец 2 есть »), давая 6; 6 больше 3, поэтому мы вычитаем 4 (давая 2 в качестве результата во втором столбце) и переносим −1 в четвертый столбец. Добавление нулей в третьем столбце дает 0; и, наконец, добавление двух единиц и переносимого -1 в четвертом столбце дает 1.

Во втором примере мы сначала добавляем 3+1, давая 4; 4 больше 3, поэтому мы вычитаем 4 (давая 0) и переносим -1 в третий столбец («столбец -4s»). Затем мы добавляем 2+0 во второй столбец, получая 2. В третьем столбце мы имеем 0+0+(−1) из-за переноса; −1 меньше 0, поэтому мы добавляем 4 (давая 3 в качестве результата в третьем столбце) и «заимствуем» +1 в пятый столбец. В четвертом столбце 1+1 равно 2; и перенос в пятом столбце дает 1, для результата $12320_{2i}$.

Пример: Вычитание

Вычитание аналогично сложению, поскольку оно использует те же два правила, описанные выше. Ниже приведен пример:

         − 2 − 8i                       1102
           1 − 6i                       1011
           -------           <=>        -----
         − 3 − 2i                       1131

В этом примере нам нужно вычесть $1011_{2i}$ от $1102_{2i}$. Самая правая цифра — 2−1 = 1. Вторая цифра справа станет —1, поэтому прибавьте 4, чтобы получить 3, а затем перенесите +1 на две позиции влево. Третья цифра справа равна 1–0 = 1. Тогда самая левая цифра равна 1–1 плюс 1 от переноса, что дает 1. Это дает окончательный ответ: $1131_{2i}$.

Умножение

Для длинного умножения в четвертьмнимой системе также используются два изложенных выше правила. При умножении чисел умножьте первую строку последовательно на каждую цифру второй строки и сложите полученные строки. При каждом умножении цифра второй строки умножается на первую строку. Умножение начинается с самой правой цифры во второй строке, а затем перемещается влево на одну цифру, умножая каждую цифру на первую строку. Затем складываются полученные частичные произведения, каждое из которых сдвигается влево на одну цифру. Пример:

              11201
              20121  ×
        ---------------
              11201      ←––– 1 × 11201
             12002       ←––– 2 × 11201
            11201        ←––– 1 × 11201
           00000         ←––– 0 × 11201
          12002      +   ←––– 2 × 11201
        ---------------
          120231321

Это соответствует умножению $(9-8i)\cdot (29+4i)=293-196i$.

Табличные конверсии

Ниже приведена таблица некоторых десятичных и комплексных чисел, а также их четвертьмнимных аналогов.

База 10	База 2 я
1	1
2	2
3	3
4	10300
5	10301
6	10302
7	10303
8	10200
9	10201
10	10202
11	10203
12	10100
13	10101
14	10102
15	10103
16	10000

База 10	База 2 я
−1	103
−2	102
−3	101
−4	100
−5	203
−6	202
−7	201
−8	200
−9	303
−10	302
−11	301
−12	300
−13	1030003
−14	1030002
−15	1030001
−16	1030000

База 10	База 2 я
1 я	10.2
22я	10.0
3 я	20.2
4 я	20.0
5 я	30.2
6 я	30.0
77и	103000.2
8 я	103000.0
9 я	103010.2
10 я	103010.0
11 я	103020.2
12 я	103020.0
13 я	103030.2
14 я	103030.0
15 я	102000.2
16 я	102000.0

База 10	База 2 я
−1 я	0.2
−2 я	1030.0
−3 я	1030.2
−4 я	1020.0
-5 я	1020.2
−6 я	1010.0
−7 я	1010.2
-8 я	1000.0
−9 я	1000.2
−10 я	2030.0
−11 я	2030.2
−12 я	2020.0
−13 я	2020.2
−14 я	2010.0
−15 я	2010.2
−16 я	2000.0

Примеры

Ниже приведены некоторые другие примеры преобразования десятичных чисел в четверть-мнимые числа.

$5=16+(3\cdot -4)+1=10301_{2i}$

$i=2i+2\left(-{\frac {1}{2}}i\right)=10.2_{2i}$

$7{\frac {3}{4}}-7{\frac {1}{2}}i=1(16)+1(-8i)+2(-4)+1(2i)+3\left(-{\frac {1}{2}}i\right)+1\left(-{\frac {1}{4}}\right)=11210.31_{2i}$

Кривая Z-порядка

Представительство

$z=\sum _{k\geq n}z_{k}\cdot (2i)^{-k}$

произвольного комплексного числа $z\in \mathbb {C}$ с $z_{k}\in \{0,1,2,3\}$ приводит к инъективному отображению

$\textstyle {\begin{array}{llcl}\varphi \colon &\mathbb {C} &\to &\mathbb {R} \\&\sum _{k\geq n}z_{k}\cdot (2i)^{-k}&\mapsto &\sum _{k\geq n}z_{k}\cdot r^{-k}\\\end{array}}$

с некоторыми подходящими $r\in \mathbb {Z}$. Здесь $r=4$ не может быть принят за основу из-за

$\textstyle \sum _{k>0}3\cdot (2i)^{-k}={\tfrac {-3-6i}{5}}\;\;\;\;\neq \;\;\;\;1=\sum _{k>0}3\cdot 4^{-k}.$

Изображение ​ $\varphi (\mathbb {C} )\subset \mathbb {R}$ представляет собой множество Кантора , которое позволяет линейно упорядочивать $\mathbb {C}$ похоже на кривую Z-порядка . Поскольку изображение отключено, $\varphi$ не является непрерывным .

См. также

• Четвертичная система счисления
• Комплексно-базовая система
• Отрицательная база

Дальнейшее чтение

• Кнут, Дональд Эрвин . «Позиционные системы счисления». Искусство компьютерного программирования . Том. 2 (3-е изд.). Аддисон-Уэсли . п. 205.
• Уоррен-младший, Генри С. (2013) [2002]. Хакерское наслаждение (2-е изд.). Аддисон Уэсли - Pearson Education, Inc. с. 309. ИСБН  978-0-321-84268-8 . 0-321-84268-5.