[Перевод] Почему троичные вычисления лучше двоичных22.10.2024 14:30

Давно изучаемая, но нечасто применяемая вычислительная система с основанием 3 всё же может найти применение в кибербезопасности.

Как рассказывали детям 1970-х годов в Schoolhouse Rock!, три — это магическое число. Три поросенка; три кровати, миски и медведя для Златовласки; три трилогии «Звёздных войн». Чтобы табуретка стояла сама по себе, нужно как минимум три ножки, и как минимум три точки, чтобы определить треугольник.

Число 3 также предполагает другой способ счёта. Наша знакомая десятичная система счисления с основанием 10 использует 10 цифр от нуля до 9. Двоичная система, наш цифровой lingua franca, представляет числа, используя только две цифры: 0 и 1.

Но математики давно изучают число три. Рассмотрим, например, основание 3 или троичную систему, которая использует три цифры. Обычно это цифры 0, 1 и 2, но так же используются и симметричные обозначения: –1, 0 и 1.

Отличительной чертой троичной записи является ее невероятная эффективность. С помощью двух двоичных битов можно представить четыре числа. Два «трита» — каждый с тремя различными состояниями — позволяют представить девять различных чисел. Число, требующее 42 бита, потребует всего 27 тритов.

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

Чтобы понять почему это так, рассмотрим важный показатель, который подсчитывает, сколько места системе понадобится для хранения данных. Вы начинаете с основания системы счисления и умножаете его на количество цифр, необходимых для представления некоторого большого числа в этой системе. Например, число 100 000 в десятичной системе счисления требует шести цифр. Его «экономичность» составляет 10 × 6 = 60. В системе счисления с основанием 2 тому же числу требуется 17 цифр, поэтому его экономичность составляет 2 × 17 = 34. А в системе счисления с основанием 3 требуется 11 цифр, поэтому его экономичность составляет 3 × 11 = 33. Для больших чисел основание 3 имеет лучшую экономичность, чем любое другое целое основание. (Удивительно, но если вы позволите основанию быть любым действительным числом, а не только целым, то наиболее эффективным основанием является иррациональное число e.)

Вот математическое доказательство этого:

Обозначим p основание системы счисления, n — количество требуемых знаков. Тогда получим $\dfrac{n} {p}$ цифр, требуемых для записи этого набора знаков в заданной системе счисления Количество чисел, которое при этом можно записать, будет равно $p^{\dfrac{n}{p}}$ .

Рассмотрим это выражение как функцию переменной p, принимающей любые положительные значения: $y(p) = p^{\dfrac{n}{p}}$ .

Найдём максимум этой функции, для этого найдём, когда первая производная от функции будет равна 0, $\dfrac{\mathrm{d} y}{\mathrm{d} p} = \dfrac{-n}{p^{2}} \cdot p^{\dfrac{n}{p}} \cdot \ln(p) + p^{\dfrac{n}{p} \cdot p^{\dfrac{n}{p - 1}} = n \cdot p^{\dfrac{n}{p - 1}} \cdot (1 - \ln(p))$ , производная будет равна 0 когда $1 - \ln(p) = 0$ , т.е. когда p = e .

Слева от точки p = e производная $\dfrac{\mathrm{d} y}{\mathrm{d} p}$ положительна, а справа отрицательна, таким образом, учитывая теоремы дифференциального исчисления, получаем, что при p = e функция y(p) действительно имеет максимум.

Из целых чисел максимум функция y(p) имеет при p = 3 . Поэтому троичная система счисления — самая экономичная целочисленная система счисления.

В дополнение к числовой эффективности основание 3 предлагает вычислительные преимущества. Оно предлагает способ сократить количество запросов, необходимых для ответа на вопросы с более чем двумя возможными ответами. Двоичная логическая система может отвечать только «да» или «нет». Поэтому, если вы сравниваете два числа, x и y, чтобы узнать, какое из них больше, вы можете сначала спросить компьютер:»x меньше y?» Если ответ «нет», вам нужен второй запрос:»x равен y?» Если ответ «да», то они равны; если ответ «нет», то y меньше x.

Система, использующая троичную логику, может дать один из трех ответов. Благодаря этому, ей требуется только один запрос:»x меньше, равно или больше y?»

Несмотря на естественные преимущества, вычисления на основе 3 так и не получили распространения, хотя многие математики восхищались их эффективностью. В 1840 году английский печатник, изобретатель, банкир и математик-самоучка по имени Томас Фаулер изобрел троичную вычислительную машину для расчета взвешенных значений налогов и процентов. «После этого в течение многих лет делалось очень мало», — сказал Бертран Камбу, прикладной физик из Университета Северной Аризоны.

В 1950 году, на заре цифровой эпохи, в большом докладе о вычислительной технике того времени говорилось о вычислительном преимуществе троичной системы. А осенью 1958 года гости Советского Союза сообщили, что инженеры там разрабатывают троичную вычислительную машину под названием «Сетунь» — первую современную вычислительную машину, основанную на троичной логике и аппаратном обеспечении. Советские ученые построили десятки машин «Сетунь». На Habr есть хорошая статья про эти машины.

Почему троичные вычисления не прижились? Основной причиной была условность. Хотя советские ученые создавали троичные устройства, остальной мир сосредоточился на разработке оборудования и программного обеспечения на основе коммутационных схем — основы двоичных вычислений. Двоичные вычисления было проще реализовать.

Но в последние несколько лет произошёл некоторый прогресс. Инженеры предложили способы создания троичных логических систем даже на двоичном оборудовании. А Камбу при поддержке американских военных разрабатывает системы кибербезопасности, использующие вычисления по основанию 3. В работах, опубликованных в 2018 и 2019 годах, он и его коллеги строго описали троичную систему, которая могла бы заменить существующую инфраструктуру открытых ключей, включающую цифровые ключи для шифрования или дешифрования киберкоммуникаций. По его словам, переход от битов к тритам значительно снижает частоту ошибок, поскольку троичные состояния лучше управляют неустойчивой информацией.

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.