Ч -

Рис. 1. Фрактальное множество S, называемое "двуглавый дракон".

Уравновешенные троичные числа Десятичные числа 101 8

1110.11 1110.11 1110

0.11111...

-32 -33

Один из способов поиска числа в уравновешенной троичной системе состоит в следующем. Сначала запишем число в троичной системе счисления, к примеру

208.3= (21201.022002200220... )з.

(Очень простой способ перевода в троичную систему, пригодный для вычисления вручную с карандашом и бумагой, описан в упр. 4.4.) Затем добавим к нему в троичной системе бесконечное число ...11111.11111..., после чего получим для

вышеприведенного примера бесконечное число

(... 11111210012.210121012101.. .)з.

Наконец, вычтем ...11111.11111... поразрядно, уменьшая на единицу каждую цифру, и получим

208.3 = (loiioi.ioioioioioio... )з. (8)

Этот процесс можно сделать вполне строгим, если заменить искусственное бесконечное число ...11111.11111... некоторым числом с соответствующим количеством единиц.

Уравновешенная троичная система счисления обладает многими привлекательными свойствами.

a) Отрицание числа осуществляется взаимной заменой 1 и 1.

b) Знак числа задается его наиболее значимым ненулевым тритом; в общем случае можно сравнивать любые два числа, используя лексикографический порядок при чтении слова слева направо, как в десятичной системе.

c) Операция округления до ближайшего целого идентична усечению; другими словами, просто отбрасывается все, что стоит правее разделяющей точки.

Операция сложения в уравновешенной троичной системе выполняется совсем просто, если воспользоваться таблицей сложения.

iiiiiiiiloooooooooiiiiiiiii ilioooiiiliioooiiiiiioooiii Jjj ijj.Jjjj. oj.J jJ ojj oj. i oj, i o i

1011 i 11 i о 1 о 111 i о i о 1 о 111 i о 1 о 1 11 1 11 10

(Три входных трита - это триты двух наших слагаемых и трит переноса.) Вычитание состоит в формировании числа, противоположного по знаку вычитаемого, и последующем выполнении сложения. Умножение также сводится к операциям перемены знака и сложения, как в следующем примере.

110 1 [17] 110 1 [17] 110 1 110 10 110 1

0 11110 1 [289]

Представление чисел в уравновешенной троичной системе неявно присутствует в одной знаменитой математической головоломке, обычно назьшаемой "задача Баше (Bachet) о весах", хотя она была сформулирована еще Фибоначчи за четыре столетия до того, как Баше написал свою книгу, а перс Табари сделал это еще раньше - более чем за 100 лет до Фибоначчи. [См. W. Ahrens, Mathematische Unterhaltungen und Spiele 1 (Leipzig: Teubner, 1910), Section 3.4; H. Hermehnk, Janus 65 (1978), 105-117.]

Позиционные системы счисления с отрицательными цифрами были изобретены Дж. Колсоном (J. Colson) [Philos. Trans. 34 (1726), 161-173], затем забыты и вновь

открыты примерно через 100 лет Джоном Лесли (Sir Joiin Leslie) [The Philosophy of Arithmetic (Edinburgh, 1817); см. с. 33-34, 54, 64-65, 117, 150] и A. Коши (A. Cauchy) [Comptes Rendus Acad. Sci. Paris 11 (1840), 789-798]. Коши отмечал, что отрицательные цифры позволяют избежать необходимости помнить таблицу умножения после 5x5. Утверждение, что подобные числовые системы были давно известны в Индии [Я. Бхарати (J. Bharati), Vedic Mathematics (Delhi: Motilal Banarsidass, 1965)], было опровергнуто К. Ш. Шуклой (К. S. Shukla) [Mathematical Education 5, 3 (1989), 129-133]. В "чистом" виде уравновешенная троичная система счисления появилась в статье изобретателя механических вычислительных устройств Леона Лаланна (Leon Lalanne) [Comptes Rendus Acad. Sci. Paris 11 (1840), 903-905]. Система оставалась незамеченной до тех пор, пока спустя 100 лет после публикации Лаланна в Электротехническом институте Мура в 1945-1946 годах не стали разрабатывать первые электронные вычислительные машины. В то время она наряду с двоичной системой серьезно рассматривалась в качестве возможной альтернативы десятичной системе. Сложность электронных схем арифметических устройств для уравновешенной троичной арифметики не намного выше, чем для двоичной системы, а чтобы задать число, в ней требуется лишь In 2/In 3 63% цифровых позиций от того количества, которое необходимо для представления чисел в двоичной системе. Дискуссии по поводу уравновешенной троичной системы счисления опубликованы в журнале АММ 57 (1950), 90-93, и в сборнике High-speed Computing Devices, Engineering Research Associates (McGraw-Hill, 1950), 287-289. Уравновешенная троичная система счисления была положена в основу экспериментальной советской вычислительной машины СЕТУНЬ (см. САСМ 3 (1960), 149-150)*.

Возможно, симметричные свойства и простая арифметика этой системы счисления окажутся в один прекрасный день весьма существенными (когда "флип-флоп" заменится "флип-флэп-флопом")**.

Еще одно важное обобщение позиционного способа представления чисел - это позиционная система со смешанным основанием. Если дана последовательность чисел (Ь„), где п могут быть отрицательными, то по определению полагается

• • • ,03,02,Oi,Oo; о 1, о 2,..

• • , Ьз, Ьг, h, Ьо; b-i, Ь 2, • • •.

=----h 03626160 -Ь «26160 + 0160 -Ь Оо -Ь o i/6 i -Ь o 2/6-i6 2 -I----. (9)

В простейших системах со смешанным основанием используются только целые числа; 6о, 61, 62, ... полагаются целыми числами, большими единицы, и рассматриваются только такие числа, которые не содержат разделяющей точки, причем а„ должно принадлежать интервалу О < о„ < 6„.

Одна из наиболее важных систем со смешанным основанием - это факториаль-ная система счисления, где 6„ = п--2. С ее помощью можно единственным образом

* См. также Бруснецов Н. П. и др. Малая цифровая вычислительная м&шина "Сетунь". - М., 1965. - Прим. перев.

** Здесь в оригинале - игра слов. Словосочетание "flip-flop" (дословно "щелчок-шлепок") означает в английской технической литературе элемент с двумя устойчивыми состояниями. По аналогии "flip-flap-flop" (дословно "щелчок-хлопок-шлепок") должно означать элемент с тремя устойчивыми состояниями. - Прим. перев.