Троичная система исчисления

Троичная система исчисления так же используется в алгоритмах и в математике. В 70-е годы в СССР даже создали несколько компьютеров, работающих в троичной системе исчисления. Правда такие компьютеры в серию не пошли. Обоснованием создания таких компьютеров служит приводимое ниже рассуждение.

Сколько знаков необходимо для выражения любого числа меньше N. В n-иричной системе исчисления требуется log N/log n знаков (разрядов) каждой из n цифр (0,1,...,n-1). Всего (n/log n) log N цифр. Минимальное значение соответствует случаю, когда log(n)/n принимает максимальное значение. Исследуем функцию log(x)/x, как функцию действительного аргумента. Здесь аргумент х больше нуля, основание логарифма натуральное - е. Дифференцируя

f'(x)=(1-log(x))/(x*x)<0, x>e

получаем, что максимум достигается при х=е, дальше функция монотонно убывает. Следовательно, троичная система исчисления экономичнее четверичной log(3)/3>log(4)/4=2log(2)/4=log(2)/2 и двоичной и любой другой целочисленной системы исчисления.

Приведенное исследование часто используется для сравнения, что больше

X^Y или Y^X, (X^Y>Y^X, e<X<Y).

Например, в Дзене встречается случай X=3, Y=pi. Возводя в степень (1/XY) сводим к исследованию функции x^(1/x)логарифмируя к исследованию функции log(x)/x.

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

Если мы знаем информацию, легче или тяжелее фальшивая монета по сравнению со стандартной, то за -[-log(N)/log(3)] взвешиваний можно найти фальшивую монету используя принцип деления множества монет на три части. Если равенство, то фальшивая находится в оставшейся части. Если перевешивает одна сторона, то из информации (тяжелее или легче) розыск фальшивой сводим к монетам на соответствующей стороне.

Когда не знаем, тяжелее или легче фальшивая монета, за дополнительное взвешивание можем разрешить и этот вопрос. Информация тяжелее или легче двух битовая (с двумя исходами). Поэтому k+1 им взвешиванием фальшивую монету (без информации тяжелее или легче) можно найти и из большего количества монет, чем N=3^k. В Дзене можно найти статью как из 12 монет найти фальшивую за 3 взвешивания.

Деление на 3 используется часто для образования фракталов. Делим интервал на три части и выбрасываем среднюю часть, из оставшихся двух интервалов так же выбрасываем треть по середине и так далее. Остаются только точки без интервалов. В троичной системе исчисления можно оставить так только точки, имеющие координаты только из цифр 0 или 2 (без 1). Это множество точек имеет мощность континуум. Достаточно взаимно однозначно сопоставить точкам интервала сопоставляя цифре 0-->0, 2-->1 в двоичной системе исчисления. В то же время это множество точек имеет нулевую размерность (как размерность пространства).

Взвешивание или построение фрактала можно интерпретировать как представление в (3.1) иричной системе. Под (n.a) иричной системой исчисления я подразумеваю представление целых чисел m в виде многочлена:

m=a0+a1*n+a2*n^2+..., ai= -a,1-a,..., n-a-1. (1)

Здесь цифры могут быть и отрицательными. Однако должно быть 0<=a<=n-2. Если a=n-1, то многие числа нельзя представить в виде (1).

В частности, в (3.1) системе 2=3-1 старшая (в десятках) цифра 1, младшая минус 1. При этом k-битные натуральные числа, являются числами из интервала [(3^(k-1)+1)/2, (3^k-1)/2]. Вот такие троичные системы исчисления.