AOP_Tom2 (1021737), страница 64
Текст из файла (страница 64)
Дополнительные ссылки на литературу приводятся в журналах 1ЕЕЕ ТгапвасВопв ЕС-12 (1963), 274 — 276; Сатриеег Рев!8п 6 (Мау, 1967), 52 — 63. Можно полагать, что идея отрицательного основания возникла независимо сразу у целого ряда авторов. Например, Д. Э. Кнут в небольшом маспинописном тексте, предназначенном для конкурса 'Поиск научных талантов" среди учеников старших классов, в 1955 году обсуждал системы счисления с отрицательными основаниями.
Там же обсуждалось и дальнейшее распространение этой идеи на основания, являющиеся комплексными числами. Выбор основания 2г приводит к интересной системе счисления, которую естественно назвать "мнимочетверичной" (по аналогии с 'четверичной'). Такая система обладает необычным свойством, заключающимся в том, что в ней любое комплексное число может быть представлено без знака при помощи цифр О, 1, 2 и 3. (См. П. Е. КписЬ, САСМ 3 (1960), 245-247.) Например, (В!21031)г =1 16+1 ( — 8г)+2-( — 4)+1 (2г)+3 ( — гс) +1( — с) = 74 — 7-,г. Здесь число (аг„...агав.а с .. а гь)сь равно (аг„...агав.а г...а гь) — с+2с(аг„с...огас.а с ..а гь+г)-с, так что перевод числа в мнимочетверичную форму и обратна сводится к переводу в "негачетверичную' форму и обратно действительной и мнимой частей числа.
Интересное свойство этой системы заключается в том, что ана позволяет единасгбразссо выполнять умножение и деление комплексных чисел без разделения действительной и мнимой частей. Например, в этой системе можно перемножить два числа так же, как при любом другом основании, но при этом нужно использовать несколько иное "правило переноса": в случае, если цифра становится больше 3, вычесть 4— н — 1 "перенесется" на два разряда влево; когда же цифра отрицательна, к ней прибавляется 4 и +1 "переносится" на два разряда влево.
Проиллюстрируем это своеобразное правило переноса следующим примером. 1 2 2 3 1 [9 — 10![ 12231 [9 — 10!] 12231 10320213 13022 13022 12231 О 2 1 3 3 3 1 2 1 [-19 — 180![ Аналогичную систему, в которой используются лишь цифры 0 и 1, можно построить и по основанию з/2 !. Однако в ней для представления мнимой единицы ! требуется бесконечное непериодическое разложение. Витторио Грюнвальд1Ъ»йгог!о Сгппв'а!Й) предложил разрешить эту проблему, используя цифры 0 и 1/~/2 в нечетных позициях, однако это фактически испортило всю систему. (См.
Сотшепгвг! <1е!!'А!епео Й Вгезс!а (1886). 43-54.) Используя основание ! — 1, можно также получить "бинарную" комплексную систему счисления, предложенную У. Пенни (%'. Реппеу) [зАСМ 12 (19б5), 247 — 248): (... азпзпзп!пе.п» ... )» 1 — 4ав + (2+ 21)аз — 2!аг + (! — 1)а~ + ае — ~~ (1+1)и — ~ + ' В ней задействованы только цифры 0 и 1. Продемонстрировать, что любое комплексное'число допускает такое представление, можно, рассмотрев интересное множество Я, приведенное на рис. 1. Это множество по определению состоит из всех точек, которые могут быть записаны в виде 2 ь>~вь(г — 1) ь для бесконечной последовательности ам ам аз, ... нулей и единиц. Она известна также как "двуглавый дракон" (см.
М. Р. Вагиз!еу, Кгасга!з ЕгегувЬеге, эесопс( ейг1оп (Асабеш!с Ргевэ, 1993)» 30б, 310). На рис. 1 показано, что множество Я можно разбить на 25б частей, конгруэнтпых — 'Я. Заметим, что если множество л повернуть по часовой 16 стрелке на 135', то оно распадется на два примыкающих одно к другому множества, конгруэнтных (1/~/2) Я, поскольку (! — 1)5 = 5 0 (5+ 1). Детально доказательство того, что множество 5 содержит все комплексные числа, достаточно малые по модулю, рассмотрено в упр. 18.
Быть может, самой изящной из всех систем счисления является уравновешенная гпроичная система счисления (по основанию 3), в которой вместо цифр О, 1 и 2 используются "триты" (троичные цифры) — 1, 0 и +1. Заменив — 1 символом 1, получим следующие примеры уравновешенных троичных чисел.
Рис. 1. Фрактальное множество 5, называемое "двуглавый дракон". 0.1 1 1 1 1 ... Один из способов поиска числа в уравновешенной троичной системе состоит в сле- дующем. Сначала запишем число в троичной системе счисления, к примеру 208.3 = (21201 022002200220.
)з (Очень простой способ перевода в троичную систему, пригодный для вычисления вручную с карандашом н бумагой, описан в упр. 4.4.) Затем добавим к нему в троичной системе бесконечное число ...11111.11111..., после чего получим для Уравновешенные троичные числа 101 1 110.11 1110.11 1110 Десятичные числа 8 321 — 32 ~~ — 33 Х г вышеприведенного примера бесконечное число ( 11111210012 210121012101 )з Наконец, вычтем ...11111.111И... поразрядно, уменьшая на единицу каждую цифру, и получим 208 3 = (101101 101010101010 )з. (8) Этот процесс можно сделать вполне строгим, если заменить искусственное бесконечное число ...
11111.11111... некоторым числом с соответствующим количеством единиц. Уравновешенная троичная система счисления обладает многими привлекательными свойствами. а) Отрицание числа осуществляется взаимной заменой 1 и 1. Ь) Знак числа задается его наиболее значимым ненулевым тритом; в общем случае можно сравнивать любые два числа, используя лексикографический порядок при чтении слова слева направо, как в десятичной системе.
с) Операция округления до ближайшего целого идентична усечению; другими словами, просто отбрасывается все, что стоит правее разделяющей точки. Операция сложения в уравновешенной троичной системе выполняется совсем просто, если воспользоваться таблицей сложения. 1 1 1 1 1 1 1 1 1 О 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 О 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 О 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 О 1 10 11 1 11 1 0 1 0 1 11 1 0 1 0 1 0 1 11 1 0 1 0 1 11 1 11 10 (Три входных трита — это триты двух наших слагаемых и трит переноса.) Вычитание состоит в формировании числа, противопопожного по знаку вычитаемого, и последующем выполнении сложения. Умножение также сводится к операциям перемены знака и сложения, как в следующем примере.
1101 1101 1101 11010 1101 (17) (17] 0111101 (289) Представление чисел в уравновешенной троичной системе неявно присутствует в одной знаменитой математической головоломке, обычно называемой "задача Баше (ВасЬес) о весах", хотя она была сформулирована еще Фибоначчи за четыре столетия до того., как Баше написал свою книгу, а перс Табари сделал зто еще раньше— более чем за 100 лет до Фибоначчи. (См. Ж. АЬгепз, Майетаг!всЛе НпгегЛайип8еп ипг( Яр!е!е 1 (Ее!рз18; ТенЬпег, 1910), 8есбоп 3.4, Н.
Негше1ш)г, .!авив 65 (1978), 105-117.) Позиционные системы счисления с отрицательными цифрами были изобретены Дж. Колсоном (Я. Со!хоп) [РЛ!!ов. Тгапа 34 (1726), 161-173), затем забыты и вновь открыты примерно через 100 лет Джоном Лесли (81г ЛоЬп Ьея!)е) (ТЛе РЛ))ояорЛу о/ АП1Лгпег)с (Ес()пЬцг8Ь, 1817): см. с. 33-34, 54, 64-65, 117, 150( и А. Коши (А. СацсЬу) [Сошргея Кепс)ия Асас). осЛ Ряг(я 11 (1840), 789 — 798].
Коши отмечал, что отрицательные цифры позволяют избежать необходимости помнить таблицу умножения после 5 х 5. Утверждение, что подобные числовые системы были давно известны в Индии (Я. Бхарати (3. ВЬагаг!), Кос))с МагЛеша11ся (Ое!Ь1: Могйа1 Вапагя!с)авя, 1965)), было опровергнуто К. Ш. Шуклой (К.
8, 8ЬцЫа) (Мабйезпазка) Ес(цсаг)оп б, 3 (1989), 129-133(. В "чистом" виде уравновешенная троичная система счисления появилась в статье изобретателя механических вычислительных устройств Леона Лаланна (Ьеоп йа!аппе) (Сотргея Кепс)ия Асяс). Яс1 Рягзя 11 (1840), 903 — 905(. Система оставалась незамеченной до тех пор, пока спустя 100 лет после публикации Лвланна в Электротехническом институте Мура в 1945-1946 годах не стали разрабатывать первые электронные вычислительные машины. В то время она наряду с двоичной системой серьезно рассматривалась в качестве возможной альтернативы десятичной системе. Сложность электронных схем арифметических устройств для уравновешенной троичной арифметики не намного выше, чем для двоичной системы, а чтобы задать число, в ней требуется лишь 1п2/1п3 - 63% цифровых позиций от того количества, которое необходимо для представления чисел в двоичной системе.
Дискуссии по поводу уравновешенной троичной системы счисления опубликованы в журнале. АММ 57 (1950), 90 — 93, и в сборнике Н186-яреес) Сотрпзшй Оекгсея, Епй)пеег)пб ВеяеагсЬ Аяяосзасея (МсСгаш-Нз11, 1950), 287 — 289. Уравновешенная троичная система счисления была положена в основу экспериментальной советской вычислительной машины СЕТУНЬ (см. САСМ 3 (1960), 149 — 150)*. Возможно, симметричные свойства и простая арифметика этой системы счисления окажутся в один прекрасный день весьма существенными (когда "флип-флоп' заменится "флип-флэп-флопомч)**.
Еше одно важное обобшение позиционного способа представления чисел — это позиционная система со смегцаннвзм основанием. Если дана последовательность чисел (6п), где и ыогут быть отрицательными, то по определению полагается ! ...,аз,аг,аз,ао; а ы а г, ..., Ьз, 6г, Ьы 663 Ь „ Ь , (9) + азЬгЬгЬо + аг616о + азЬо + ао + а г/Ь 1 + а г/Ь зЬ г + В простейших системах со смешанным основанием используются только целые числа; Ьо, Ьг, Ьг, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
