НОВЫЕ СИСТЕМЫ СЧИСЛЕНИЯ КАК АЛЬТЕРНАТИВА ИНТЕРВАЛЬНЫМ ВЫЧИСЛЕНИЯМ
В.П.Федотов
Северо-Западный
институт печати
В числе атрибутов того или иного этапа развития человеческой цивилизации можно указать на диапазон чисел, востребованных этой исторической эпохой. Соответственно развиваются языковые средства (прежде всего, количественные числительные) и способы записи чисел – системы счисления.
До наших дней остались в употреблении римские цифры. Анализ возможностей представления чисел с их помощью явно указывает на то, что древним римлянам практически не приходилось иметь дело с числами, значительно превышавшими 1000.
К концу XX века этот диапазон достиг 1099. С одной стороны, именно таков предел для представления чисел в компьютерах и микрокалькуляторах (если не прибегать к специальным ухищрениям). С другой, лишь «чуть-чуть меньше» (около 1082) оценка для числа элементарных частиц во вселенной. Поэтому естественные науки никогда не потребуют чисел вне этого диапазона, а ни «традиционная» техника, ни экономика к его границе пока даже и не приближаются.
Но, между тем, рубеж тысячелетий стал рубежом исторических эпох. Наступившее время характеризуется, в первую очередь, тотальным внедрением компьютерной техники во все сферы человеческой жизни.
Соответственно возникает потребность и в резком расширении диапазона чисел. Ее стимулируют теоретические исследования в области информатики, криптографии и ряда смежных дисциплин, а также борьба с катастрофической потерей точности, часто возникающей в процессе вычислений. Встал вопрос и о новых системах счисления.
Основатель теории информации Джон фон Нейман доказал теорему о том, что среди всех основных позиционных систем счисления именно троичная система счисления позволяет наиболее эффективно сворачивать информацию о вещественном числе. Этот факт базируется на том, что среди целых чисел именно 3 ближе всех к основанию натуральных логарифмов e»2.718. Однако названный эффект можно усилить, если вместо традиционных систем счисления использовать более сложные конструкции башенных [5], итерационных [1] и интервальных [6] систем, построенные автором этого доклада и моими учениками.
В отличие от традиционных, только что упомянутые системы счисления базируются на информационном принципе: каждый очередной бит последовательно уточняет информацию о месте числа на числовой оси [7]. Это становится важным, например, при параллельных вычислениях: первые цифры числа можно передавать очередному этапу алгоритма еще задолго до того, как найдены последующие цифры. При традиционной же записи числа первые цифры вообще не несут никакой информации о величине числа до тех пор, пока неизвестен его порядок. Однако все последующие цифры вполне соответствуют этому требованию.
Первый бит информации о числе, чаще всего, совпадает с его знаком. Он служит ответом на вопрос о сравнении числа с нулем. В качестве второго бита разумно взять знак порядка (то есть, знак логарифма, причем совершенно безразлично, идет ли речь о натуральных, десятичных, двоичных логарифмах, либо по другому основанию, большему 1). Этот бит служит ответом на вопрос о сравнении положительного числа с 1 или отрицательного числа с –1.
Ясно, что и в качестве последующих битов записи числа можно брать ответ на вопрос о сравнении данного числа с числами из некоторой последовательности. Проблема лишь в том, как задать саму эту последовательность. При этом алгоритм формирования последовательности следует выбрать заранее, хотя конкретные ее члены будут строиться в зависимости от числа.
Чтобы таким способом получить какую-либо итерационную систему счисления [1], в качестве чисел для сравнения надо взять корни последовательных итераций нужной монотонной функции. В частности, если эта функция – логарифм, основание которого не меньше e1/e»1.44 , то получится башенная система счисления [5].
Именно башенные системы счисления позволяют убить сразу двух зайцев. Во-первых, они лучше всего усиливают эффект названной теоремы Джона фон Неймана. Во-вторых, сравнительно небольшим количеством цифр они позволяют записать числа, абсолютная величина которых пока еще не доступна не только словесной формулировке, но даже и весьма богатому воображению.
Несколько примеров систем счисления, реализующих описанную конструкцию (в том числе, золотая система счисления [3] и уравновешенная троичная информационная система счисления [4]), были построены в самые последние годы.
Еще одна новая возможность – задание одной последовательностью цифр не числа, а пары чисел, то есть интервала на числовой прямой. Следует особо подчеркнуть, что речь здесь идет о произвольных интервалах, а не только о тех, границами которых служат узловые точки системы счисления.
Тем самым появляется новый язык для мягких вычислений и, в особенности, для интервального анализа [2]. Это направление вычислительной математики, соединившее классическую технику приближенных вычислений с идеями Л.А.Заде [8] и его последователей, получило особенно бурное развитие в последней четверти XX века.
Конечно, результативное использование новых систем счисления требует разработки алгоритмов выполнения базовых операций и вычисления функций от чисел, заданных в таком виде. Решение этой задачи потребует немного лет. В самом крайнем случае, цель будет достигнута путем создания таблиц.