Уравновешенная троичная система счисления
В СССР с информационными технологиями было не очень хорошо: то кибернетику объявят "продажной девкой империализма", то примутся бездумно копировать зарубежные разработки. Но все же был очень продуктивный период, где-то 60-70 годы, когда были предложены и выполнены "в железе" многие интересные идеи. Была шахматная программа "Каисса", выигравшая первый мировой турнир шахматных программ и очень элегантно проигравшая во втором, найдя у противника комбинацию, приводящую к неизбежному мату и которую можно избежать только отдав ферзя, что и было сделано. Любопытно, что ни сам противник (программа Duchess), ни присутствовавшие на турнире шахматисты этой комбинации не видели.
И примерно тогда же был собран и даже пущен в серию троичный компьютер Сетунь, который и сейчас поражает элегантностью технических решений. К сожалению, дальнейшего развития троичные компьютеры не получили, отчасти из-за уже упомянутой установки "копировать запад", отчасти из-за объективных трудностей реализации троичной системы на интегральных схемах (Сетунь работала на ферродиодных ячейках).
С уравновешенной троичной системой счисления у меня давнее знакомство, а этой весной мне удалось применить ее в своем алгоритме уравновешенного троичного быстрого преобразования Фурье, чрезвычайно удобного при расчете дифракции в оптических системах. Об этом напишу чуть позже (если повезет, то в ВАКовском журнале), а пока хочу рассказать, что же это за система счисления и чем она так хороша.
Казалось бы, чем меньше цифр - тем лучше. Двоичная система счисления - это основа, меньше уже нельзя. Иногда говорят об унарной системе счисления с одним символом, например. * - это 1, ** - 2, *** - 3, **** - 4. Думаю, идея ясна. Но такая система совершенно непрактична. Двоичная система - самая простая из позиционных, т.е из таких, где значение цифры зависит от ее положения. 1 - это и есть 1, 10 в двоичной системе - это 2, 100 - это 4, 1000 - 8 и т.д.
Опять же, можно провести аналогию с формальной логикой, если назвать ноль - "ложью", а единицу - "истиной". По этой причине простейшие элементы, на которых построена вся цифровая электроника, называют логическими: "И" (AND), "ИЛИ" (OR), "Исключающее или" (XOR), "НЕ" (NOT) и еще несколько. Скажем, в ТТЛ-схемотехнике главным кирпичиком был элемент "И-НЕ", NAND (Not-AND). Т.е "И" с инверсией. Любопытно, что имея только такие элементы (NAND), можно, по-разному соединяя их, получить все остальные.
Такая аналогия очень полезна, поскольку придает ясный смысл различным операциям над битами. Но некоторые математики считают, что двоичная логика изначально неполна. Одним из таких математиков был Чарльз Доджсон, более известный как Льюис Кэррол. Другим - Николай Брусенцов, создатель комьютера Сетунь. Основные претензии предъявляются к правилу импликации (логического следования), к той его части, где "из лжи следует истина". "Если 2+2=5, то я Папа Римский" - правильное утверждение с точки зрения формальной логики, как бы абсурдно оно ни звучало. Используя значения "Ложь", "Истина" и "Не имеет значения", можно получить более разумные правила логики.
Впрочем, мы ушли немного в сторону, речь-то шла о системе счисления, о способе представления чисел, удобном для выполнения арифметических операций. Здесь уместно вспомнить задачку про весы. Есть весы с друмя чашами, которые показывают - какая из чаш перевешивает. На левую чашу кладется взвешиваемое тело с весом от 0 до 31 грамма. Вопрос - какое минимальное количество разных грузиков надо взять, чтобы можно было взвесить его с точностью до грамма?
Двоичная система счисления подсказывает хорошее решение: взять грузики с массами 1,2,4,8 и 16 грамм и производить взвешивание так. Сначала ставим на правую чашу грузик 16г. Если взвешиваемое тело тяжелее, оставляем его, если легче - убираем. Теперь кладем 8г и поступаем также - или оставляем его, или убираем, если грузики перевесили. И так далее, до 1 грамма. Останется только посчитать суммарную массу грузиков на чаше - и мы получим ответ. Классический метод "деления пополам". Ровно так работают АЦП (аналогово-цифровые пребразователи) последовательного приближения, таким же способом часто ищут запись в отсортированном массиве. Кажется, что ничего лучше придумать нельзя.
Оказывается - можно! Ведь грузики можно ставить как на правую чашу весов, так и на левую, вместе со взвешиваемым телом. Тогда хватит всего 4 грузов вместо 5 - 1г, 3г, 9г, 27г. Чтобы уравновесить 1 грамм, достаточно положить грузик 1г на правую чашу. Чтобы уравновесить 2г, поставим 3г справа и 1г слева. 4 = 3 + 1. 5=9-3-1, 6=9-3 и.т.д. Это и есть уравновешенная троичная система счисления.
К двум цифрам - 0 и 1, мы добавляем третью - (-1) или для краткости 1. Младший разряд числа - это разряд единиц, следующий - разряд троек, за ним - разряд девяток и так далее. Запишем первые 10 чисел в такой системе:
0 = 1*0 = 0 в десятичной
1 = 1*1 =1,
11 = 1*3+(-1)*1 = 2,
10 = 1*3+0*1 = 3,
11 = 1*3+1*1 = 4,
111 = 1*9+(-1)*4+(-1)*1 = 5,
110 = 6,
111 = 7,
101 = 8,
100 = 9,
101 = 10.
Используя четыре разряда (те самые 4 грузика в задаче про весы), можно записать целые числа от -40 до 40.
Тут остановимся подробнее. Что значит -40 грамм? А очень просто. Например, мы решили измерить подъемную силу воздушного шарика и привязали его к чаше весов. Или захотели сравнить два тела по массе, для чего одно поставили в левую чашу, второе в правую, а точную разницу между ними стали измерять, уравновешивая их с помощью грузиков. Даже в задаче про весы отрицательный вес может иметь смысл. Имея возможность класть гирьки на обе чаши весов, мы получаем возможность взвешивать и положительные, и отрицательные веса. Иными словами, уравновешенная троичная система изначально предназначена для записи целых чисел, а не только натуральных.
Это принципиальный момент. Все системы счисления, с которыми мы привыкли работать, изначально были придуманы для представления положительных чисел и только! Чтобы ввести в рассмотрение отрицательные числа, нужно было дополнительно поставить знак числа перед его модулем. Мы к этому привыкли, но если поразмыслить, это не самый последовательный шаг. У нас появляется "плюс ноль" и "минус ноль", т.е две записи одного и того же числа - нуля. Для человека в этом нет ничего страшного - ясно же, ноль - он и в Африке ноль! Но если мы релизуем целые числа на компьютере, мы обязаны при сравнении чисел не просто сравнить их побитово, но и проверить, вдруг это две разные записи нуля? Да и сами по себе арифметические операции над числами со знаком становятся усложненными. Чтобы сложить два числа, надо посмотреть, совпадают ли их знаки. Если совпадают, то этот же знак мы ставим в ответ, а модули складываем. Если знаки разные, то мы ставим в ответ знак числа с бОльшим модулем, а модули вычитаем - из бОльшего меньшее. Это привычно для нас, но требует довольно сложной схемотехники в компьютере.
Ровно по этой причине для представления целых чисел при вычислениях на компьютере придумали более удобный формат - "дополнительный код". В нем старший бит числа берется с обратным знаком, а в остальном все то же самое. То есть, если число записывается с помощью 8 бит, то
01111111=0*(-128)+1*64+1*32+...+1*1=127, а
11111111=1*(-128)+1*64+...+1*1=-1.
10000000=-128 - самое большое отрицательное число. Но и здесь, разумеется, много подводных камней. При сложении чисел надо проверять, появился ли перенос в самый старший разряд - он тоже должен войти с обратным знаком. Следовательно, самый старший разряд должен обрабатываться совсем не так, как все остальные. Особая предосторожность нужна, если мы расширили 8-битное число до 16 бит. Нельзя просто добавить нули слева. Если число отрицательное, слева надо довавить единиц, иначе будет ошибка.
В уравновешенной системе счисления таких проблем нет. Вся "возня со знаками" органически входит в сами правила сложения двух тритов (это как биты, только троичные). Другой привлекательный факт - чтобы правильно округлить число, достаточно отсечь ненужные разряды - и все! Не нужно смотреть, какое там было значение, чтобы округлить вверх или вниз, или даже смотреть на последние 2 разряда - незачем.
Совсем нетрудно сменить знак числа - надо все 1 поменять на 1 и наоборот. Причем, можно быть уверенным, что такая замена допустима - количество положительных и отрицательных чисел совпадает, в отличие от уже упоминавшегося дополнительного кода, где 1 байт представляет числа от -128 до 127. Попытаешься изменить знак у -128 - получится переполнение.
Все это представлялось очень важным, пока компьютер проектировался вручную и был очень прожорливым устройством. Каждое усложнение грозило увеличением габаритов, стоимости и энергопотребления, снижением надежности. Да и попросту разрабатывать таких монстров было не самым приятным занятием. Сейчас, не знаю уж, к счастью или к сожалению, эти проблемы мало кого волнуют. АЛУ (арифметическое-логическое устройство) стало настолько маленькой частью процессора, что перекраивать всю электронику ради его упрощения никто не хочет. Поезд ушел, человечество выбрало двоичную логику.
И примерно тогда же был собран и даже пущен в серию троичный компьютер Сетунь, который и сейчас поражает элегантностью технических решений. К сожалению, дальнейшего развития троичные компьютеры не получили, отчасти из-за уже упомянутой установки "копировать запад", отчасти из-за объективных трудностей реализации троичной системы на интегральных схемах (Сетунь работала на ферродиодных ячейках).
С уравновешенной троичной системой счисления у меня давнее знакомство, а этой весной мне удалось применить ее в своем алгоритме уравновешенного троичного быстрого преобразования Фурье, чрезвычайно удобного при расчете дифракции в оптических системах. Об этом напишу чуть позже (если повезет, то в ВАКовском журнале), а пока хочу рассказать, что же это за система счисления и чем она так хороша.
Казалось бы, чем меньше цифр - тем лучше. Двоичная система счисления - это основа, меньше уже нельзя. Иногда говорят об унарной системе счисления с одним символом, например. * - это 1, ** - 2, *** - 3, **** - 4. Думаю, идея ясна. Но такая система совершенно непрактична. Двоичная система - самая простая из позиционных, т.е из таких, где значение цифры зависит от ее положения. 1 - это и есть 1, 10 в двоичной системе - это 2, 100 - это 4, 1000 - 8 и т.д.
Опять же, можно провести аналогию с формальной логикой, если назвать ноль - "ложью", а единицу - "истиной". По этой причине простейшие элементы, на которых построена вся цифровая электроника, называют логическими: "И" (AND), "ИЛИ" (OR), "Исключающее или" (XOR), "НЕ" (NOT) и еще несколько. Скажем, в ТТЛ-схемотехнике главным кирпичиком был элемент "И-НЕ", NAND (Not-AND). Т.е "И" с инверсией. Любопытно, что имея только такие элементы (NAND), можно, по-разному соединяя их, получить все остальные.
Такая аналогия очень полезна, поскольку придает ясный смысл различным операциям над битами. Но некоторые математики считают, что двоичная логика изначально неполна. Одним из таких математиков был Чарльз Доджсон, более известный как Льюис Кэррол. Другим - Николай Брусенцов, создатель комьютера Сетунь. Основные претензии предъявляются к правилу импликации (логического следования), к той его части, где "из лжи следует истина". "Если 2+2=5, то я Папа Римский" - правильное утверждение с точки зрения формальной логики, как бы абсурдно оно ни звучало. Используя значения "Ложь", "Истина" и "Не имеет значения", можно получить более разумные правила логики.
Впрочем, мы ушли немного в сторону, речь-то шла о системе счисления, о способе представления чисел, удобном для выполнения арифметических операций. Здесь уместно вспомнить задачку про весы. Есть весы с друмя чашами, которые показывают - какая из чаш перевешивает. На левую чашу кладется взвешиваемое тело с весом от 0 до 31 грамма. Вопрос - какое минимальное количество разных грузиков надо взять, чтобы можно было взвесить его с точностью до грамма?
Двоичная система счисления подсказывает хорошее решение: взять грузики с массами 1,2,4,8 и 16 грамм и производить взвешивание так. Сначала ставим на правую чашу грузик 16г. Если взвешиваемое тело тяжелее, оставляем его, если легче - убираем. Теперь кладем 8г и поступаем также - или оставляем его, или убираем, если грузики перевесили. И так далее, до 1 грамма. Останется только посчитать суммарную массу грузиков на чаше - и мы получим ответ. Классический метод "деления пополам". Ровно так работают АЦП (аналогово-цифровые пребразователи) последовательного приближения, таким же способом часто ищут запись в отсортированном массиве. Кажется, что ничего лучше придумать нельзя.
Оказывается - можно! Ведь грузики можно ставить как на правую чашу весов, так и на левую, вместе со взвешиваемым телом. Тогда хватит всего 4 грузов вместо 5 - 1г, 3г, 9г, 27г. Чтобы уравновесить 1 грамм, достаточно положить грузик 1г на правую чашу. Чтобы уравновесить 2г, поставим 3г справа и 1г слева. 4 = 3 + 1. 5=9-3-1, 6=9-3 и.т.д. Это и есть уравновешенная троичная система счисления.
К двум цифрам - 0 и 1, мы добавляем третью - (-1) или для краткости 1. Младший разряд числа - это разряд единиц, следующий - разряд троек, за ним - разряд девяток и так далее. Запишем первые 10 чисел в такой системе:
0 = 1*0 = 0 в десятичной
1 = 1*1 =1,
11 = 1*3+(-1)*1 = 2,
10 = 1*3+0*1 = 3,
11 = 1*3+1*1 = 4,
111 = 1*9+(-1)*4+(-1)*1 = 5,
110 = 6,
111 = 7,
101 = 8,
100 = 9,
101 = 10.
Используя четыре разряда (те самые 4 грузика в задаче про весы), можно записать целые числа от -40 до 40.
Тут остановимся подробнее. Что значит -40 грамм? А очень просто. Например, мы решили измерить подъемную силу воздушного шарика и привязали его к чаше весов. Или захотели сравнить два тела по массе, для чего одно поставили в левую чашу, второе в правую, а точную разницу между ними стали измерять, уравновешивая их с помощью грузиков. Даже в задаче про весы отрицательный вес может иметь смысл. Имея возможность класть гирьки на обе чаши весов, мы получаем возможность взвешивать и положительные, и отрицательные веса. Иными словами, уравновешенная троичная система изначально предназначена для записи целых чисел, а не только натуральных.
Это принципиальный момент. Все системы счисления, с которыми мы привыкли работать, изначально были придуманы для представления положительных чисел и только! Чтобы ввести в рассмотрение отрицательные числа, нужно было дополнительно поставить знак числа перед его модулем. Мы к этому привыкли, но если поразмыслить, это не самый последовательный шаг. У нас появляется "плюс ноль" и "минус ноль", т.е две записи одного и того же числа - нуля. Для человека в этом нет ничего страшного - ясно же, ноль - он и в Африке ноль! Но если мы релизуем целые числа на компьютере, мы обязаны при сравнении чисел не просто сравнить их побитово, но и проверить, вдруг это две разные записи нуля? Да и сами по себе арифметические операции над числами со знаком становятся усложненными. Чтобы сложить два числа, надо посмотреть, совпадают ли их знаки. Если совпадают, то этот же знак мы ставим в ответ, а модули складываем. Если знаки разные, то мы ставим в ответ знак числа с бОльшим модулем, а модули вычитаем - из бОльшего меньшее. Это привычно для нас, но требует довольно сложной схемотехники в компьютере.
Ровно по этой причине для представления целых чисел при вычислениях на компьютере придумали более удобный формат - "дополнительный код". В нем старший бит числа берется с обратным знаком, а в остальном все то же самое. То есть, если число записывается с помощью 8 бит, то
01111111=0*(-128)+1*64+1*32+...+1*1=127, а
11111111=1*(-128)+1*64+...+1*1=-1.
10000000=-128 - самое большое отрицательное число. Но и здесь, разумеется, много подводных камней. При сложении чисел надо проверять, появился ли перенос в самый старший разряд - он тоже должен войти с обратным знаком. Следовательно, самый старший разряд должен обрабатываться совсем не так, как все остальные. Особая предосторожность нужна, если мы расширили 8-битное число до 16 бит. Нельзя просто добавить нули слева. Если число отрицательное, слева надо довавить единиц, иначе будет ошибка.
В уравновешенной системе счисления таких проблем нет. Вся "возня со знаками" органически входит в сами правила сложения двух тритов (это как биты, только троичные). Другой привлекательный факт - чтобы правильно округлить число, достаточно отсечь ненужные разряды - и все! Не нужно смотреть, какое там было значение, чтобы округлить вверх или вниз, или даже смотреть на последние 2 разряда - незачем.
Совсем нетрудно сменить знак числа - надо все 1 поменять на 1 и наоборот. Причем, можно быть уверенным, что такая замена допустима - количество положительных и отрицательных чисел совпадает, в отличие от уже упоминавшегося дополнительного кода, где 1 байт представляет числа от -128 до 127. Попытаешься изменить знак у -128 - получится переполнение.
Все это представлялось очень важным, пока компьютер проектировался вручную и был очень прожорливым устройством. Каждое усложнение грозило увеличением габаритов, стоимости и энергопотребления, снижением надежности. Да и попросту разрабатывать таких монстров было не самым приятным занятием. Сейчас, не знаю уж, к счастью или к сожалению, эти проблемы мало кого волнуют. АЛУ (арифметическое-логическое устройство) стало настолько маленькой частью процессора, что перекраивать всю электронику ради его упрощения никто не хочет. Поезд ушел, человечество выбрало двоичную логику.