Материалы к докладу
Классификация систем счисления
на 7-ой Международной конференции памяти П.Л.Чебышева
(Санкт-Петербург, СПбГУ, февраль 2002г.,
докладчик - Федотова М.В. ,
научный руководитель - Федотов В.П.)
Текст цитируемого доклада
ИТЕРАЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
(докладчик - Баранова Н. В.,
научный руководитель - Федотов В. П.,
6-я Международная конференция молодых учёных, посвященная памяти
С.Н.Бернштейна. Санкт-Петербург, СПбГУ, февраль 2000 года)
Для вычислительной техники и проблем передачи числовой информации важны такие
способы представления чисел, в которых наиболее важную информацию о числе содержат
первые символы его записи. Это нужно для того, чтобы экономить ресурсы и терять
меньше информации при округлении чисел или при обрыве сеанса связи. Основные
позиционные системы счисления не удовлетворяют этому требованию, так как в традиционной
записи более существенную информацию о величине числа несут не цифры, а их количество
в целой части числа ( порядок ). Одним из путей решения названной проблемы являются
башенные системы счисления, построенные два года тому назад моим научным руководителем
В.П.Федотовым [1].
Мой доклад посвящен построению новых систем счисления, также полезных в этом контексте,
и их сравнению с башенными.
Обозначим через M множество функций y=f(x) со следующими свойствами :
1) областью определения f(x) является вся числовая ось,
т.е. f(x) существует (имеет смысл) для любого x ,
2) f(x) строго монотонно возрастает, т.е. для любых p и q из p<q следует f(p)<f(q) ,
3) областью значений f(x) является полупрямая x>0 , т.е. ( с учетом монотонности )
существуют два предела: f(x) является бесконечно малой при бесконечно больших отрицательных x и
бесконечно большой при бесконечно больших положительных x .
Через N обозначим подмножество функций из M с дополнительным свойством нормировки :
4) f(0)=1 .
Примерами функций из множества N являются показательные функции
y=dx с d>1 .
Другими примерами служат функции, графики которых – соответствующим образом повернутые
ветви гипербол.
Обозначим через K и L множества функций g(x) , обратных функциям из M и N соответственно.
Эти функции также обладают свойством 2) и, кроме того, свойствами :
5) областью определения g(x) является полупрямая x>0 ,
6) областью значений g(x) является вся числовая ось, т.е. (с учетом монотонности)
существуют два предела: g(x) является отрицательной бесконечно большой при бесконечно малых x и
положительной бесконечно большой при бесконечно больших x .
7) g(1)=0 ( только для g(x)€L ).
Примерами функций из множества L являются логарифмические функции
y=logdx с d>1 . Другими примерами служат функции,
графики которых – соответствующим образом повернутые ветви гипербол,
например, y=x–1/x (для x>0 ).
Наконец, удобно рассмотреть множества G и H , состоящие из четных функций,
определенных при всех x¹0 ,
сужения которых на полуось x>0 являются функциями
из K и L соответственно.
Зафиксируем теперь функцию f(x)€M и соответствующую ей g(x)€G .
Для записи произвольного вещественного числа в итерационной системе счисления,
связанной с этими функциями, будут использоваться всего три символа : N , O
и P , средний из которых играет роль нуля, а крайние – отрицательной ( Negative )
и положительной ( Positive ) единиц.
Выберем теперь произвольное вещественное число x . Если x=0 , то вся его запись
в итерационной системе счисления, как и в любой позиционной, ограничится одной цифрой O .
Прежде, чем получить запись ненулевого числа в итерационной системе счисления,
составим вспомогательную последовательность знаков.
Начнем эту цепочку со знака самого числа ( плюс для x<0 и минус – для x>0 ).
Тем самым, как и в традиционной записи, первый символ имеет смысл знака числа.
Второй знак – знак g(x) . Если g(x)€H , то он имеет смысл знака порядка числа в
любой основной позиционной системе счисления.
И все последующие знаки выбираются по тому же самому закону : третий – знак g(g(x)) ,
четвертый – знак g(g(g(x))) и т.д.
Ясно, что нумерацию разрядов удобнее начать не с единицы ( как это было сделано в
предыдущих абзацах ), а с нуля. Кроме того, разряды нумеруются в прямом направлении
( слева направо, а не задом наперед от десятичной точки, как это принято в основных
позиционных системах счисления ). При такой нумерации разрядов k-ый знак совпадает со
знаком k-ой итерации функции g(x) .
Множество H было выбрано как раз таким образом, чтобы итерации имели смысл всегда,
за исключением единственного случая, когда очередная итерация функции g(x) обратится в ноль.
Тем самым для последовательности знаков возможны два исхода : либо она конечна и завершается
нулем, либо ноль в ней никогда не появится, а сама последовательность потенциально бесконечна.
Весьма серьезным неудобством представления числа в виде такой цепочки знаков является
нарушение обычного порядка следования на числовой оси. Чтобы восстановить его, модифицируем
знаки аналогично тому, как это сделал В.П.Федотов
при построении башенных систем счисления.
Вместо плюса и минуса с этой целью используются латинские буквы P и N соответственно, причем
буква выбирается в зависимости не только от самого знака, но и от четности числа предшествующих
ему минусов. Это и будет запись в итерационной системе счисления.
Так как выбранные для модификации знаков латинские буквы непосредственно следуют друг
за другом в латинском алфавите, то представления чисел в итерационной системе счисления
можно рассматривать как слова, составленные из этих трех букв, и сравнивать положение слов
друг относительно друга в принятом в словарях лексикографическом порядке. При этом окажется,
что чем меньше x , тем раньше соответствующее слово стоит в словаре.
Заметим, что башенные системы счисления являются частным случаем итерационных с
g(x)=logdx .
Чтобы не путать число x с его итерационным представлением, обозначим последнее через I(x) .
Найдем его в простейших случаях. Прежде всего, всегда I(0)=0 . Если g(x)€H ,
то I(1)=PO и I(–1)=NO .
Заменим теперь в итерационном представлении I(x) произвольного вещественного числа x
все вхождения буквы N на цифру 0, а букв P и O – на цифру 1, поставив в начале записи
двоичную точку, а перед ней – 0 в целой части. Полученное число обозначим через P(x) и
рассмотрим как функцию от x . Эта функция всюду монотонно возрастает и заключена между 0 и 1 .
Поэтому ее можно интерпретировать как вероятностное распределение. Так как P(0)=1/2 , то
этот факт ( в полном соответствии со «здравым смыслом» ) означает, что произвольное
вещественное число x с вероятностью 50% отрицательно и с той же вероятностью положительно.
Далее, если g(x)€H , то P(1)=3/4 и P(–1)=1/4. Наконец,
P(x)-->1 при положительных бесконечно больших x , и
P(x)-->0 при отрицательных бесконечно больших x.
В.П.Федотов предпочитает вместо P(x) рассматривать другую функцию
F(x)=4P(x)–2 . Она более удобна для исследования, так как четна, монотонна, а уравнение
F(x)=x в случае g(x)€H имеет не менее трех корней : x=–1 , 0 и 1.
Мною были проведены вычисления значений названных выше представлений и функций
для некоторых различных функций g(x)€H . В тех случаях, когда не удавалось найти точное
значение, приближенные вычисления проводились на микрокалькуляторе Casio, либо на
компьютере с использованием электронных таблиц Excel-97.
Литература