AOP_Tom2 (1021737), страница 165
Текст из файла (страница 165)
Например, когда а' = 883 и ав = 70317, достаточно только шести умножений, двух делений, четырех вычитаний: Г в — 883(х шой 2432031) — 274[х/2432031], 1 +- 70317(1 шой 30540) — 2467[1/30540] . [Может ли наихудшее число умножений и делений быть сведено максимум к 11 для всех а и тп, либо 12 является наилучшей верхней границей? Другой способ достичь значения 12 приведен в упр. 4.3.3 — 19.] 12.
(а) Пусть т = 9999998999 = 10'в — 10в — 1. Чтобы умножить (хвхв .. хе)вв на 10 по модулю т, используем тот факт, что 10'ехд щ 10 хд + хв: добавим (хдООО)эв к (хвхв...хвхв)вв. Чтобы избежать циклических сдвигов, представим, что цифры упорядочены на круге. Добавим цифру высшего порядка хд к цифре хв, переместим на три позиции влево и рассмотрим хв как новую цифру высшего порядка. Если хв + хд > 10, то перенос совершается влево.
И если этот перенос покрывает весь путь влево от хв, он совершается не только к позиции хд, но и к позиции хв. Он может распространяться от хд и хг до тех пор, пока процедура не остановится. (21игла также могут не намного превышать тл. Например, 0999999900 переходит в 9999999000 = т + 1, которая переходит в 9999999009 = т+ 10. На избыточное представление не является обязательно пагубным.) (Ь) Это операция 02еленил на 10. Выпшчняем процедуру, обратную процедуре (а): перемещаем цифру высшего порядка влево и еычитаем новую цифру высшего порядка от третьей цифры слева. Если результат вычитания отрицателен, выполняем»заимствование» обычным способом (алгоритм 4.8.18), т. е.
уменьшаем предыдущую цифру на 1. Заимствование может распространяться, как в (а), ио ие за позицию цифры высшего порядка. В результате этой операции числа сохраняются неотрицательными и меньшими, чем тн. (Таким образом, деление на 10 выполняется проще умножения иа 10.) (с) Можно запомнить заимствованный бит вместо того, чтобы распространять его, потому что он может быть включен в процесс вычитания иа следующем шаге. Таким образом, если определить цифру х«и заимствованные биты Ь„рекурревтиой формулой х„= (х«-10 — х«-3 — Ь„) шот) 10 = х«-и — х -3 — Ь + 10Ь 4.1, то, используя индукцию по и, можно получить 9999999000" шат) 9999998999 = Х«, где Х» = (х«-тх«-гх -зх -4х„-зх«-ох«-тх дгх 41х )10 — 10ООЬ 42 = (х»-1х — г х« — 10)10 (х«-1х» — 2х -3)1о Ь при начальных условиях Хо — — 1.
Заметим, что 10Х«е1 = (х»х« — 1х«-2х -Зх«-4х — зх -ох 43х 4гх 410)10 10000Ь 44 = тпх«+Х»; следовательно, 0 < Х„ < т для всех н > О. (т)) Если 0 < бт < т, первая цифра десятичного представления П/т. равна (10бт/т) и последующие цифры являются десятичным представлением (10П шод т)/т (см., наприлгер, метод 2, а в разделе 4.4). Таким образом, У/т = (.итнг .. )10, если положить По = П и К„= 10(,'«1 шоб т = 10Ьтт, 1 — тн„.
Неформально цифры 1/т являются начальными цифрами 10«шот) т при н = 1, 2, Последовательность, в конце концов, периодическая; она совпадает с иачвльнымн цифрами 10 «глоб т, взятыми в обратном порядке. Таким образом, можно вычислять их, как в (с), Точное доказательство, конечна, предпочтительнее неформального. Пусть )т — наименьшее положительное чигло с 101 ш 1 (по модУлю тн). ОпРеделим х«2«х„ж»о 3, Ь« = Ьтт м»О 3, Х = Х««2»01 ДЛЯ ВССХ и < О ТОГДа РЕКУРРЕНтиав СООТНОШЕНИЕ ДЛЯ Х«, Ь и Х«в (с) справедливо для всех целых и.
Если По = 1, та бт« = Х «и н« = х следовательно, 999999900«шод 9999998999 = (.х«тх„-гх«-з .. )1о. (е) Пусть ш — длина компьютерного слова ш, Используем рекуррентное соотношение х«»3(х 3 — х„т — Ь„)шодш=х,. 3 — х 1 — Ь 4-108.„1, где 0 < 1 < Ь и Ь большое.
Тогда (.х«-тх„гх«-з ..)« = Х /т, где тн = цз — ш' — 1 и Х ш = (ш" ' — ш' ')Х«шобт. Соотношение Х = (3» 1 .. х» 3)« — (х» 1,., х„1) + Ь„ справедливо для и > О; величины х 1,, х 3 и Ьо должны быть такими, что 0 < Хо < т. Такие генераторы случайных чисел и подобные им (см. слелутощие упражнения) были введены в работе С. Магза8110 апд А. Еашап, АвпаЬ 01 Арр)тед Ргобабт)тгу 1 (1991), 462 — 480. Авторы назвюти свой метод емчннзанием с заимствованием. Пни всходили из представления с основанием ш дробей со знаменателем тн. Связь с линейной конгруэнтной последовательностью была зал)ечена Шу Тезука (Яйн Техн)са) и детально проанализирована в работе ТехпЫа, 1 'Еспуег апд Сопзпге, АСМ Тгапз.
54о))е))нб авс) Сошртег Япш)ас)оп 3 (1993), 315 — 331. Длина периода обсуждалась в упр. 3.2.1.2-22. 13. Для умножения на 10 сейчас требуется представление добавленных цифр в виде отрицания их дополнения. Для этого удобно представить число так, чтобы последние три цифры заменялнсь отрицанием их дополнений, например 9876543210 = (9876544790))о. Тогда на 10-м шаге (хд.. хзхзх)хо)ю равно (хз...хзх х)хохд)ш, где х' = хз — хз Аналогично (хо...хзхзх)хо))о. деленное на 10, равно (хохо...хзхойзх)))о, где хо = хо — гз. Из рекуррентного соотношения х»»» (х„з — х» ш — Ь )) шо610 = х» з — х„)о — Ь»-) +105 следует 8999999101" шоб 9999999001 = Х„, где Х» = (х -)х»-зхп-зх»-зх — зх»-зх» — гх»озх т!х»)10+ 10005 хз =(х -)х -з ..х»-)о))о — (х -)х»-зх»-з))о+Ь)- Когда за основание системы счисления вместо 10 принимается ю, находим, что обратная степень ю по модулю ю — ю + 1 порождена рекуррентным соотношением л ) х» ж (х„) — х„л — Ь ) шос) и) = х„) — х,)-л — Ь» + шЬ о) (таким же, как в упр.
12, но Ь и 1 меняются пестами). 14. Небольшое обобщение. Для любого Ь, меньшего или равного длине слова ю, можно эффективно осуществлять деление на Ь по мо,аулю Ь вЂ” Ь х1. Таким образом, рекуррентное л соотношение для х» почти так же эффективно при Ь < ю, как и при Ь = ю. Сильное обобщение. Рекуррентное соотношение ) а,х„, + + а),х„з + с» ) х„= (а)х ) + + азх„л + с„) пю)) Ь, с»») — ~ эквивалентно Х„= Ь )Х„) шос) )т) в том смысле, что Х»/~т~ = (.х„)х„з .. )з, если определить т и Х„следующии образом: =,ь' ",ь — ), х. »(З»[*.— ..
*. ) .))»л ) Начальные значения х )... х л и со должны быть выбраны так, что О < Хо < )т~) тогда получим х = (ЬХ„т) — Х )/)т) для и ) О. Значения хз для 7' < О, которые появляются в формуле Х»/~т) = (х )х» з,. )„можно просто рассиатриватзч как х,ел, где Ь ш 1 л (по модулю т). Эти величины могут отличаться от заданных вначале чисел х ),..., х Цифра переноса с удовлетворяет неравенствам ~ ~пни(О,аз) < с» < ~ ~шах(О,а ), если начальный перенос со лежит в тех же пределах. Представляет особый интерес случай, когда гн = Ь + Ь вЂ” 1, для которого а, л б ) + 51л, поскольку он легко вычисляется Марсалья и Заман назвали его генераторолз суммирования с переносом: х» = (х» — ) +х — ) ч с») шойЬ= х, -) + х»-о+с — Ьс х), Другой привлекательной потенциальной возможностью является использование )с = 2 в генераторе с, скажем, Ь = 2з' и т = 65430Ьз + Ь вЂ” 1.
Этот модуль т является простым числом, и длина периода оказывается равной (т — 1)/2. Спектральный тест из раздела 3.3.4 показывает, что интервал между уровнями хороший (большие значения и), хотя, конечно, множитель Ь ' плохой по сравнению с другими множитглямн для этого значения модуля т.
В упр. 3.2.1.2 — 22 содержится дополнительная информация о модулях, позволяющих получить чрезвычайно длинные периоды в методах 'вычитание с заимствованием' и есуммирование с переносом". РАЗДЕЛ 3.2.1.2 1. Согласно теореме А длина периода равна т (см. упр. 3). 2. Да, из этих условий следует, что выполняются условия теоремы А, так как единственным простым делителем 2' является 2 и любое нечетное чншю является относительно простым с 2'.
(На самом деле условия упражнения являются необходпмммп и достаточными.) 3. Согласно теореме А требуется, чтобы а = 1 (по модулю 4) и а ы 1 (по модулю 5). По закону П нз раздела 1.2.4 зто эквивалентно тому, что а ы 1 (по лгоггулю 20).
4. Из теоремы А следует, что Хг. е: — О (по модулю 2' ') (случай, когда т = 2' ') Используя также теорему А при т = 2", получим, что Хг. е х О (по модулю 2"). Отсюда сдедует равенство Хге-е — — 2' '. Вообще говоря, можно использовать формулы 3.2 1 — (6) для доказательства того, что вторая половина периода, по существу, подобна первой половине, так как Х„„г. е — — (.Х„+ 2' ~) шо62'.
(Четверти также подобны; см. упр. 21.) б. Необхолимо, чтобы выполнялось следующее соотношение а = 1 (по модулю р) для р = 3,11>43,281,861?1. По закону П из раздела 1.2.4 это эквивалентно тому, что а э— з 1 (по модулю 3 11 43 281 86171). Итак, веееенствегенмм решением будет ужасный множитель а = 1, 6. (См.
предыдущее упражнение.) Из подобия а ш 1 (по модулю 3 7 11 13 . 37) следует, что решением будет число а = 1+ ) 11111?с для О ( ?с ( 8. 7. Воспользуемся обозначениями из доказательства леммы с). ?е является наименьшим значением, при котором Х„хг = Х„; также оно является наименьшим значением, при котором 1;,+х = 1;, и Я„.„г = И, Таким образом, показано, что д = шах(рц,. еде). Наибольшим из возможных значений д есть шах(ем..., ее), но никто не пытается достичь его.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
