Санкт-Петербург, Санкт-Петербургский институт (филиал) Московского государственного университета печати
БАШЕННЫЕ
СИСТЕМЫ СЧИСЛЕНИЯ
(В
сб. «Информационные технологии в образовании. К 80-летию РГПУ им. Герцена».
СПб, 1998)
Сегодня процессоры всех компьютеров основаны на двоичной системе счисления. Однако среди первых вычислительных машин была и московская «Сетунь», арифметическое устройство которой базировалось на троичном представлении чисел. В нынешней рыночной ситуации, когда поколения процессоров сменяют друг друга в считанные месяцы, любая альтернатива хорошо налаженному производству абсолютно неконкурентноспособна. Однако в более далекой перспективе просматривается и возможность перехода на троичную систему счисления, так как она позволяет более эффективно сворачивать числовую информацию ( как показал Джон фон Нейман, это следует из того, что число 3 ближе, чем 2, к основанию e натуральных логарифмов ).
Оказывается, если рассматривать более сложные ( по сравнению с основными ) типы систем счисления, то удается построить еще более эффективное представление. Его описанию и посвящен настоящий доклад.
Вслед за общеизвестными действиями над числами – сложением, умножением и возведением в степень, каждое из которых является итерацией предыдущего, четвертый член этой последовательности бинарных операций получил название башни. В отличие от традиционно рассматриваемых башен, в которых все показатели степени равны друг другу и положительны, в настоящем докладе вводятся башни со знакопеременными ( но равными по абсолютной величине ) показателями.
Оказывается, что, если зафиксировать такой показатель и произвольно выбирать последовательность знаков, то каждое вещественное число однозначно представляется в виде соответствующей башни ( конечной – заканчивающейся нулем, либо бесконечной ). Тем самым возникает совершенно новый тип систем счисления : показатель башни играет роль основания системы счисления, а знаки – цифр.
Алгоритм представления числа в башенной системе счисления весьма прост. Первый знак – это знак самого числа. Затем, на каждом последующем шаге, если число не равно нулю, то его нужно заменить логарифмом ( по фиксированному основанию - основанию башни, обозначим его d ) от абсолютной величины числа. Очередной знак – знак этого логарифма. Алгоритм обратного преобразования также не сложен и сводится к серии операций возведения в степень.
Этому процессу можно придать следующий смысл. С точки зрения «здравого смысла» вещественное число с вероятностью 50% положительно, либо отрицательно. Поэтому информация о знаке числа составляет в точности 1 бит. Следующий бит – информация о знаке логарифма от абсолютной величины числа и т.д. Таким образом, знаки на каждом шаге несут этот «информационный» смысл.
Оказывается, что лучше фиксировать не сами знаки, а несколько их модифицировать. Чтобы не возникло путаницы, для модифицированных знаков используем другие обозначения – латинские буквы P и N ( от слов positive и negative соответственно ). Кроме того, введем третий знак – букву O ( для фиксации особого случая, когда на каком-либо шаге процесс закончится появлением нуля, логарифмировать который уже невозможно ; ясно, что этот знак может появиться только в самом конце записи ).
Модификация происходит следующим образом. В качестве первого знака башенного представления числа x используем P , если это число положительно, и N, если оно отрицательно. Если же x=0 , то его башенное представление сводится к O . Начиная со следующего шага, учитываем четность числа минусов, уже замененных буквами. Каждый новый минус инвертирует все последующие знаки. Таким образом, если еще не было минусов, замененных буквами, либо их число четно, то буквы, как и на первом шаге, выбираются в соответствии с их смыслом. Если же число использованных минусов нечетно, то выбираются противоположные соответствующим знакам буквы.
Целью такой модификации является достижение монотонности соответствия между точками числовой прямой и их башенными представлениями. Выбранные для модификации знаков латинские буквы непосредственно следуют друг за другом в латинском алфавите. Башенные представления чисел можно рассматривать как слова, составленные из этих трех букв, и сравнивать положение слов друг относительно друга в принятом в словарях лексикографическом порядке. Оказывается, что чем меньше x , тем раньше соответствующее слово стоит в словаре.
Обозначим башенное представление числа x через B(x) и найдем его в простейших случаях. Ясно, что всегда ( при любом d ) справедливы равенства B(0)=O , B(1)=PO и B(-1)=NO .
Далее, для примера рассмотрим случай d=2 . Имеем B(2)=PPO , B(-2)=NNO , B(1/2)=PNO , B(-1/2)=NPO , B(4)=PPPO , B(-4)=NNNO , B(1/4)=PNNO , B(-1/4)=NPPO , B(16)=PPPPO , B(65536)=PPPPPO и т.д.
Последующие вычисления показывают, что, с одной стороны, точными башенными числами ( заканчивающимися знаком O ) могут быть как дроби, так и иррациональные числа, а, с другой стороны, некоторые целые числа ( например x=3 при d=2 ) не являются точными башенными числами. Более того, в случае любого целого основания башни, целые числа крайне редко будут представляться конечной цепочкой знаков. Поэтому башенные системы счисления никак не предназначены для представления целых чисел, а для теоретических исследований наиболее важным является случай d=e .
Зато, в сравнении с основными позиционными системами счисления, башенные позволяют гораздо более эффективно сворачивать информацию о вещественном числе. Выше уже сказано, что каждый бит можно естественным образом интерпретировать как выбор одной из двух равновероятных возможностей для знака числа или очередного логарифма. Кроме того, нет необходимости разбивать запись вещественного числа на две части ( мантиссу и порядок ). Наконец, снимаются ограничения на представление как очень больших, так и очень малых по абсолютной величине чисел. Поэтому создание микропроцессоров, основанных на представлении вещественных чисел в башенных системах счисления, может резко повысить производительность компьютеров в их наиболее слабом сегодня месте – операциях «с плавающей точкой».
Разумеется, арифметические действия с башенным представлением чисел более трудоемки, чем традиционные. Однако это препятствие нужно будет преодолеть только один раз – на этапе проектирования и создания микропроцессоров, базирующихся на таких вычислениях. Сами же вычисления будут проходить в быстрых регистрах, чего пользователь просто не заметит. В качестве аналогии здесь вполне уместен пример с логарифмической линейкой : достаточно было один раз научиться ее градуировать, чтобы затем на протяжении нескольких столетий она оставалась одним их наиболее удобных вычислительных устройств.
Определенным неудобством предложенной формы записи являются возникающие трудности с ее графическим представлением. Чтобы получить возможность строить графики, можно рассмотреть функцию распределения P(x), отвечающую описанной выше «вероятностной интерпретации». Центрирование и перенормировка F(x)=4P(x)-2 дают более удобную для исследования функцию : она четна, монотонна, а уравнение F(x)=x при d=2 имеет 7 корней : x=-1 , -1/2 , -1/4 , 0 , 1/4 , 1/2 , 1 .
Детальное изучение свойств функции F(x) и позволит решить все технические проблемы, поставленные в этом докладе.