AOP_Tom2 (1021737), страница 191
Текст из файла (страница 191)
-6)ь, Деление на с( на шаге ПЗ опускаем. (В сущности, числа и и о сдвигаются "виртуально". Такой метод снижает объем вычиглений, если сп малб по сравнению с и.) 38. Присвоим 1с +- и, т +- О, в 4 — 1, ! 4- О, со 4 — и. Тогда сохраняется инвариантное отношение ии = 24" (т+ зь — в) + 2 "!+ 24" '"оис при О < з,ис < 2" н при О < т < 26. Если условие (т, в) = (О, 1) больше не выполняется, то до тех пор, пока !с >.О, положить 4и! = 2"ш' + ис ' и 41+ исо = 2"!'+ 1", где О < ис", !' < 2" и О < !' < 5. Затем присвоить Ф 4- !", со +- ш", в +- 26, т + — 4т+ !' — з, !с +- !с — 1. Если т < О, присвоить в 4- в — 1 и г +- т + 26, в противном случае, если т > 26, присвоить т 4 — т — 26 и з +- з + 1 (зта поправка может понадобиться дважды). Повторять до тех пор, пока не получим 5 = О. Тогда ио = т+ вз — в, так как со всегда умножается на 26" с".
Соответственво, т = О тогда и толысо тогда, когда ио = О. В противном случае результат будет равен в, так как ио — в<в <но+в. з 39. Положим 5! ю 2 >о 16 ~/(85+!). Необходимо выяснить, выполняется ли неравенство 2" '!с псос1 1 < с. Так как я = 45! — 254 — 56 — 5з, этого достаточно для наличия хороших оценок 2" '5! шос) 1, Теперь 2" '5! конгрузнтно (по модулю 1) а„сь/(814+1)+ ) 2" ! ~/(85-!-1), ьй 44 ойв< тс 57 + з 54 + 4 56 + 6 56 252+ 456 25з + 254 + з! 5сб 5! + 4 56+ 456+ 654; 5! — -56+ -56 — -54' ! 1 „! 4 "" З 5! — 54 — -54 — -56' ! ! З 4 85! — 856 — 45з — 854 — 256 — 256 + 5т !п2 = !пЗ = !п5= 4/2 !п(ь/2+ 1) = ь/2 агссап(1/ъ/2) = агссап(1/3) = О= где а„зз = 2" ' 46 шос! (81с + !). Каждый член в первой сумме может быть аппроксимирован посредством вычисления а„,ь при помощи 0(!оЗп) операций (раздел 4.6.3) в пределах 2 .
После этого получится промасштабированное частное (2 а„сь/(85 + 1)). Вторая сумма может быть аппроксимирована в пределах 2 в результате вычисления 2 раз ее первых пс/4 членов. Егли тп ж 2 !8 и, интервал неопределенности будет равен 1/и, что почти всегда обеспечивает достаточную точность. [Ма!5. Соспр. 66 (1997), 903-913.) Примечание.
Пусть Ь = етнс = (1 + !)/4/2 равно корню степени 8 из единицы. Рассмотрим значения! = !п(1-~ /4/2 ). Тогда 16 = !п(1-1/4/2 ), 1! = 1т = з 1и з — ! агсьап 1, 16 = !ь — — 1 !и з — с агсьап(1/4/2 ), 1з = !ь = з!п ь — ! агссап(1/3), !4 = 1п(1+ 1/4/2). Кроме того, -54/2'с~ = с(!о + С '1! + + С" ~414) при 1 < 1 < 8 вследствие 129 — (13). Отсяща 45! — 254 — 5ь — 56 = 2!о — (2 — 2!)2Н + 2!4 + (2 + 2!)1! = я. Другие интересные тождества приведены ниже: В общем случае получаем вьэь = А+ В+ С+Р, ь>о во-~-о — =А — Вч-С вЂ” Р, влив — =А —  — С+Р, 8/с+ 3 вььс †=А+ †С, ь>а 8/с -ь. 7 где 1 1 + л/2в -Ь хо 2>го ! л/йх.л во ' 1 1+в А = — !и —, 8 1 — с 1 С = — агсьап в, 4 1 л/2х Р = — эгссап 2 в с' 2 1 — хо ' и ь-~-а = — — ~!п(1 — в) + (-1)'(текел) !п(1+ в) + /, (в)), тЬ+о т ь>о И и-11/в! ( 2яйо г 2 /, (в) = ~~| сов — !п~! — 2в сов — + х ) уп сп 2кйа в сбп(2я)с/т) ) — 2 сбп — эгс1ап т 1 — с сов(2я)с/т) 40.
Чтобы получить п/2 старших разрядов числа, необходимо выполнить около 2 ь,тйп ава ь в основных операций (см. упр, 15). Используя Ь-эпический метод, где 6 — степень 2, можно получить и/2 младших разрядов числа (см. упр. 4.1-31). Эта задача легко сводится к случаю, когда о нечетное. Пусть имеется три числа: и = ( .. иосссиа)ь, о = (... овос со)ь и ю = (... юоюсюо)ь. Необходимо найти и = ою (по модулю 6"с~). Вычислим о' так, чтобы и'и шос! 6 = 1 (см. упр. 4 5.2 — 17), В этом случае юо = о'иа шос! 6 и можно вычислить и' = и — юао, юл = с'и~о шо46 и т. д. Понадобится выполнить примерно Ьп основных операций, в чтобы вычислить и/2 разрядов справа Таким образом, общее количество операций равно ь по + 0(п), в то время как для выполнения алгоритма Р требуется п~ + 0(п) операций.
Для реализации прямого метода вычисления всех п разрядов справа налево необходимо -'по+ 0(п) онэраций. !См. Т. ЛеЬе!сап, У. ЯушЬо!!с Сошр. 15 (1993), 189 — 180; А. БсЬопЬабе апс! Е. Чегоег, 1 ее!иге !упоев га Сотр Яс1 855 (1994), 448-459 ) 41. (а) Если т=О, то положим о=и.
В противном случае вычтем хю из (и чя г, испо)ь, где х = иоюс шос! 6 Эти нули расположены вне разрядов представления числа, так что мы эффективно уменьшили т на 1. (Эта операция тесно связюса с операцией вычисления в Ь-вдической арифметике частного и/ю, так как для некоторого целого числа д оно равно и/ю = д+ Ь о/ю (см. упр. 4.1-31). Преимущество такого деления заключается в том, что нет необходимости в коррекции пробного делителя.) (Ь) Применим алгоритм (а) для получения ию Необходимый объем памяти останется неизменным, если объединить операции улсножения и вычисления остатка по модулю следующим образом.
Присвоим Ь +- О, 1, О. Пока Ь < п, присваиваем 1 +- 1+ иьи, В +- (1 — хю)/Ь, Ь < — /с+ 1, где х = саю' шос! Ь выбирается так, чтобы 1 — хю было кратным Ь. Тем самым обеспечим инвариантность отношения 6 Г = (иь с .. ио)о (по модулю ю). При этом принимаем, что числа 1, и и о представлены в прямом коде со знаком. Можно оперировать и неотрицательными числами < 2ю или числами, представченными в виде дополнений, как описано Шэндом (ЯЬапс!) и Вуйлеменом (Чшйеппп), а также Корнерупом (Когвегпр) (1ЕЕЕ Яугпр.
Сошрпгег АН!Лшесгс 11 (1993), 252 — 259, 277-283). При большом и для повышения скорости умножения может быть применена методика, описанная в разделе 4.3.3. (с) Представим все числа, конгрузнтные и (по модулю ш), внутренним значением г(и) (г(и) ш Ь" и). Далее операции сложения и вычитания выполняются обычным образом, а операция умножения — в виде г(ис) = Ьпш11(г(и), г(е)), где Ьшэ!! — -операция из алгоритма (Ь). В начале вычислений каждый операнд и заменяется на г(и) = Ьшп!с(и, а), где а = Ь~" шоб ш — константа, полученная до начала вычислений. И наконец заменим каждое г(в) на и = Ьпш!1(г(и),1).
(В приложении к ВЯА-кодированию программа переделана так, чтобы необходимость в предварительных и заключительных вычислениях отпала (см. раздел 4.5.4).) 42. Дж. М. Холт (1. М. Но!Ге) в работе, опубликованной в журнале АММ 104 (1997), 138-149, получил точную формулу Внутренняя сумма равна 2', о( — 1)'(мьо)(5+ 1 — г) = (ь) прн 1' = О. (В упр. 513-25 поясняется причина появления чисел Эйлера.) 43. Согласно упр. 1.2.4-35 получаем ш = (И'/2'~), где И" = (2 + 1) ! = (2 4 1)(ас 4 2"). Поэтому есля ху/255 ) с+ -', имеем с < 2 . Следовательно, ю > ((2ш(с+ 1) +2 — с)/2'э) > с+ 1.
Если хр/255 < с+ -', то получаем ш < ((2'~(с+ 1) — с — 1)/2'~) = с. [См. 3. Г. Вйпп, !ЕЕЕ Сотригег Сгарй!сз апд Аррбс. 14,6 (ХочешЬег, 1994), 78-82.) РАЗДЕЛ 4.3.2 1. Решение единственно, так как 7 11 13 = 1001. Из конструктивного доказательства теоремы С следует, что ответом будет ((11.13) +6. (7 13)'о+5 (7 11)ш) шо41001, Но этот ответ не совсем точный! В соответствии с (24) имеем е~ = 1, ез = (6 — 1) .
8 шоб 11 = 7, ез = ((5 — 1) 2 — 7) бшод13 = 6, так что и = 6 7 11+7. 7+1 = 512. 2. Нет. Найдется хотя бы одно число о, для которого условия теоремы не удовлетворяются. Необходимым и достаточным является дополнительное условие и1 = . = э, (по модулю 1). Из этого следует, что такое обобщение не представляет большого интереса. 3. Из того, что и = и, (по модулю т,), следует и = и, (по модулю йсб(т„ш,)).
Так что, если Решение сУществУет, то Условие Ш = иэ (по модУлю йсс!(т„т,)) должно непременно выполнятьсл. Далее, если и ш с (по модулю шэ) при всех /, то и — е кратно !сш(шп.,., ш„) = вй следовательно, имеется ие более одного решения. Доказательство можно завершить неконструктивным способом, подсчитав число различных г-наборов (иц..., и,), которые удовлетворяют условиям 0 < оэ < тэ и и, = из (по модулю йсб(пэ;, пь!)). Если это число равно гп, то решение должно существовать, так как при изыенеиии числа в от а до а+ т — 1 набор (в шейвиц..., и шоб го,) принимает гп различных значений. Предположим, что выбранные иы..., и, 1 удовлетворяют перечисленным УсловиЯм.
Необходимо подобРать и„ш и, (по модУлю йсб(гпз, т,.)) длЯ 1 < 1 < г. В соответствии с обобщенной китайской теоремой об остатках для г — 1 элементов это можно сделать т„/!сш(йод(тц т,),...,бсср(т„ц т„)) = т,/йсо()сп1(шц..., ш„1), ш„) = !сп1(тц..., ш„)/!сш(тц, т„1) способами. (Данное доказательство основано на тождествах (10), (11), (12), (14) из оаздела 4.5.2.) Конструктивное доказательства (А. 8.
Ггаеп1те1, Ргос. Ашег. Масте. Яос. 14 (1963), 790- 79Ц; обобщающее (25), можно провести следующим образом. Пусть М, = )сш(шт,..., тт); необходимо найти и = в„ЛХ„т+ . +вгМт+вт, где 0 < в, < Мт/Мт т. Предположим, что вт, ..., в; т уже определены. Тогда нужно решить уравнение в,М, т+в, тМ,-г+ +от ы ит (по модулю т,). Здесь в, тМ, г+ .+вт щи, тв и, (по модулю бей(т„т )) при т < у по предположению. Так что с = ит — (вт тМ, г+ +от) кратно 1сш(бсй(тт,тт),...,Вст1(т т, тп )) = Вой(М т, тпт) = йт.
Поэтому нужно решить веют т = с (по модулю т,). В соответствии с алгоритмом Евклида найдется число ст, такое, что с„М т ш йт (по модулю т,): следовательно, можно взять в, = (ст с)/йт шой (тт /йт). Обратите внимание на то, что, как и при неконструктивном способе доказательства, получено шт/йт = Мт/Мт 4. (После вычисления ш, = 91 = 7 13 мы исчерпали все произведения двух или более нечетных простых чисел, меньших 100, поэтому все числа ше, ... должны быть простыми.) ттт = 61, тите = 41, ты = 17. тш =67, тпы = 43, тге = 23, тт = 79, пте = 73, тпе = 71, ты=59, ттт = 37, тите = 31, пете = 47, тте = 29, После этого процесс прерывается (тлгг — — 1 ие подходит). б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
