AOP_Tom2 (1021737), страница 192
Текст из файла (страница 192)
Нет. Очевидная верхняя граница равна — П р аечв ав р праевае и достигается прв тт = Зе, тг = 5' и т. д. (Труднее, однако, определить максимальное значение тт ... тп„в случае, когда г фиксировано, либо максимизировать ет + + е, со взаимно простыми е;, если используются модули 2'т — 1.) 6. (а) Если е = у'+Лд, то 2' = 2т(2т)а ьв 2т 1е (по модулю 2т — 1). Поэтому при 2' ш 2т (по модулю 2г — 1) имеем 2' ~'~ т вэ 2т 'е т (по модулю 2т — 1); а так как эти последние величины расположены между нулем и 2т — 1, должно быть е пют1 д = у пюй д. (Ь) Согласно п. (а) имеем (1+ 2" + +2ы Н") (2' — 1) и (1+ 2е+ + 20 це) (2 — 1) = 2'е — 1 щ 2" — 1 щ 2' — 1 = 1 (по модулю 27 — 1).
7. Имеем в.тп, т...тт = и: — (в„тшт г... тт+ . +вт) и Сттт т ... тт щ 1 (по модулю тл„) из (23), (25) и (26); см. Р. А. РгНсЬагй, САСМ 27 (1964), 57. Этот метод преобразования формул включает столько же арифметических операций, но меньше констант. Количество констант будет меньше только в том случае, если упорядочить модули таким образом, чтобы удовлетворялось неравенство те < тг « т,; в противном случае потребуется таблица значений ш, пюйт;. Может показаться, что это упорядочение модулей связано с ббльшими вычислительными затратами, чем если бы мы придавали наибольшие значения сначала модулю тт, затем — тпг н т.
д., так как оперелттй по модулю т, нужно выполнить значительно больше, чем по модулю тпт. Но поскольку в; может быть сталь же большим, как и т, — 1, упорядочение тт < птг « .. т, лучше ввести и в (24). Таким образом, желательно применить эту идею и к другим формулам в тексте, хотя, как показано в разделе 4.3.3В, они полезны и тогда, когда модули представлены в виде (14). 8. Модуль!и!.' 7пэ-!,. п$!в! щ эпэ-! «. т!( .. Ки! в!)с!! вэ)сэ! ' ' ' в! — !)с(! !В щ тэ-.э...
гп! (... (и! — е!)Г!! — ' ' ' вэ-2)с!! э)!' вэ-!гпэ-2... т! — и! в! — в2т!— — и! гп0 е...гп!. 9. и, +- ((...(в,т„ ! + о, !) т, ! + . )т! + в!) то!1 т,, иэ е — (вот! + в!) той те, и! с — о! шобт!. (Вычисления следует выполнять именно в такам порядке, если и, и в! должны распола- гаться в одних и тех же ячейках памяти, что и допускается в (24).) 10. Если переопределить оператор "шо!1" так, чтобы оп выдавал зиачеиия в симметричной области, то основные форлэулы для арифметических операций (2)-(4) и уравнений перевода (24) и (25) остаиутся теми же, а число и в (25) будет принадлежать области (10). (Здесь (25) — представление в уравновешенной позиционной сисэпеме счисления со смешанным основанием, являющееся обобщением уравновешенной троичной системы.) Сравнение двух чисел можно по-прежиему выполнять слева направо простым способом, описанным в тексте.
Далее, если в компьютере реализовав прямой код, можно хранить значение числа и в одном машинном слове, даже в том случае, когда т, почти в два раза больше машинного слова. Однако арифметические операции, аналогичные (11) и (12), осуществляются сложнее. Создается впечатление, что применение этой идеи иа большинстве компьютеров приведет к иекоторому замедлению выполнения операций. 11. Умиожим иа -'(гп+ 1) = (-'(гп! + 1), ..., -'(т, + 1)).
12. Заменим в (11) число т, числом гп. [Можио также выполнить проверку переполнения, если гп нечетко, сохраияя внешние биты ио = ищо42 и во = вгпое12. В таком случае переполнение наступит тогда и толька тогда, когда ио+во Ю ш! + + ш 1'эеСпомалулю2, где (ю!,..., ш,) — значения разрядов, соответственно с и+ в предстаалеииые в системе со смешанным осиоваиием.
13. (а) Пусть равенство хэ — х = (х — 1)х щ О-' ХеСпомещулю10" эквивалеитио равенству (х — 1)х щ 0-!*/еСпомозулюр" для р = 2 и 5. Из двух чисел х и х — 1 адно должно быть кратным числу р, и тогда другое из иих будет взаимио простым с р": поэтому либо х, либо х — 1 должно быть кратным числу р". Если х шоб 2" = х щое1 5" = 0 или 1, то должно выполняться х пюй 10" = 0 или 1. Следовательио, свойством автоморфа обладает число, для которого х шо!1 2" ~ х щоб 5".
(Ь) Если х = йр" + г, где !. = О или 1, то ! щ г! = гэ, так что Зх' — 2хэ щ (бор"г+ Зг) — (бвр" г+ 2г) ж г-'*уеСпомодулюрэ". (с) Положим с' равиь!м (3(сх)э — 2(сх)э)/хэ = Зс! — 2сэх. Примечание. Так как последние й цифр и-разрядиого автоморфиого числа образуют Й-разрядное автоморфиое число, можно говорить о двух оо-разрядпых автоморфиых числах х и 1 — х, которые являются 10-адическими числами (см. упр.
4.1 — 31). Ряд 10-адических чисел эквивалентен ряду упорядоченных пар (и!, и!) чисел, представленных в модуляриом виде, где и! есть 2-эдическое число, а и! есть 5-адическое число. 14. Найдем циклическую свертку (хо, э!, ..., с„!) приближений к (асио, а!и!, ... ..., а„!и !) и (аево,а!в!,...,а !в„!) в формате с плавающей точкой, где константы ае = 2 !гв мве"!1" уже вычислены. Теперь из тождеств и = 2 "„е ива!2"е!" и в 2 „" о веаь2ье!" следует ш ю 2 " 1еае2"е!", где Е! хь!Гаь.
При сохранении требуемой точности каждое из чисел будет очень близко к целому. Представление числа ю может быть легко получено через эти целые числа. (См К. Сгаш1ай апд В. габ!и, Ма!И. Сотр. 62 (1994), 305 — 324.] РАЗДЕЛ 4.3.3 1. 12х23: 02 02 — 01 Об Об 0276 34 х 41: 12 12 +03 04 04 1394 22 х 18: 02 02 +00 16 16 0396 1234 х 2341: 0276 0276 — 0396 1394 1394 2888794 *./а+г2»гь~ч Л [а+гга г=га+г, " нгага г аг+~. 3. При й < 2 неравенства выполняется, поэтому предположим, что й > 2. Пусть аь = 2 ", г» = 2 ", так что Вь = (ь/К) и Я» = Яь 2 + Л» 2. Необходимо показать, яь что 1 + (В» + 1)2"ь < 2аь-г. Отметим, чта это неравенство грубое.
Возможный способ доказательства — проанализироватьг выполняется ли 1 + (Яь + 1)2 ' < 1 + 2 ль 2вь и 2»г» < Я» г при 12 > 2. (Тат факт, что 221» < Я» г, легко доказывается по индукции, поскольку В»+г — Я» < 1 и Яь — Яь 2 > 2.) 4. Для 3 = 1, ..., г вычисляем 5;(22), уУ,(уг), 12,(32), у)2,(22); рекурсивно обращаясь к алгоритму уиножения, вычисляем Иг(3) — (Н (32)+ (/ 02))(14(32) +71»(72)) И (-у) = (и,(/' ) - у(/.(у'))(И О') - у) .(у')).
Тогда получаем И',(уг) = г (ИЩ)+Иг( — 1)), И' (12) = 2(И(у) — И~(-2)). Вычисляем также И;(0) = (/(0)ЦО). Затем стРоим таблицы Разностей дла полиноиав Игг и И'„степени которых равны г и г — 1 соответственна. Этот метод позволяет уменьшить размер обрабатываемых чисел и количество авераций сложения и умножения. Единственный минус — более длинная програмиа (так как усложняется управление процессам и некоторые вычисления должны выполняться над числами со знаком).
Другая возможность заключается в определении значений полиномов И', и И'„в точках 1, 2, 4, ..., (2")2. Несмотря на то что величины обрабатываемых чисел здесь 2 2 2 больше, вычислении выполняются быстрее, поскольку все операции умножения заменяются операциями сдвига, а все операции деления выполняются над дюичными числами вида 2'(2" — 1).
(Деление на такие числа осуществляется с помощью простых средств.) 5. Начнем построение последовательностей г7 и г с достаточно больших начвлыпях значеняй да и яг так. чтобы выполнялось неравенство из упр. 3. После этого из формул, аналогичных формулам, которые предшествовали теореме В, можно найти, что пг -+ 0 и 212 = (1+ 1/(2г~))2~~ 20» 2»1»+' (1,1»я» ы). При й -» оо множитель »Е»/»1»+» -» 1, и поэтому его можно не учитывать, ибо необходимо доказать, что 02 < 1 — е при всех г .
и,, га„, -~го, г1 22,1~2 [га, г»га гг+г ч/2»еь + 1 + 1/(Зггь). Отсюда при достаточно больших к 02 < (1 + 1/(2гь))2 ~гг~~»1 и 18 212 < О. Замечание. Алгоритм Т тоже можно модифицировать так, чтобы он находил последовательность сходного типа 92, дг, ., ч построенную на базе и в тои смысле,, что после шага Т1 и — 9» -» д»ег. Такая модификация приводит к оценке (20). б. Любой обньнй делитель чисел бд + »12 и бо + 42 должен также быть делителем их разности 42 — г1». Такими (е) разнастяии будут 2, 3, 4, б, 8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, поэтому необходимо только показать, что на каждое нз простых чисел 2, 3, 5 делится не более чем одно из данных чисел, Ясно, что только число бд+ 2 четно и только число бд+ 3 кратно 3. Имеется также адно самое большое число, кратное 5, посказьку йь ж 3 (по модулю 5).
7. Пусть рь с < и < рю Тогда для некоторога постоянного числа с Сь < ВСь с + с!сЗ . Поэтому сь(б < Сь с/б +ой/2 < Со+ с1',>,1/21 = М. Таким образом, Сь < М б О(р',""). 8. Ложно. Для этого достаточно посмотреть на результат при й = 2. 9. й, = йсом,ох. В частности, при д = — 1 получаем й! „> мрак, что прн выполнении обратного преобразования позволяет избежать обращения данных (побитового инвертирования кода). 10. А!"!(зь ц.,., ос м Сь, и..., Со) можно записать в виде Е о«,,, л,,бс о<о<к о<о<8 а это Равно 2 р о иРооБ(Р, д), где )Б(Р, д)! = 0 или 2~. ДлЯ точных значений 2™/2' чисел Р и о получаем (Б(р,й)) = 2'.
11. Автомат не может иметь оо = 1 до тога, как у него не будет с > 2, а эта в момент 3( — 1 случится сначала для автомата М,. Отсюда следует, что автомат М, не может иметь вросло ф 000 до момента 3(1 — 1). Далее, если в момент С в автомате М, компонента го ф О, то нельзя сделать со = О, не повлияв при этом на выходные данные. Но на выходные дшрные нельзя повлиять при указанном значении ло, по крайней мере до момента С+( — 1, поэтому должно выполняться неравенство С+ у — 1 < 2п. Поскольку мы доказали, что З(1 — 1) < й должно быть 4(1 — 1) < 2п или, что то же самое, ( — 1 < и/2, т.
е. ( < сп(2) + 1. Поскольку для обработки входных данных и = о = 2" — 1 необходимо использовать автоматы М, для всех ( < (и/2) + 1, полученная оценка является наилучшей из возможных, (Ншсример, из табл. 2 видно, что автомат Мо необходим для умножения двухбитовых чисел в момент 3.) 12. Можно "просмотреть" К списков команд для компьютера наподобие 811, выполняя первую команду из каждого списка за 0(К + (Х!об Х) ) шагов следующим образом. (!) Алгоритм поразрядной сортировки списка (раздел 5.2.5) сгруппирует все идентичные комацлы за время 0(К + Х). (О) Каждый из наборов у идентичных команд может быть выполнен за О(!обХ) + О(() шагов, а имеется О(АР~) таких наборов. Все списки будут просмотрены за конечное число просмотров.
Остаются очевидные детали. Например, арифметические операции можно промапелировать, переведя числа р и д в двоичную систему счисления. (Б1СОМР 9 (1980), 490 508.) 13. Если на перемножение двух п-битовых чисел затрачивается Т(п), то умножение т-битовога числа на и-битовое можно выполнить за (п(т)Т(пс) + 0(п + гл) операций, разбив для этого и-битовое число на )и/т) групп т-битовых чисел. Из результатов, полученных в этом разделе, следует, чта для машины Тьюринга оценка времени равна О(п!окт !оВ!обгп), дли машин со случайной выборкой слов ограничешюго размера— 0(п 1аб т), а для машин с указателями — 0(п).
15. Известная наилучшая верхняя оценка, равная 0(п(!об и) !об !об и), предложена М. Дж. Фишером (М. 3. Г!зсЬег) и Л. Дж. Штокмейером (Ь. 1. Бсос!ошеуег) (Х Сашр. ааа Бузе. Бой 9 (1974), 317-ЗЗЦ. Рассматриваемая ими конструкция ориентирована на машину Тьюринга с множеством лент; для машин с указателями зта оценка равна 0(п!оба). М. С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
