Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 83
Текст из файла (страница 83)
Повторять до тех пор, пока не получим Ь = О. Тогда ие г+ зз — з, так как аэ всегда умножается на 2«" з . Соответственно, г = О тогда и только тогда, когда ки = О. В противном случае результат будет раасн э, так как ие — з < з < во+э. з 39. Положим Я = Я«>е16 ~/(85+2). Необходимо выяснить, выполняетсялинеравекство 2" 'л шо61 < -'. Так как х = 43~ — 25а — Яь — Юь, этого достаточно для наличия хороших оценок 2" 'Яз шоа! 1, Теперь 2" 'Яз конгруэнтко (по модулю 1) В общем случае получаем вь+ь — ы А+В+ С+Р„ ь ба+1 вь+в Е* †=А †В+С, 85+ 5 вь+в Е' — =А-В-С+Р, „,85+3 вь+7 — А+В-С-Р, ь>а 8" +У в= — '! 2ггв ! — Ях+ хв' 1 1+х А -!и —, 8 1 — х' 1 С = — эхсгап х, 4 1 ь/2х Р = — эгсгал— 2ьГв 1 — хв' ль+а — = — — ~!п(1 — х) + (-1)'[влетев)!п(1 + х) + У» (в)), +.— в>в 1(м-Ц/в! 2хйа у«т(в) = ~ ! сьн — !в~1 — 2хсов — + х ) 2ьгй 21 гл т 15 .р !1«/) Ь) — 2 вш — агсвап нь 1 — х сов(2хй/гл) 40.
Чтобы получить и/2 старшик разрядов числа, необходимо выполнить около 2 ь ьвьйп и/в ь в основных операций (см. упр, 15). Используя Ь-едический мнгод, где Ь вЂ” степень 2, можно получить и/2 младших разрвдов числа (см. упр. 4.1-31). Эта задача легко сводится к случаю, когда и нечетное. Пусть имеется трн числа: и = (... ивиьво)ь, е = (... еьоь ее)ь и и = (...
июиь ме)ь. Необходимо найти и = оьг (по модулю Ь" Гв). Вычислим о' так, чтобы о'е шов! Ь ы 1 (см. упр. 4.5.2-17). В этом случае ьсв = о'ив шоь! Ь и можно вычислить и' = в — мео„юь = э'ео шоб Ь и т. д. Понадобится вьпюлннть примерно 5 ив основных операций, чтобы вычислить и/2 разрядов глрава. Таким образом, общее количество операций равно -'нз + О(н), в то время квк для выполнения алгоритма Р требуется и + О(п) операций. Для реализации прямого метода вычисления всех и разрядов справа налево необходимо -'в~+О(л) операций.
(См. Т. ЛеЬе!сап, 3. ЯушЬобс Соьпр. 15 (1993), 189-180; А. Бсйопйабе авь! Е. 1гегвег, Ъасгпге !вогез ьл Сошр. Ясб 855 (1994), 448-459.) 41. (а) Если ив=О,то положим в=в. В противномслучаевычтем хм из (и +в ь...вьве)ь, где х = ввм пюб Ь. Эти нули расположекы вне разрядов представления числа, так что мы эффективно уменьшили гл на 1. (Эта операция тесно связана с операцией вычисления в Ь-аднческой арифметике частного в/ьо, так как для некоторого целого числа 9 оно равно в/ьи м 9+ 5~о/ю (см. упр. 4.1-31). Преимущеспю такого деления заключаетск в том, что нет необходимости в коррекции пробного делителе.) (Ь) Применим алгоритм (а) для получения ио. Необходимый объем памяти останется неизменным, если объединить операпии умножения и вычисления остатка по мьщтлю следующим образом.
Присвоим Ь +- О, 1 +- О, Пока Ь с н, присваиваем 1 ь- 1+ вьи, 1 +- (Ф вЂ” хьи)/Ь, Ь +- й+ 1, где х ы Фви,' пюь! Ь выбирается так, чтобм ! — хье было кратным Ь. Тем самым обеспечим инвариантность отношения Ь 1 ы (кь ь... ие)о (по модулю щ). Прн этом принимаем, что числа 1, в и е представлены в прямом коде со знаком. убожко оперировать и неотрицательными числами с 2ш или числами, представленными в виде дополнений, как описано Шэндом (БЬын1) и Вуйлеменом (тц!!!еш!п), а также Корнерупом (Когвггпр) (1ЕЕЕ Яушр.
Сошрнгег АНгбшебс 11 (1993), 252-259, 277-283]. Прн большом и для повышения скорости умножения может быть применена методика, описанная в разделе 4.3.3. (с) Представим все числа, конгруэнтные в (по модулю ш), внутренним значением г(и) (г(н) ш Ь" в). Далее операции сложения и вычитания выполняюгся обычным образом, а операция умножения — в виде г(ве) = Ьпш!г(г(и), г(е)), где Ь|пп1г — операция из алгоритма (Ь). В начале вычислений каждый операнд и заменяется на г(и) = Ьпш!г(в, а), где а = Ьз" шог! ш — константа, полученная до начала вычислений. И наконец заменим глнгдое г(и) на в ж Ьпшй(г(и),Ц. (В приложении к НЯА-кодированию программа переделана так, чтобы необходимость в предварительных и заключительных вычислениях отпала (см. раздел 4,5.4).) 42. Дж, М.
Холт (3. М. Но!ге) и работа, опубликованной в журнале АЛгМ 104 (1997), 138 — 149, получил точную формулу Внутренняя суммаравна 2„(-Ц'( е')(5+1 — г! = ( ) при у = О. (В упр. 5.1.3-25 поясняется причина появления чисел Эйлера.) 43. Согласно упр. 1.2.4-35 получаем ш = 'гИ/2ы), где Й' = (2'+ цг = (2' + ц(во+ 2'). Поэтому, если хр/255 > с+-', имеем с < 2 .
Следовательно, ш > !(2е(с+ Ц+2е-с)/2е ! > с+ 1. Если хр/255 < с+ -', то получаем ы < ((2ы(с+ Ц вЂ” с — Ц/2'е) = с. (Сы. 3. Г. В!!пп, !ЕЕЕ Сошригег Сгарййсэ вад Аррйс 14, 6 (ХотешЬег, 1994), 78-82,) РАЗДЕЛ 4.3.2 1. Решение единственно, так как ? 11 13 = 1001. Из конструктивного доказательства теоремы С следует что ответом будет ((11. 13)в+6 (7 13) о+ 5 (7.1Ц з) шоб 1001. Но этот ответ не совсем точный! В соответствни с (24) имеем е1 = 1, иэ = (6- Ц 8 шод 11 = 7, из ы ((5 — Ц 2 — 7) бпюб13 = 6 твк что в=6 7 11+7 7+1= 512.
2, Нет. Найдется хотя бы одно число и, для которого условия теоремы не удовлетворяются. Необходкмым и достаточным является дополнительное условие в1 ш ш и, (по модулю Ц. Из этого следует, что такое обобщение не представляет большого интереса. 3. Из того, что и ш и; (по модулю та;), следует и ш в, (по модулю боб(т;,тн;)). Так что, если решение существует, то условие и; ш иу (по модулю бей(пц, тз)) должно непременно выполняться. Далее, если и ш е (по молулю нг!) при всех у, то в — е кратно !сш(гпм..., т ) = гп; следовательно, имеется не более одного решения. Доказательство можно завершить неконструктивным способом.
подсчитав число различных г-наборов (им .., „и„), которые удовлетворяют условиям 0 < и < т! и и; ш и (по модулю боб(тц гп!)). Если это число равно гп, то решение должно существовать, так как при изменении числа и от а до и + т — 1 набор (и шоб тм... „и шод нм) принимает я~ различных значений. Предположим, что выбранные вм..., и„1 удовлетворяют перечисленным условиям. Необходимо подобрать в ш из (по модулю боб(тз, пз„)) для 1 <,! < г.
В соответствии с обобщенной китайской теоремой об остатках для г — 1 элементов это можно сделать т,/!сш(бей(тыт,),...,8сб(т, и т,)) = т„/бег!(!ст(тм...,т„1),т„) = 1сго(ты..., пг„)/!сш(пц,..., пм .1) способами. (Данное доказательство основано на тождествах (10), (1Ц, (12), (14) из раздела 4.о.2.) Конструктивное доказательство [А. Б. ггвеп)се1, Ргос. А»пег. Масй. Яос. 14 (1963), 790- 791)„' обобщающее (25), можно провести следующим образом.
Пусть М = (ап(гам... „п»1); необходимо найти е ми,М, с+ . +е»М»+ем где 0 < иг < Мз/М; ь Предположим, что ем ..., ез с уже определены. Тогда нунсио решить уравнение е му» + иу»му з+ + щ а нз (по модулю пг»). Здесь и» см, э+ +ос а к; а в (по модулю боб(татз)) при»'< у по предположению. Так что с= ⻠— (е» »М» э+ ° +и») кратно 1сш(бес((т»,ту),,боб(ту цн»,)) жбсб(М1 мт,) =4. поэтому нужно решить изм»-с а с (по модулю ту). В соответствии с алгоритмом Евклида найдется число см такое, что с М» а 4 (по модулю т ); следовательно, можно взять и, = (с, с)/4, шоб(т>/с(1). Обратите внимание на то, что, как н цри неконструктивном способе доказательства, получено тз/сг» = Мз/511 4.
(После вычисления т» - -91 ы 7 13 мы исчерпали вся произведения двух или более нечетных простых чисел, меньших 100, поэтому все числа пээ, ... должнм быть простыми.) тг 79, тэ = 73, те 71, тсе 67, гпм 61, н»и = 59, тсз =53, т»» = 47, ты =43, тсе = 41, ты=37, тс»=31, т»эы29, сазе=23, тм =17, После этого процесс прерываетса (»пю * 1 не подходит). б.
Нет. Очевидная верхняя граница равна 3»бз72111,, П ~1»»зг»ео1 »» Ф»»И» ° г ар»»»»» и достигается прн т» - -3», тэ = 5з н т. д. (Труднее, однако, определить максимальное значение тс ... »и, в случае, когда г фиксировано, либо максимизировать ес + + е, со взаимно простыми ез, если используются модули 2'с — 1.) 6.
(а) Если е = /+с»у, то 2' = 2»(2»)ь а 2» ° 1» (по модулю 2» -1). Поэтому при 2' а 2» (по модулю 2» — 1) имеем 2' 'е э а 2» '» ' (по модулю 2» — 1); а так как эти последние величины расположены между нулем и 2» -1, должно быть е шос) р = / шоб 9.
(Ь) Согласно п, (а) имеем (1+ 2»+ + 2М Н») . (2' — 1) а (1+ 2»+ . + 2Ы ц') . (2" — 1) м 2"' — 1 а 2»' — 1 а 2» — 1 = 1 (по модулю 2» — 1). 7. имеем и ту с...т» ан»-(е »ту з...тс+ ° +ос) и с т с...тс а 1(помолулю т,) нз (23), (25) и (26); см. Р. А. Рг(ссЬагс(, САСМ 27 (1964), 57.
Этот метод преобразования формул включает столько же арифметических операций, но меньше констант. Количество констант будет меньше только е том случае, если упорядочить модули таким образом, чтобы удовлетворялось неравенство тс < тз « . »н; в противном случае потребуется таблица значений т, п»об»ам Может показаться, что зто упорядочение модулей связано с ббльшимн вычнслнтельнымн затратами, чем если бы мы придавали наибольшие значения сначала модулю глм затем — тз и т. д., так как операций по модулю т нужно выполнить значительно больше, чем по мсщулю ть Но поскольку е может бмть столь хсе большим, как и гл — 1, упорядочение тс < тз « т„лучше ввести и в (24). Таким образом, желательно применить зту идею и к другим формулам в тексте, хотя, как показано в разделе 4.3.3В, они полезны и тогда, когда модули представлены в виде (14).
8. модуль изь: т ь... пзьььг ш пьз-ь...ть( . ((иг — вь)сьг — вг)сзп †.. -вг ь)сп ць ш тг-г... ть (... (иу — вь)с\г — ° ° — вь з)сьг зц -вз-ать-г .., ть = ° ° ° ш иг — вь — взть — ° ° ° вг-ьгпз-г . ° . иьь ° 9. и, ь- ((...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
