Фиеричная система счисления, или почему 1 + 10 = 100

«10.01 х 10.01 = 1000.1001»
Джордж Оруэлл. «1010001001001000.1001001000100001»

Существует ли позиционная система счисления с иррациональным основанием, в которой все натуральные числа записываются конечным числом цифр? В которой число больше единицы, не имеющее цифр после запятой, наверняка не целое и даже не рациональное? В которой 1 + 10 = 100, а 1 + 1 = 10.01?

Существует. Зовётся она системой Бергмана, или системой счисления с основанием Φ (читается как «фи», это буква греческого, а не русского алфавита). Число Φ, называемое также золотым числом или постоянной золотого сечения, имеет следующую формулу:

Далее по тексту я иногда буду называть её фиеричной (по аналогии с, допустим, восьмеричной) системой счисления, а иногда не буду.

Что это такое?

Фиеричная система счисления — это обычная позиционная система счисления с необычным основанием. Если в общеупотребительной десятичной системе счисления каждая цифра соответствует некоторой степени десятки (123 = 1∙10² + 2∙10¹ + 3∙10⁰), а в двоичной — некоторой степени двойки (101₂ = 1∙2² + 0∙2¹ + 1∙2⁰), то в системе Бергмана, в которой, как и в двоичной, есть только цифры 0 и 1, каждая единица символизирует некоторую степень числа Ф. Например:

Откуда есть пошла?

Как нетрудно догадаться исходя из названия, система Бергмана была придумана неким Бергманом. Возможно, у вас возник вопрос, что за харизматичный бородач изображён в начале статьи. Так вот, это Джордж Бергман, матеметик-алгебраист, профессор Калифорнийского университета в Беркли. Он родился в Бруклине в 1943 году, а четырнадцать лет спустя, когда у него ещё не было ни бороды, ни докторской степени, но уже имелось воображение и интерес к абстрактной алгебре, опубликовал статью ^[1] в Mathematics Magazine, в которой описал открытую им систему счисления (сам он называл её «тау-система»), её основные свойства и правила арифметических действий в ней. В своей статье он с достойной уважения скромностью признался, что «не видит никакого полезного применения для систем счисления, подобных этой, помимо развлечения и зарядки для ума». Время показало, однако, что в своей оценке он был не вполне прав. Однако о применении фиеричной системы счисления мы поговорим позднее.

Чем интересна?

Систем с иррациональным основанием, позволяющих записать любое натуральное число конечным количеством цифр, вообще говоря, бесконечно много. Например, система счисления с основанием, равным квадратному корню из двух. Если использовать лишь каждую вторую цифру (те, которые соответствуют чётным степеням основания), то ей можно пользоваться как обычной двоичной системой счисления:

Точно так же в качестве основания нам подойдут квадратный корень из трёх, кубический корень из двух… Ну, вы поняли мысль. Систем счисления, в которых почти все целые числа будут записываться бесконечной дробью, также немало. Скажу по секрету,

Строго говоря, этим свойством обладает любая система с трансцендентным основанием и достаточным набором цифр. В пи-ичной, е-ичной и даже в е-в-степени-пи ^[2]-ичной системе счисления все натуральные числа, превосходящие единицу, будут записываться в виде бесконечной дроби.

Система Бергмана отличается и от первой, и от второй группы. В ней любое натуральное число, большее единицы, имеет ненулевое, но конечное количество цифр после запятой. Например:

2 = 10.01_Ф
5 = 1000.1001_Ф
42 = 10100010.00100001_Ф
451 = 1010000001010.000100000101_Ф
1984 = (см. эпиграф)

Просторечно выражаясь, это немного рвёт шаблон. Мы привыкли, что понятия «знаки после запятой» и «дробная часть» очевидным образом взаимосвязаны. Однако в фиеричной системе дробная часть может равняться нулю, а количество цифр после запятой при этом — не равняться. Более того, можно доказать, что если количество цифр после запятой равняется нулю, то во всех случаях кроме нуля и единицы ненулевая дробная часть неиллюзорно присутствует.

Кроме целых чисел, конечным количеством знаков в фиеричной системе счисления записываются также числа из ℤ(Ф), то есть все числа вида:

Как, возможно, заметил внимательный читатель, ни в одной из фиеричных записей, приведённых выше, не было случая, когда две единицы идут подряд. Это не случайно. Как и в фибоначчиевой системе счисления ^[3], в системе Бергмана единица старшего разряда равняется сумме двух единицы помладше. Иначе говоря, 100_Ф = 11_Ф. Это обусловлено уникальным свойством золотого сечения: Ф² = Ф + 1. Поэтому каноничной записью числа в фиеричной системе считается та, где никакие две единицы не идут подряд.

Как в неё переводить?

Для натуральных чисел Бергман предлагал следующий алгоритм: если мы знаем запись числа n, то смотрим, что у неё за цифра в нулевой позиции, перед запятой. Если там нуль, записываем туда единицу и получаем n+1. если там уже единица, то мы денормализуем запись числа, применяя к этой единице правило 100 = 11. Если при этом одна из вновь образовавшихся единиц попадает на место, уже занятое другой единицей, предварительно преобразуем её, и так далее. Затем в денормализованной записи меняем нуль на единицу и нормализуем обратно. Например:

4 = 101.01_Ф = 101.0011_Ф = 100.1111_Ф
5 = 101.1111_Ф = 110.0111_Ф = 1000.0111_Ф = 1000.1001_Ф

Из доказательства корректности этого алгоритма (которое я оставляю на совесть читателя) следует, в частности, что любое натуральное число имеет конечное представление в фиеричной системе счисления. Я уже говорил об этом раньше, но теперь вы не обязаны верить мне на слово.

Этот алгоритм обладает достаточно грустной временной сложностью. Можно оптимизировать его следующим образом: вместо тупого прибавления единицы мы будем поочерёдно умножать на два и при необходимости прибавлять единицу (так, например, мы получаем значение числа из его двоичной записи). Однако умножение на два, оно же сложение числа с самим собой, в системе Бергмана — не вполне тривиальная операция, о чём мы поговорим чуть позже.

С другой стороны, мы можем за линейное время найти фиеричную запись числа тупо по определению. Этот алгоритм можно приблизительно описать следующим js-кодом:

const Phi = (Math.sqrt(5)+1)/2;

function toPhiBase(n){
    var power = 1;
    var result = "";

    while(power <= n){
        power *= Phi;
    }
    while(n > 0){
        console.log(power, result);
        if(power == 1){
            result += ".";
        }
        power /= Phi;
        if(power <= n){
            n -= power;
            result += 1;
        }else{
            result += 0;
        }
    }
    return result;
}

Увидев этот код, человек, знакомый с программированием, конечно, должен приуныть. В голове его должны пронестись мысли о числах с плавающей точкой, потере точности, тщетности бытия… И действительно, приведённая функция будет работать некорректно для хоть капельку большого числа, вроде того же 1984. Реализация подкачала, но это не значит, что плоха сама идея.

Если мы работаем с числами с плавающей точкой, потеря точности практически неизбежно. Но можно не работать с такими числами. Можно вести все операции в поле ℚ(√5) (то есть в поле, состоящем из чисел вида a + b√5, a, b ∈ ℚ). Действия над такими числами можно реализовать, используя только операции над рациональными числами. А операции над рациональными числами можно реализовать, используя только сложение, вычитание и умножение целых чисел, которые к потере точности не приводят. Короче говоря, можно написать свою маленькую символьную арифметику ^[4]. А я всегда хотел её написать.

Как только я понял, насколько страдают обитатели интернета без возможности переводить числа в систему Бергмана и обратно, я немедленно наваял npm-модуль ^[5], основанный на вышеописанном подходе. Теперь каждый может самостоятельно проверить, не ошибся ли я в фиеричной записи числа 42, введя в консоль что-то типа:

npm install phibase
node
var PhiBase = require("phibase")
Phibase.toPhiBase(42)

Те, у кого по каким-то неясным причинам не установлены node и npm, могут воспользоваться онлайн-конвертером ^[6]

Кстати о переводе обратно. Тут опять же есть несколько подходов. Можно в стиле Бергмана вынимать из числа по единичке, при необходимости денормализуя его запись. Можно посчитать по определению в числах с плавающей точкой, смирившись с потерей точности (алгоритм приводить не буду, он вполне очевиден). Или, имея дело с рациональными числами, можно опять же воспользоваться «символьными» вычислениями — в моём модуле, как вы могли догадаться, используется именно этот способ.

Как в ней работать?

Краткий ответ: с трудом.

В системе Бергмана не работают классические алгоритмы сложения и вычитания. Как мы помним, 1_Ф + 1_Ф = 10.01_Ф. Это означает, что при попытке сложения «в столбик» возникающие переносы будут идти как влево, так и вправо. Это лишает нас надежды просто взять числа с какого-то конца и складывать, перенося излишки в другой конец. Один из подходов к сложению в фиеричной системе состоит в том, что для начала мы складываем числа просто как векторы цифр (10.01 + 101.01 = 111.02), а затем как-то нормализуем запись. Оригинальный (в смысле, изначальный) подход, предложенный Бергманом, состоял в следующем: выписав числа одно над другим, денормализуем их таким образом, чтобы в одном и том же разряде не находились две единицы. После этого сложим их поразрядно (сложение нуля с единицы или нуля с нулём уже не представляет трудности для тренированного математика), затем нормализуем сумму.

Этот подход показался мне настолько забавным, что я написал небольшую игру ^[7], которая позволяет игроку ощутить всю прелесть этого подхода лично.

Умножение и деление, впрочем, реализуются более или менее стандартным образом — умножаем в столбик, делим уголком.

И на кой она нужна?

По-хорошему, этот раздел должен писать не я, а какой-нибудь суровый инженер советской закалки. Насколько мне известно, система Бергмана использовалась в некоторых избыточность ^[9] для большей помехоустойчивости, однако «железная» реализация такого преобразователя оказалась склонна к ошибкам, и идею отправили в ящик. Я бы с удовольствием рассказал больше, но не могу, и честно признаюсь в своей некомпетентности. Надеюсь, кто-то из читателей знает больше — в таком случае я с удовольствием размещу здесь ссылку на его содержательный комментарий.

Ах да, чуть не забыл. Ещё фиеричную систему счисления можно использовать для перемножения целых чисел. Делается это следующим образом:

1. Одно из чисел переводится в фиеричную систему счисления и записывается куда-нибудь, желательно на клетчатую бумагу.
2. Другое выписывается в клетку под нулевым разрядом первого числа.
3. Слева от второго числа пишем произвольное третье число — вообще любое.
4. Ряд из второго и третьего числа продолжаем влево и вправо таким образом, чтобы каждое число в ряду равнялось сумме двух чисел справа от него. Получается нечто вроде ряда Фибоначчи, только построенного на других начальных числах и направленного справа налево.
5. Просуммируем все числа в этом ряду, над которыми написаны единицы. Эта сумма и будет искомым произведением

Шаг 1.

1 |0 |1.|0 |1 
--+--+--+--+--
  |  |  |  | 

Шаг 2.

1 |0 |1.|0 |1 
--+--+--+--+--
  |  |9 |  | 

Шаг 3.

1 |0 |1.|0 |1 
--+--+--+--+--
  |13|9 |  |
 
Шаг 4.

1 |0 |1.|0 |1 
--+--+--+--+--
22|13|9 |4 |5

Шаг 5.

22 + 9 + 5 = 36

Если у вас плохо с умножением, но вы умеете быстро переводить числа в фиеричную систему счисления и строить фибоначчиобразные ряды, этот метод определённо для вас. Доказательство же его корректности основано на том, что при денормализации записи вверху сумма чисел под её единицами не изменится.

И это всё?

Есть ещё несколько вещей, которые я бы хотел сказать напоследок. Во-первых, если вы как следует помучили мой онлайн-конвертер ^[6], то могли заметить, что дробные числа в фиеричной системе счисления, как и в любой другой позиционной, записываются в виде периодической дроби. Доказательство этого факта основывается на делении уголком и опять же не отличается от доказательства, проведённого в системе счисления здорового человека.

Во-вторых, я вам наврал, когда говорил об «уникальном свойстве золотого сечения». Оно, конечно, уникально, но не совсем. Уравнение x² = x + 1 имеет ещё одно решение, равное

В системе с основанием φ (назовём её антифиеричной) сохраняются все свойства фиеричной системы, которые выводятся из тождества 100_Ф = 11_Ф. В частности, в ней имеют конечную запись все целые числа (причём ту же самую, что и в фиеричной системе). Это особенно забавно, потому что новое основание не только иррационально, но ещё и отрицательно и по модулю меньше единицы. Можно доказать даже следующую теорему: если число имеет одну и ту же конечную запись в фиеричной и антифиеричной системе счисления, то оно целое.

И наконец, в фиеричной системе счисления формулу числа Ф можно переписать следующим образом:

Это забавно, потому что приведённая формула, если рассматривать её как уравнение, имеет единственное действительное решение. То есть её в самом деле можно использовать как определение числа Ф.

Вдумайтесь в это.

Автор: Sirion

Источник ^[10]