«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 году, а четырнадцать лет спустя, когда у него ещё не было ни бороды, ни докторской степени, но уже имелось воображение и интерес к абстрактной алгебре, опубликовал статью в Mathematics Magazine, в которой описал открытую им систему счисления (сам он называл её «тау-система»), её основные свойства и правила арифметических действий в ней. В своей статье он с достойной уважения скромностью признался, что «не видит никакого полезного применения для систем счисления, подобных этой, помимо развлечения и зарядки для ума». Время показало, однако, что в своей оценке он был не вполне прав. Однако о применении фиеричной системы счисления мы поговорим позднее.

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

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



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

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

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

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

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



Как, возможно, заметил внимательный читатель, ни в одной из фиеричных записей, приведённых выше, не было случая, когда две единицы идут подряд. Это не случайно. Как и в фибоначчиевой системе счисления, в системе Бергмана единица старшего разряда равняется сумме двух единицы помладше. Иначе говоря, 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){
        if(power == 1){
            result += ".";
        }
        power /= Phi;
        if(power <= n){
            n -= power;
            result += 1;
        }else{
            result += 0;
        }
    }
    return result;
}

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

Если мы работаем с числами с плавающей точкой, потеря точности практически неизбежна. Но можно не работать с такими числами. Можно вести все операции в поле ?(v5) (то есть в поле, состоящем из чисел вида a + bv5, a, b ? ?). Действия над такими числами можно реализовать, используя только операции над рациональными числами. А операции над рациональными числами можно реализовать, используя только сложение, вычитание и умножение целых чисел, которые к потере точности не приводят. Короче говоря, можно написать свою маленькую символьную арифметику. А я всегда хотел её написать.

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

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

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

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

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

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

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

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

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

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

janatem подсказывает в своих комментариях, что если добавить в систему Бергмана специальную цифру "-1", то получившаяся в результате симметричная система счисления будет обладать очень полезным свойством: возможностью параллельного поразрядного сложения. Иначе говоря, в ней можно получить некоторую цифру суммы чисел, не вычисляя для этого предыдущие. В десятичной системе счисления такое невозможно: чтобы наверняка знать, с какой цифры будет начинаться сумма 999995 + x (x — цифра), нам обязательно нужно знать значение x, несмотря на то, что эта цифра находится за пять разрядов от той, которая нас действительно интересует. Такую независимость разрядов можно использовать для радикального ускорения вычислений на определённых архитектурах.

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

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

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

И это всё?

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

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


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

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



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

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