Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 84
Текст из файла (страница 84)
(в,т ь+ в„ь)тг з+ )ть+ вь) пьойпич из +-(взть+ вь) шой те, иь +- вь пюйть. (Вычисления сэелует выполнять именно в таком порядке, если и и в должны распола- гаться в одних и тех же ячейках памяти, что и допускается в (24).) 10. Если переопределить оператор "шой" так, чтобы оы выдавал значения в симметричной области, то основные формулы для арифметических операций (2)-(4) и уравнений перевода (24) и (25) останутся теми же, а число и в (25) будет принадлежать области (10).
(Здесь (25) — представление е уравновешенней позиционной систеэье счислемил се смеиьаннмм основанием, являющееся обобщением уравновешенной троичной системы.) Сравнение двух чисел можно по-прежнему выполнять слева направо простым способом, описанным в тексте, Далее, если в компьютере реализован прямой код, можно хранить значение числа и в одном машинном слове, даже в том случае, когда глу почты в два раза больше машинного слова, Однако арифметические операции, аналогичные (1Ц и (12), осуществляются сложнее. Создается впечатление, что применение этой идеи на большинстве компьютеров приведет к некоторому замедлению выполнения операшьй. 11.
Умножим на -,'(т+ Ц = (г (гнь + Ц, ..., 1(т, + Ц), 12. Заменим в (1Ц число оьь числом пз, [Можно также выполнить проверку переполненив, если гп нечетно, сохраняя внешние биты ие = и пюй2 ы ве = в шой 2. В таком случае переполнение наступит тогда н только тогда, когда из+во ~ юь+ + вь,-'"1еСпомолулю2, где (шь,..., ю,) — значения разрядов, соответственно с и+ в представленные в системе со смешанным основанием.
13. (а) Пусть равенство х — х м (х — Цх ьп 03 1еСпомодулю10" эквивалентно равенству (х — Цх ш 0 зь'1еСпомодулюр" лля р = 2 и 5. Из зшух чисел х и х — 1 одно должно быть кратным числу р, и тогда другое нз иих будет взаимно простым с р"; поэтому либо х, либо х — 1 должно быть кратным числу р". Если х той 2" ж х шой 5" = 0 или 1, то должно выполняться х шой 10" = О иля 1. Следовательно, свойством автоморфа обладает число, для которого х той 2" Р хпюй5". (Ь) Если х м йр" +г, где г = О или 1, тот ш гз ш гз, так что Зхг — 2хз ш (бйр"г+ Зг) — (бйр"г+ 2г) ш гзь*!еСпоъюдулюр™, (с) Положим с' равным (3(сх)г 2(сх)з)ьхг Зсз 2сзх Примечание.
Так как последние й цифр п-разрядного автоморфного числа образуют lс-разрядное автоморфное число, можно говорить о двух оо-разрядных автоморфных числах х и 1 — х, которые являются 10-адическими числами (см. упр. 4.1-3Ц. Ряд 10-акических чисел эквивалентен ряду упорядоченных пар (иь, вз) чисел, представленных в модулврном виде, где иь есть 2-эдическое число, а из есть 5-адическое число, 14. Найдем циклическую свертку (зе, зь,, з ь) приближений к (аеие, аьш, ... , а„ьи ь) и (авве,аьвь,...,а„ьв„ь) в формате с плавающей точкой, где константы аз = 2 Ри 'е "ЬГ" уже вычислены. Теперь из тождеств и = 2 "„е изаь2"гь" и в = 2',",:е Шаь2зчз" следУет ьв = 2 „е Фьаз2~гь", где Фь ьи зд/аь. ПРи сохРанении тРЕбУемой точности каькдое из чисел будет очень близко к целому.
Представление числа ю может быть легко получено через зтн целые числа, [См. К. Сгаийа!1 апй В. Раб(п, Мазй. Сошр. 62 (1994), 305-324.] РАЗДЕЛ 8.3З 1. 12х23: 02 02 -01 06 Об 0276 34 х 41: 12 12 +03 04 04 1394 22 х18: 02 02 +ОО 16 16 0396 1234 х 2341: 0276 0276 -0396 1394 1394 2888794 3. Прн й < 2 неравенство выполняется, поэтому предположим, что й > 2. Пусть 4» = 2 ', г» = 2л', так что В» = («/Щ н Я» = »г» ~ + В» ь Необходимо показать, что 1 + (В» + 1)2л" < 2а*-'.
Отметим, чта это неравенство грубое. Возможный способ доказательства — проаналнзировать, выполняется лн 1+ (В» + 1)2л» < 1 + 2~~» и 2В» < О» ~ прн й > 2. (Тот факт, что 2В» < б)» и легко доказывается по нндукцнп, поскольку В»+« — В» < 1 и Ц» — Я» «> 2.) 4. Ддя,у = 1, ..., г вычисляем У,(у»), у1)" (уэ), 1)~(р»), уИ (уз); рекурснвно обращаясь к алгоритму умножения, вычисляем И'(у) = %(у') + у(~.0'))(К(у') +/1'(у*)), (4г( ) ((/ (/2) *11 02))(1) ( 3) 1 02)) Тогда получаем Иг,(/ ) = -'(Иг(у)+ И'(-у)), И;,(ут) = -'(Иг(у) — И'(-у)).
Вычисляем также И')(О) = с)(0)«~(О). Затем строим теблнцы разностей дла поливанов И', н И'„степени которых равны г и г — 1 соответственно. Этот метод позволяет уменьшить размер обрабатываемых чисел и количество операций сложения н умножения.
Единственный минус — более длинном программа (так как усложняется управление процессом и некоторые вычисления должны выполняться над чнсламп ео знаком). Другая возможность заключается в определении значений полнномов Иг, н И', в точках 1», 2», 4», ..., (2")э. Несмотря на то что велнчнны обрабатываемых чисел здесь больше, вычисления выполняются быстрее, поскольку все операцнн умножения заменяются операциями сдвига, а все операцнн делении выполняются над двоичными числами вида 2~ (2» — 1).
(Деление на такие числа осуществляется с помощью простых средств.) 5. Начнем настроение последовательностей 4 и г с достаточно больших начальных значений ао и д, так, чтобы выполналось неравенство из упр. 3. После этого вз фар»«ул, аналогичных формулам, которые, предшествоваля теореме В, можно найти, что и« -+ 0 и» = (1+ 1/(2 *))2'г" эа» ~а"»' Щ~/Я» ы).
Прн й -+ оо ~~~~~~ Я~/Ц~~ -+ 1, и поэтому его можно не учитывать, нба необходимо доказать, что» < 1 — е п н всех ь ) И ~ )з* «2о »)2~Г2~ 112» ос +2)ш+1)) ) «/2я» + 1 + 1/(ЗВ»). Отсюда прн достаточно больших й и» < (1 + 1/(2г»))2 'д»л»1 н !8чэ <О. Замечание. Алгоритм Т тоже можно моднфнцнравать так, чтобы он нахадцл последовательность сходного типа до, Ом ..., построенную на базе п в том смысле,. что после шага Т1 п ш 9» + д»+ь Такая моднфнкацяя приводит к оценке (20). 6. Любой общий делитель чисел ба+ И«н 64+ Н» должен также быть делителем нх разности 4» -4ь Такнмп Д) разностями будут 2, 3, 4, б, 8, 1, 2, 4„6, 1, 3, 5, 2, 4, 2, поэтому необходимо только показать, что на каждое нз простых чнсел 2, 3, Ь делится не более чем одно из данных чисел.
Ясно, что только число 69+ 2 четно и только число 69+ 3 кратно 3. Имеется также одно самое большое число, кратное 5, поскольку д» Ш 3 (по модулю 5). 7. Пусть р» з < и < р». Тогда для некоторого постоянного числа с !» < 61» з + сйЗ». Поэтомуг»/6" <!» з/6 '+ой/2 <го+с~у>зу/2» = М. Таким образом, 1» < М 6 О( з»а»в) 8. Ложно.
Для этого достаточно из»смотреть на результат при й = 2. 9. О, = Ори! „зк. В частности, прн 9 = -1 получаем Оз,з »к, что прн выполнении обратного преобразовании позволяет избежать обращенкя данных (побитового инвертиро. ваиня кода). 10. А!1!(э»-з,...,з» зчз»-з-з,...,1о) можно записать в виде -""- "-""- ч-"(Е"-И Е -"' Е 4/ обз» з...„з» зйз о<»<к еб»<к аэто равно Я и„е»Я(р,д), где (Я(р,о)! = 0 или 2'. Для точных значений 2ы/2з чисел р н 9 получаем (Я(р,9)( = 2з, 11.
Автомат не молзет иметь лз = 1 до того, как у него не будет с > 2, а шо в момент 3/ — 1 случится сначала для автомата Мз. Отсюда следует, что автомат М; ие может иметь «зхз хе ~ 000 до момента 3(у — 1) . Далее, если в момент 1 в автомате М» иомпонента»о ф О, то нельзя сделать ло = О, не повлияв при этом на выходные данные. Но на выходные данные нельзя повлиять при указанном значении се, по крайней мере до момента 1+ у — 1, поэтому должно выполняться неравенство 1+ у — 1 < 2п.
Поскольку мы доказали, что 3(2 — 1) < г, должно быть 4(/ — 1) < 2п или, что то же самое, у — 1 < и/2, т. е.,у < (и/2) + 1. Поскольку для обработки входных данных к = е = 2 — 1 необходимо использовать автоматы Мз для всех,у < (н/2) + 1, полученная оценка является наилучшей из возможных. (Например, из табл. 2 видно, что автомат Мз необходим для умножения двухбитовых чисел в момент 3.) 12. Можно "просмотреть" К списков команд для компьютера наподобие й13, выполняя первую команду из каждого списка за 0(К + (Аз!обйз) ) шагов следующим образом.
(з) Алгоритм поразрядной сортировки списка (раздел 5.2.5) сгруппирует все идентичные команды за время 0(К+ Ж). (и) Казкдый из наборов у идентичных команд может быть выполнен за О(!об Аз)з + О(/) шагов, а имеется О(Аз») таких наборов. Все списки будут просмотрены за конечное число просмотров. Остаются очевидные детали, Например, арифметические операции мол»но промоделировать, переведя числа р и 9 в двоичную систему счисления.
(ЫСОМР 9 (1980), 490-508.] 13. Если на перемнозкение двух и-битовых чисел затрачивается Т(п), то умножение пз-битового числа на н-битовое можно выполнить ча (и/гл)Т(ш) + 0(п + гл) операций, разбив для этого и-битовое число на (н/т) групп пз-битовых чисел. Из результатов, полученных в этом разделе, следует, что для машины Тьюринга оценка времени равна 0(п!обтл!ой!обпз), для машин со случайной выборкой слов ограниченного размера— О(п!обт), а для машин с указателями--0(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
