Сайт Марии Федотовой, ученицы ФМЛ №239 СПб

Материалы к докладу

Классификация систем счисления

на 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.

Литература

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

Сайт управляется системой uCoz