Фиеричная система счисления, или почему 1 + 10 = 100
»10.01×10.01 = 1000.1001»
Джордж Оруэлл.»1010001001001000.1001001000100001»
Существует ли позиционная система счисления с иррациональным основанием, в которой все натуральные числа записываются конечным числом цифр? В которой число больше единицы, не имеющее цифр после запятой, наверняка не целое и даже не рациональное? В которой 1 + 10 = 100, а 1 + 1 = 10.01?
Существует. Зовётся она системой Бергмана, или системой счисления с основанием Φ (читается как «фи», это буква греческого, а не русского алфавита). Число Φ, называемое также золотым числом или постоянной золотого сечения, имеет следующую формулу:
Далее по тексту я иногда буду называть её фиеричной (по аналогии с, допустим, восьмеричной) системой счисления, а иногда не буду.
Что это такое?
Фиеричная система счисления — это обычная позиционная система счисления с необычным основанием. Если в общеупотребительной десятичной системе счисления каждая цифра соответствует некоторой степени десятки (123 = 1∙102 + 2∙101 + 3∙100), а в двоичной — некоторой степени двойки (1012 = 1∙22 + 0∙21 + 1∙20), то в системе Бергмана, в которой, как и в двоичной, есть только цифры 0 и 1, каждая единица символизирует некоторую степень числа Ф. Например:
Откуда есть пошла?
Как нетрудно догадаться исходя из названия, система Бергмана была придумана неким Бергманом. Возможно, у вас возник вопрос, что за харизматичный бородач изображён в начале статьи. Так вот, это Джордж Бергман, матеметик-алгебраист, профессор Калифорнийского университета в Беркли. Он родился в Бруклине в 1943 году, а четырнадцать лет спустя, когда у него ещё не было ни бороды, ни докторской степени, но уже имелось воображение и интерес к абстрактной алгебре, опубликовал статью в Mathematics Magazine, в которой описал открытую им систему счисления (сам он называл её «тау-система»), её основные свойства и правила арифметических действий в ней. В своей статье он с достойной уважения скромностью признался, что «не видит никакого полезного применения для систем счисления, подобных этой, помимо развлечения и зарядки для ума». Время показало, однако, что в своей оценке он был не вполне прав. Однако о применении фиеричной системы счисления мы поговорим позднее.
Чем интересна?
Систем с иррациональным основанием, позволяющих записать любое натуральное число конечным количеством цифр, вообще говоря, бесконечно много. Например, система счисления с основанием, равным квадратному корню из двух. Если использовать лишь каждую вторую цифру (те, которые соответствуют чётным степеням основания), то ей можно пользоваться как обычной двоичной системой счисления:
Точно так же в качестве основания нам подойдут квадратный корень из трёх, кубический корень из двух… Ну, вы поняли мысль. Систем счисления, в которых почти все целые числа будут записываться бесконечной дробью, также немало. Скажу по секрету,
таких даже больше, их континуум. А систем счисления, где натуральное число записывается конечным количеством цифр, лишь счётное множество.
Строго говоря, этим свойством обладает любая система с трансцендентным основанием и достаточным набором цифр. В пи-ичной, е-ичной и даже в е-в-степени-пи-ичной системе счисления все натуральные числа, превосходящие единицу, будут записываться в виде бесконечной дроби.
Система Бергмана отличается и от первой, и от второй группы. В ней любое натуральное число, большее единицы, имеет ненулевое, но конечное количество цифр после запятой. Например:
2 = 10.01Ф
5 = 1000.1001Ф
42 = 10100010.00100001Ф
451 = 1010000001010.000100000101Ф
1984 = (см. эпиграф)
Просторечно выражаясь, это немного рвёт шаблон. Мы привыкли, что понятия «знаки после запятой» и «дробная часть» очевидным образом взаимосвязаны. Однако в фиеричной системе дробная часть может равняться нулю, а количество цифр после запятой при этом — не равняться. Более того, можно доказать, что если количество цифр после запятой равняется нулю, то во всех случаях кроме нуля и единицы ненулевая дробная часть неиллюзорно присутствует.
Пусть у числа есть единицы старше нулевого разряда. Они, как мы уже выяснили, будут соответствовать неким
натуральным степеням Ф. Записав эти степени, раскрыв и сложив их, мы получим число вида a + b√5, где a и b рациональны, а b к тому же строго положительно, как сумма некоторого количества биномиальных коэффициентов, умноженных на некоторое количество пятёрок. Очевидно, такое число не может быть рациональным, а значит, и целым.
Кроме целых чисел, конечным количеством знаков в фиеричной системе счисления записываются также числа из ℤ (Ф), то есть все числа вида:
Как, возможно, заметил внимательный читатель, ни в одной из фиеричных записей, приведённых выше, не было случая, когда две единицы идут подряд. Это не случайно. Как и в фибоначчиевой системе счисления, в системе Бергмана единица старшего разряда равняется сумме двух единицы помладше. Иначе говоря, 100Ф = 11Ф. Это обусловлено уникальным свойством золотого сечения: Ф2 = Ф + 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 ∈ ℚ). Действия над такими числами можно реализовать, используя только операции над рациональными числами. А операции над рациональными числами можно реализовать, используя только сложение, вычитание и умножение целых чисел, которые к потере точности не приводят. Короче говоря, можно написать свою маленькую символьную арифметику. А я всегда хотел её написать.
Как только я понял, насколько страдают обитатели интернета без возможности переводить числа в систему Бергмана и обратно, я немедленно наваял 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), а затем как-то нормализуем запись. Оригинальный (в смысле, изначальный) подход, предложенный Бергманом, состоял в следующем: выписав числа одно над другим, денормализуем их таким образом, чтобы в одном и том же разряде не находились две единицы. После этого сложим их поразрядно (сложение нуля с единицы или нуля с нулём уже не представляет трудности для тренированного математика), затем нормализуем сумму.
Этот подход показался мне настолько забавным, что я написал небольшую игру, которая позволяет игроку ощутить всю прелесть этого подхода лично.
Умножение и деление, впрочем, реализуются более или менее стандартным образом — умножаем в столбик, делим уголком.
И на кой она нужна?
По-хорошему, этот раздел должен писать не я, а какой-нибудь суровый инженер советской закалки. Насколько мне известно, система Бергмана использовалась в некоторых АЦП. Предполагалось использовать её избыточность для большей помехоустойчивости, однако «железная» реализация такого преобразователя оказалась склонна к ошибкам, и идею отправили в ящик. Я бы с удовольствием рассказал больше, но не могу, и честно признаюсь в своей некомпетентности. Надеюсь, кто-то из читателей знает больше — в таком случае я с удовольствием размещу здесь ссылку на его содержательный комментарий.
Ах да, чуть не забыл. Ещё фиеричную систему счисления можно использовать для перемножения целых чисел. Делается это следующим образом:
- Одно из чисел переводится в фиеричную систему счисления и записывается куда-нибудь, желательно на клетчатую бумагу.
- Другое выписывается в клетку под нулевым разрядом первого числа.
- Слева от второго числа пишем произвольное третье число — вообще любое.
- Ряд из второго и третьего числа продолжаем влево и вправо таким образом, чтобы каждое число в ряду равнялось сумме двух чисел справа от него. Получается нечто вроде ряда Фибоначчи, только построенного на других начальных числах и направленного справа налево.
- Просуммируем все числа в этом ряду, над которыми написаны единицы. Эта сумма и будет искомым произведением
Шаг 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
Если у вас плохо с умножением, но вы умеете быстро переводить числа в фиеричную систему счисления и строить фибоначчиобразные ряды, этот метод определённо для вас. Доказательство же его корректности основано на том, что при денормализации записи вверху сумма чисел под её единицами не изменится.
И это всё?
Есть ещё несколько вещей, которые я бы хотел сказать напоследок. Во-первых, если вы как следует помучили мой онлайн-конвертер, то могли заметить, что дробные числа в фиеричной системе счисления, как и в любой другой позиционной, записываются в виде периодической дроби. Доказательство этого факта основывается на делении уголком и опять же не отличается от доказательства, проведённого в системе счисления здорового человека.
Во-вторых, я вам наврал, когда говорил об «уникальном свойстве золотого сечения». Оно, конечно, уникально, но не совсем. Уравнение x2 = x + 1 имеет ещё одно решение, равное
В системе с основанием φ (назовём её антифиеричной) сохраняются все свойства фиеричной системы, которые выводятся из тождества 100Ф = 11Ф. В частности, в ней имеют конечную запись все целые числа (причём ту же самую, что и в фиеричной системе). Это особенно забавно, потому что новое основание не только иррационально, но ещё и отрицательно и по модулю меньше единицы. Можно доказать даже следующую теорему: если число имеет одну и ту же конечную запись в фиеричной и антифиеричной системе счисления, то оно целое.
И наконец, в фиеричной системе счисления формулу числа Ф можно переписать следующим образом:
Это забавно, потому что приведённая формула, если рассматривать её как уравнение, имеет единственное действительное решение. То есть её в самом деле можно использовать как определение числа Ф.
Вдумайтесь в это.
