Баранова Н.В.

ИТЕРАЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

(Доклад на 6-ой Международной конференции молодых ученых, посвященной памяти С.Н.Бернштейна.

Санкт-Петербург, СПбГУ, февраль 2000 года)

 

Для вычислительной техники и проблем передачи числовой информации важны такие способы представления чисел, в которых наиболее важную информацию о числе содержат первые символы его записи.  Это нужно для того, чтобы экономить ресурсы и терять меньше информации при округлении чисел или при обрыве сеанса связи. Основные позиционные системы счисления не удовлетворяют этому требованию, так как в традиционной записи более существенную информацию о величине числа несут не цифры, а их количество в целой части числа ( порядок ). Одним из путей решения названной проблемы являются башенные системы счисления, построенные два года тому назад моим научным руководителем  В.П.Федотовым [1].

Мой доклад посвящен построению новых систем счисления, также полезных в этом контексте,  и их сравнению с башенными.

Обозначим через M множество функций  y=f(x)  со следующими свойствами :

1)       областью определения f(x) является вся числовая ось, т.е. f(x) существует  ( имеет смысл )  для любого x ,

2)       f(x)  строго монотонно возрастает, т.е. для любых x₁ и x₂ из  x₁<x₂  следует   f(x₁)<f(x₂) ,

3)       областью значений  f(x)  является полупрямая  x>0 , т.е. ( с учетом монотонности )  существуют два предела :           f(x)®0   при  x® –µ       и      f(x)® +µ     при  x® +µ  .

Через  N  обозначим подмножество функций из  M  с дополнительным свойством нормировки :

4)        f(0)=1 .

Примерами функций из множества  N  являются показательные функции  y=d^x   с  d>1  .  Другими примерами служат функции, графики которых – соответствующим образом повернутые ветви гипербол, например,             y=x+.

Обозначим через  K и L множества функций  g(x) , обратных функциям из M и N соответственно.  Эти функции также обладают свойством  2)  и, кроме того, свойствами :

5)       областью определения  g(x)  является полупрямая  x>0 ,

6)       областью значений  g(x)  является вся числовая ось, т.е. ( с учетом монотонности )  существуют два предела :  g(x)® –µ при  x® 0   и   g(x)® +µ     при  x® +µ  ,

7)       g(1)=0             ( только для   g(x)L  ).

Примерами функций из множества L являются логарифмические функции  y=log_d x   с  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)=log_d x   .

Чтобы не путать число 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, либо на компьютере с использованием электронных таблиц Excel97.

 

Литература

1.  Федотов В.П.  Башенные системы счисления. – В сб. «Информационные технологии в образовании. К 80-летию РГПУ им. Герцена». СПб, 1998.