Комплексная и кватернионная системы счисления
Когда-то у Кнута прочитал про красивейшую систему счисления, имеющую основание i-1.
В каждом разряде может стоять нуль либо единица, и тогда строчка anan-1...a1a0 выражает следующее число:
_{i-1}=a_n(i-1)^n+a_{n-1}(i-1)^{n-1}+\dots+a_1(i-1)+a_0)
Вот, для примера, первые 16 чисел:
0000i-1= 0,
0001i-1= 1,
0010i-1= -1 + i,
0011i-1= i,
0100i-1= - 2i,
0101i-1= 1 - 2i,
0110i-1= -1 - i,
0111i-1= - i,
1000i-1= 2 + 2i,
1001i-1= 3 + 2i,
1010i-1= 1 + 3i,
1011i-1= 2 + 3i,
1100i-1= 2,
1101i-1= 3,
1110i-1= 1 + i,
1111i-1= 2 + i.
На гифке показано заполнение плоскости с помощью 8-битных чисел в этой системе счисления. Получается фрактальная структура, "Дракон". Довольно своеобразно: нам понадобилось 4 бита, чтобы, наконец-то получить ДВОЙКУ, а вот число "-1" даже на 4 битах не появилось, оно выражается как 11101i-1, это же очевидно :)
Но при этом гарантируется, что любое число с целой действительной и мнимой частью таким способом представить МОЖНО. А можно, разумеется, пойти и вправо, т.е ввести "дробную часть", и в итоге получить необходимую точность.
Если в обычном двоичном коде даже представление отрицательных чисел является головной болью (дополнительный код требует "расширения знака", т.е 8-битное число 0xFF = -1 при переводе в 16-битное представление должно превратиться в 0xFFFF, НЕЛЬЗЯ ПРОСТО ВЗЯТЬ И ПОСТАВИТЬ СПЕРЕДИ НУЛИ), а здесь естественным образом у нас и знак появился, и ДВЕ компоненты, действительная и мнимая! Спереди числа можно добавлять сколько угодно нулей - это ни на что не влияет.
Сумматор для таких чисел, будто бы, не сильно отличается от обычного двоичного, а умножитель - не отличается ВООБЩЕ (т.е сдвиг + сумматор для комплексных чисел), и в них оказываются "вшиты" правила работы с комплексными числами! По крайней мере, пока это на бумаге.
Подумаем, как это реализовать "в железе", и можно ли придумать КВАТЕРНИОННУЮ систему счисления, где подобным образом представим ЛЮБОЙ КВАТЕРНИОН?
Сложение выполняется, как обычно, "в столбик", но перенос реализуется сложнее, поскольку 2 = 1100i-1, т.е "единичку" надо перенести не в соседний разряд, а ЧЕРЕЗ ОДИН и ЧЕРЕЗ ДВА! Попробуем по таким правилам посчитать, чему равно 2+2?
Выходит:
Как видим, два переноса "наложились друг на друга", в результате чего, хоть разрядность исходных чисел давно закончилась, а мы продолжили переносить, с 4-битных чисел перейдя к 9-битному!
Обычно при проектировании АЛУ начинают рассмотрение с полусумматора, который складывает однобитные числа и выдаёт ответ и перенос. Затем переходят к полному сумматору, который складывает два однобитных числа и бит переноса. Он уже посложнее, но на одном ЛЭ в ПЛИС реализуется. Этому не надо удивляться: штука очевидно очень нужная, поэтому саму по себе структуру ЛЭ в ПЛИС придумывали в том числе под такое применение.
Но нам, выходит, нужен сумматор 4 значений!
И самое неприятное: если нам так "повезёт" на четыре единицы, то мы не обойдёмся переносом "двойки" - придётся справляться с четвёркой, а она, как мы знаем, занимает 9 бит!!!
Может, мы плохо выбрали основание для этой системы счисления? Увы, это чуть ли не лучшее, которое можно придумать. Если мы хотим однозначного представления чисел, модуль нашего основания должен равняться корню из двух. Дело в том, что один бит "снижает неопределённость ровно вдвое". Пока мы представляли целые числа, т.е работали на числовой оси, имея по одному биту в каждом разряде (т.е доступные цифры только 0 или 1), мы неизбежно получали основание 2. Например, чтобы "загадать" число от 0 до 15, мы сначала "спрашиваем": оно больше или равно восьми? Ответ на этот вопрос записываем в старший разряд (0: нет, 1: да). Неопределённость сократилась вдвое, и следующий вопрос: больше или равно середине оставшегося интервала? И так, пока не надоест. Но в случае с комплексными числами, мы имеем дело с числовой плоскостью, и тут, чтобы сократить СТОРОНУ квадрата вдвое, нужно затратить два бита, т.е поделить квадрат на 4 части. И для единообразия, каждый следующий разряд должен иметь вес отличающийся в КОРЕНЬ ИЗ ДВУХ раз. "Красивых" оснований (т.е имеющих целые числа в действительной и комплексной части) всего 4: 1+i, 1-i, i-1, -i-1.
Основание i-1 мы рассмотрели. Давайте посмотрим на 1+i:
Вообще финиш: мы как ушли от начала координат, так и с концами! Двойки пока нет, минус единицы нет, числа i нет! Причём Кнут утверждает, что число i так и не появится, сколько бы мы бит не нарастили "слева" (т.е в сторону увеличения чисел). Оно появится лишь как бесконечная "двоичная" дробь, кажется, 0.11111.... В общем, так себе...
Можно ещё взглянуть на 1-i, вдруг оно получше?
Таже проблема: мы куда-то ушли от центра, толком его не "исследовав". Оно, в принципе, понятно: умножение на 1+i приводит к повороту на 45° против часовой стрелки, а умножение на 1-i - по часовой стрелке. В любом случае, получаем нечто похожее на медленно раскручивающуюся спираль. Первый раз она отошла от центра, потом, как будто бы хочет вернуться, но поскольку к тому времени амплитуда возросла, она через центр "перескакивает", и так раз за разом.
Вариант i-1 хорош тем, что мы получаем поворот на 135° против часовой стрелки, т.е при столь же неторопливом росте амплитуды мы шустрее оборачиваемся, благодаря чему заполняем плоскость плотно! И тогда можно предположить, что вариант -i-1 столь же неплох, только в зеркальном отражении. Проверим:
Так оно и есть.
Но какой из этих двух вариантов (i-1 либо -i-1) мы бы не взяли, двойка будет выражаться одинаково, 1100, т.е "двойного переноса" не избежать!
Можно взять основание системы счисления
, в таком случае никаких фракталов не остаётся, а число довольно легко разделяется на действительную и мнимую части:
_{i\sqrt{2}}=a_{2n-1}(i\sqrt{2})^{2n-1}+a_{2n-2}(i\sqrt{2})^{2n-2}+\dots+a_1i\sqrt{2}+a_0=)
^{n-1}+a_{2n-2}(-2)^{n-1}+\dots+a_{1}i\sqrt{2}+a_{0}=)
^{n-1}+a_{2n-4}(-2)^{n-2}+\dots+a_2(-2)+a_0\right)+i\sqrt{2}\left(a_{2n-1}(-2)^{n-1}+a_{2n-3}(-2)^{n-2}+\dots+a_3(-2)+a_1\right))
Но даже здесь с переносами всё не так просто! Теперь у нас и действительная, и мнимая части работают по "основанию (-2)", т.е веса разрядов 1, -2, 4, -8, и так далее. Поэтому двойка выражается здесь как 110-2, т.е снова имеем два переноса, которые могут натворить бед. Только теперь, впридачу, у нас мнимая часть оказывается домножена на корень из двух. Т.е, число i может быть представлено только в виде бесконечной периодической дроби, равно как и 2i, 3i, и пр. Как-то это немного неприятно...
Вернёмся к основанию i-1, там Кнут заметил ещё одну подлянку! Ладно, что у нас очень "длинные" переносы, из 4-битных чисел у нас вдруг получается 9-битное. Но если пытаться делать переносы, пока они "сами собой" не затухнут, мы можем вообще попасть в бесконечный цикл! Причём далеко за примером ходить не надо: затруднения возникнут на простейшем выражении (-1)+1 ! Впрочем, с точки зрения реализации это не должно нас сильно пугать: зная, что практике имеем дело с конечными числами, мы сразу определяем необходимую разрядность результата, чтобы он заведомо поместился, и уже из старших разрядов перенос уходит "в никуда". Очевидно, с основанием -i-1 будет та же фигня.
С умножением всё куда проще, при условии, что сложение уже реализовано. Это у нас полноценные позиционные системы счисления, сдвиг на единицу влево эквивалентен умножению на основание системы счисления, в нашем случае i-1. Попробуем посчитать 2·2:
1100
* 1100
---------
1100
1100
---------
111010000
Это 9-битное число мы уже знаем, оно же получалось для 2+2. Это четвёрка!
Предварительный итог
Есть в этом всём определённая красота: с помощью всего двух цифр, 0 и 1, в одной-единственной битовой строке, мы записываем комплексные числа, не прибегая даже к дополнительному коду со всеми его заскоками!
Но да: из обычного представления довольно нетривиально прийти к этому, а потом и назад. Впрочем, из десятичной в двоичную и назад преобразовывать тоже не сахар, но как-то смирились, так что и здесь смириться можно было бы.
Плюс к тому, есть сложности с обработкой больших чисел. Если в обычной арифметике сложить два больших (больше размера слова, с которым оперирует АЛУ) числа не представляет труда, нужен лишь один бит переноса, то здесь одним битом переноса мы не обойдёмся, их прилично больше выйдет. Да и с небольшими числами тоже трудности, сумматор заметно сложнее обычного бинарного. Хотя не удивлюсь, если есть довольно красивые решения, возможно в несколько этапов.
А кватернионы?
Вот это было бы очень интересно! Всё-таки умножение комплексных чисел это ещё цветочки, а вот свести умножение кватернионов к самому простому умножению - уже повеселее.
Кажется, что можно пойти такой же дорожкой: основанием системы счисления выбрать какой-то хитрый кватернион, и затем "по аналогии" всё сойдётся. Я поначалу думал о чём-то вроде 1/2(1+i+j+k). Не вышло, тогда переключился на i+j+k, опять не то. Причём я был готов и на использование чуть большего количества цифр, чем просто 0 и 1. Например, для представления комплексных есть вполне разумное основание 2i, "мнимочетверичная система счисления". Чтобы она нормально заработала, нужно использовать цифры 0,1,2,3.
Увы, позиционная система счисления для кватернионов невозможна! По крайней мере, если мы под этим понимаем следующее выражение:
_{\Lambda}=a_n\Lambda^n+a_{n-1}\Lambda^{n-1}+\dots+a_1\Lambda+a_0)
Причина очень проста: в кватернионе Λ мы можем выбрать определённое направление, его векторную/мнимую компоненту. При возведении в квадрат, векторная компонента останется коллинеарна исходной, поскольку векторное произведение равно нулю (вектор умножается на самого себя), и остаётся лишь умножение на скалярную компоненту, что не меняет направления.
Поэтому сколько разрядов мы бы не привели, мы в итоге начнём выражать лишь числа, расположенные в определённой плоскости, вложенной в четырёхмерное пространство кватернионов. В этой плоскости содержатся числа (1;0;0;0) и (0;nx, ny, nz). А мы-то надеялись всё четырёхмерное пространство потихонечку замостить своими числами...
В общем, очередную бредовую идею пока что отсекаем. На очереди ещё парочка, вроде проективной геометрической алгебры и дуальных кватернионов. Но пока не получается всю задачу целиком уместить в это "прокрустово ложе", всё равно, хочешь не хочешь - а надо к линейной алгебре переходить с матрицей 6×6 и вектором 6×1, и красивой записи для них я пока найти не могу, так, чтобы оно "естественным образом" было встроено в числовую систему. До поры до времени всё хорошо, а потом я это всё "ломаю через колено"...
В каждом разряде может стоять нуль либо единица, и тогда строчка anan-1...a1a0 выражает следующее число:
Вот, для примера, первые 16 чисел:
0000i-1= 0,
0001i-1= 1,
0010i-1= -1 + i,
0011i-1= i,
0100i-1= - 2i,
0101i-1= 1 - 2i,
0110i-1= -1 - i,
0111i-1= - i,
1000i-1= 2 + 2i,
1001i-1= 3 + 2i,
1010i-1= 1 + 3i,
1011i-1= 2 + 3i,
1100i-1= 2,
1101i-1= 3,
1110i-1= 1 + i,
1111i-1= 2 + i.
На гифке показано заполнение плоскости с помощью 8-битных чисел в этой системе счисления. Получается фрактальная структура, "Дракон". Довольно своеобразно: нам понадобилось 4 бита, чтобы, наконец-то получить ДВОЙКУ, а вот число "-1" даже на 4 битах не появилось, оно выражается как 11101i-1, это же очевидно :)
Но при этом гарантируется, что любое число с целой действительной и мнимой частью таким способом представить МОЖНО. А можно, разумеется, пойти и вправо, т.е ввести "дробную часть", и в итоге получить необходимую точность.
Если в обычном двоичном коде даже представление отрицательных чисел является головной болью (дополнительный код требует "расширения знака", т.е 8-битное число 0xFF = -1 при переводе в 16-битное представление должно превратиться в 0xFFFF, НЕЛЬЗЯ ПРОСТО ВЗЯТЬ И ПОСТАВИТЬ СПЕРЕДИ НУЛИ), а здесь естественным образом у нас и знак появился, и ДВЕ компоненты, действительная и мнимая! Спереди числа можно добавлять сколько угодно нулей - это ни на что не влияет.
Сумматор для таких чисел, будто бы, не сильно отличается от обычного двоичного, а умножитель - не отличается ВООБЩЕ (т.е сдвиг + сумматор для комплексных чисел), и в них оказываются "вшиты" правила работы с комплексными числами! По крайней мере, пока это на бумаге.
Подумаем, как это реализовать "в железе", и можно ли придумать КВАТЕРНИОННУЮ систему счисления, где подобным образом представим ЛЮБОЙ КВАТЕРНИОН?
Сложение выполняется, как обычно, "в столбик", но перенос реализуется сложнее, поскольку 2 = 1100i-1, т.е "единичку" надо перенести не в соседний разряд, а ЧЕРЕЗ ОДИН и ЧЕРЕЗ ДВА! Попробуем по таким правилам посчитать, чему равно 2+2?
Выходит:
Как видим, два переноса "наложились друг на друга", в результате чего, хоть разрядность исходных чисел давно закончилась, а мы продолжили переносить, с 4-битных чисел перейдя к 9-битному!
Обычно при проектировании АЛУ начинают рассмотрение с полусумматора, который складывает однобитные числа и выдаёт ответ и перенос. Затем переходят к полному сумматору, который складывает два однобитных числа и бит переноса. Он уже посложнее, но на одном ЛЭ в ПЛИС реализуется. Этому не надо удивляться: штука очевидно очень нужная, поэтому саму по себе структуру ЛЭ в ПЛИС придумывали в том числе под такое применение.
Но нам, выходит, нужен сумматор 4 значений!
И самое неприятное: если нам так "повезёт" на четыре единицы, то мы не обойдёмся переносом "двойки" - придётся справляться с четвёркой, а она, как мы знаем, занимает 9 бит!!!
Может, мы плохо выбрали основание для этой системы счисления? Увы, это чуть ли не лучшее, которое можно придумать. Если мы хотим однозначного представления чисел, модуль нашего основания должен равняться корню из двух. Дело в том, что один бит "снижает неопределённость ровно вдвое". Пока мы представляли целые числа, т.е работали на числовой оси, имея по одному биту в каждом разряде (т.е доступные цифры только 0 или 1), мы неизбежно получали основание 2. Например, чтобы "загадать" число от 0 до 15, мы сначала "спрашиваем": оно больше или равно восьми? Ответ на этот вопрос записываем в старший разряд (0: нет, 1: да). Неопределённость сократилась вдвое, и следующий вопрос: больше или равно середине оставшегося интервала? И так, пока не надоест. Но в случае с комплексными числами, мы имеем дело с числовой плоскостью, и тут, чтобы сократить СТОРОНУ квадрата вдвое, нужно затратить два бита, т.е поделить квадрат на 4 части. И для единообразия, каждый следующий разряд должен иметь вес отличающийся в КОРЕНЬ ИЗ ДВУХ раз. "Красивых" оснований (т.е имеющих целые числа в действительной и комплексной части) всего 4: 1+i, 1-i, i-1, -i-1.
Основание i-1 мы рассмотрели. Давайте посмотрим на 1+i:
Вообще финиш: мы как ушли от начала координат, так и с концами! Двойки пока нет, минус единицы нет, числа i нет! Причём Кнут утверждает, что число i так и не появится, сколько бы мы бит не нарастили "слева" (т.е в сторону увеличения чисел). Оно появится лишь как бесконечная "двоичная" дробь, кажется, 0.11111.... В общем, так себе...
Можно ещё взглянуть на 1-i, вдруг оно получше?
Таже проблема: мы куда-то ушли от центра, толком его не "исследовав". Оно, в принципе, понятно: умножение на 1+i приводит к повороту на 45° против часовой стрелки, а умножение на 1-i - по часовой стрелке. В любом случае, получаем нечто похожее на медленно раскручивающуюся спираль. Первый раз она отошла от центра, потом, как будто бы хочет вернуться, но поскольку к тому времени амплитуда возросла, она через центр "перескакивает", и так раз за разом.
Вариант i-1 хорош тем, что мы получаем поворот на 135° против часовой стрелки, т.е при столь же неторопливом росте амплитуды мы шустрее оборачиваемся, благодаря чему заполняем плоскость плотно! И тогда можно предположить, что вариант -i-1 столь же неплох, только в зеркальном отражении. Проверим:
Так оно и есть.
Но какой из этих двух вариантов (i-1 либо -i-1) мы бы не взяли, двойка будет выражаться одинаково, 1100, т.е "двойного переноса" не избежать!
Можно взять основание системы счисления
, в таком случае никаких фракталов не остаётся, а число довольно легко разделяется на действительную и мнимую части:
Но даже здесь с переносами всё не так просто! Теперь у нас и действительная, и мнимая части работают по "основанию (-2)", т.е веса разрядов 1, -2, 4, -8, и так далее. Поэтому двойка выражается здесь как 110-2, т.е снова имеем два переноса, которые могут натворить бед. Только теперь, впридачу, у нас мнимая часть оказывается домножена на корень из двух. Т.е, число i может быть представлено только в виде бесконечной периодической дроби, равно как и 2i, 3i, и пр. Как-то это немного неприятно...
Вернёмся к основанию i-1, там Кнут заметил ещё одну подлянку! Ладно, что у нас очень "длинные" переносы, из 4-битных чисел у нас вдруг получается 9-битное. Но если пытаться делать переносы, пока они "сами собой" не затухнут, мы можем вообще попасть в бесконечный цикл! Причём далеко за примером ходить не надо: затруднения возникнут на простейшем выражении (-1)+1 ! Впрочем, с точки зрения реализации это не должно нас сильно пугать: зная, что практике имеем дело с конечными числами, мы сразу определяем необходимую разрядность результата, чтобы он заведомо поместился, и уже из старших разрядов перенос уходит "в никуда". Очевидно, с основанием -i-1 будет та же фигня.
С умножением всё куда проще, при условии, что сложение уже реализовано. Это у нас полноценные позиционные системы счисления, сдвиг на единицу влево эквивалентен умножению на основание системы счисления, в нашем случае i-1. Попробуем посчитать 2·2:
1100
* 1100
---------
1100
1100
---------
111010000
Это 9-битное число мы уже знаем, оно же получалось для 2+2. Это четвёрка!
Предварительный итог
Есть в этом всём определённая красота: с помощью всего двух цифр, 0 и 1, в одной-единственной битовой строке, мы записываем комплексные числа, не прибегая даже к дополнительному коду со всеми его заскоками!
Но да: из обычного представления довольно нетривиально прийти к этому, а потом и назад. Впрочем, из десятичной в двоичную и назад преобразовывать тоже не сахар, но как-то смирились, так что и здесь смириться можно было бы.
Плюс к тому, есть сложности с обработкой больших чисел. Если в обычной арифметике сложить два больших (больше размера слова, с которым оперирует АЛУ) числа не представляет труда, нужен лишь один бит переноса, то здесь одним битом переноса мы не обойдёмся, их прилично больше выйдет. Да и с небольшими числами тоже трудности, сумматор заметно сложнее обычного бинарного. Хотя не удивлюсь, если есть довольно красивые решения, возможно в несколько этапов.
А кватернионы?
Вот это было бы очень интересно! Всё-таки умножение комплексных чисел это ещё цветочки, а вот свести умножение кватернионов к самому простому умножению - уже повеселее.
Кажется, что можно пойти такой же дорожкой: основанием системы счисления выбрать какой-то хитрый кватернион, и затем "по аналогии" всё сойдётся. Я поначалу думал о чём-то вроде 1/2(1+i+j+k). Не вышло, тогда переключился на i+j+k, опять не то. Причём я был готов и на использование чуть большего количества цифр, чем просто 0 и 1. Например, для представления комплексных есть вполне разумное основание 2i, "мнимочетверичная система счисления". Чтобы она нормально заработала, нужно использовать цифры 0,1,2,3.
Увы, позиционная система счисления для кватернионов невозможна! По крайней мере, если мы под этим понимаем следующее выражение:
Причина очень проста: в кватернионе Λ мы можем выбрать определённое направление, его векторную/мнимую компоненту. При возведении в квадрат, векторная компонента останется коллинеарна исходной, поскольку векторное произведение равно нулю (вектор умножается на самого себя), и остаётся лишь умножение на скалярную компоненту, что не меняет направления.
Поэтому сколько разрядов мы бы не привели, мы в итоге начнём выражать лишь числа, расположенные в определённой плоскости, вложенной в четырёхмерное пространство кватернионов. В этой плоскости содержатся числа (1;0;0;0) и (0;nx, ny, nz). А мы-то надеялись всё четырёхмерное пространство потихонечку замостить своими числами...
В общем, очередную бредовую идею пока что отсекаем. На очереди ещё парочка, вроде проективной геометрической алгебры и дуальных кватернионов. Но пока не получается всю задачу целиком уместить в это "прокрустово ложе", всё равно, хочешь не хочешь - а надо к линейной алгебре переходить с матрицей 6×6 и вектором 6×1, и красивой записи для них я пока найти не могу, так, чтобы оно "естественным образом" было встроено в числовую систему. До поры до времени всё хорошо, а потом я это всё "ломаю через колено"...