AOP_Tom2 (1021737), страница 91
Текст из файла (страница 91)
[М25[ .Целое число и, принадлежащее симметричной области (10), можно было бы представить при помощи чисел им ..., и„таких, что и ш и, (по модулю тэ), удовлетворяющих условию — гп,/2 < и, < т,/2 вместо условия 0 < и < т, как укаэюю в тексте раздела. Рассмотрите процедуры модулярной арифметики для такого симметричного представления, включан процедуру перевода (24). 11. [Мдд] Допустим, все числа т, — нечетные и известна, что и = (иц ..,, и„) — четное число при 0 < и < гп.
Используя модулярную арифметику, найдите достаточно быстрый способ вычигтения и/2. Обратите внимание на тождество 21 - зх1 = 1 (по модулю т). В общем случае, если е и т являются взаимно простыми, можно найти (по алгоритму Евклида) число е' (е'„..., е„'), такое, чта ее' ш 1 (по модулю т). Далее, если известно, что и кратно е, та и/е = ие' вычисляем при помощи мадулярного умножения. Если е не является взаимно простым с пз, то деление выполняется значительно сложнее.
12. [М10[ Докажите, чта, если 0 < и, е < т, мадулярное сложение чисел и и е приведет к переполнению (т. е, полученное число будет находиться за пределамн допустимой области) тогда и только тогда, когда сумма меньше числа и. (Таким образом, проблема обнаружения переполнения зквивачентна проблеме сравнения.) ° 13. [М05] (Авп)еморфн.) Деситичное и-разрядное число х > 1 математиками-шутниками называется автоморфом, если последние н цифр числа х' равны х. К примеру, 9 376 есть 4-разрядный автоморф, так как 9376 = 87909 376. [См. бс!елпбс Ашег)сал 218 (Лаввагу, 1968), 125.] а) Докажите, что и-рэзрядное число х > 1 есть автоморф тогда и только тогда, когда хто«15" = 0 (или 1) и хто«) 2" = 1 (или 0) соответственно. (Таким образом, если т« = 2" и т» = 5", то в (7) только числа М«и М» являются и-разрядными автоморфами.) Ь) Докажите, что если х есть н-разрядный автоморф, то (Зх~ — 2хз) щод 10~" является 2ж-разрядным автоморфом.
с) Пусть известно, что сх «э 1 (по модулю 9). Найдите простую формулу для числа с', являющегося функцией с и х, но не у, которая (формула) имеет вид с'х = 1 (по модулю 9»). ь 14. [МУО] (Мерзкое умноясенве.) По определению циклическая свертка (хе, х),,х «) и (уа, .ун..., у «) есть (х«, хм..., х «), где х;9, для 0 < )с < и. сюяь (и» м«ду«юи) Эффективные алгоритмы для циклической свертки будут рассмотрены в разделах 4.3.3 и 4.6.4.
Рассмотрим 4-битовые целые числа и и в, которые представлены в виде п — 1 в = ~ ~в«2) «)"), и = ) и«2)"«)"), где 0 < вы в« < 2П"+')«)") )~«)"). (Такое представление является смесью оснований 2)»дй и 2)«)").) Используя подходящую циклическую свертку, предложите хоро«яий способ поиска представления числа ш = (ив) п«о«((2» — 1) . [Указание. Не бойтесь использовать вычисления в формате с плавающей точкой.] в4.3.3. Насколько быстро можно выполнять умножение Для умножения т-разрядного числа на п-разрядное традиционным методом (алгоритм 4.3.1М) требуется приблизительно стп операций, где с — константа.
Для простоты в этом разделе предположим, что т = и, и обсудим следующий вопрос: Дтя любого ли обычного вычислительного алгоритма умножения двух и-разрядных чисел время выполнения пропорционально п~ по мере увеличения п? (В этом вопросе под термином "обычный" понимается алгоритм, воспринимающий в качестве входа число п и два произвольных и-разрядных числа в позиционной интерпретации и на выходе дающий произведение этих чисел также в позиционной интерпретации. Безусловно, если бы можно было для каждого значения и выбрать свой алгоритм, вопрос не представлял бы интереса, так как для любого конкретного значения п умножение можно было бы выполнить, просто отыскав результат в некоторой огромной таблице. Под термином "вычислительный алгоритм« понимается алгоритм, пригодный для применения на цифровом компьютере, подобном И1Х, а время выполнения — это время, затраченное на таком компьютере на получение результата по такому алгоритму.) А.
Цифровые методы. Ответ на поставленный вопрос звучит довольно неожиданно — "Нет". И в самом деле, нетрудно понять, почему. Для удобства будем далее полагать, что мы оперируем числами, выраженными в двоичной системе счисления. Два 2п-битовых числа и = (иг„~... игио)г и е = (ег„г... егео)г можно записать в виде и = 2" Ь"г + Но, е = 2" Р'г + 1'о (1) где ог = (иг„ы .. и„)г — "наиболее значимая половина" числа и и Но — — (и„г... ио)г— "наименее значимая половина" числа и. Аналогично 1г — — (ег„г...е„)г и 1о = (еч-г... ео)г. Тогда ие = (2г" + 2")Ь'~Ъ1 + 2"(Ц вЂ” Ьо)(Ро — Ъг) + (2" + 1)УоК).
(2) Эта формула сводит задачу умножения 2п-битовых чисел к трем операциям умножения и-битовых чисел Ьг1ы (Гг — Уо)(1го — 'гг) и Ьо\~~ и выполнению некоторых простых операций сдвига и сложения. Формула (2) пригодна и для умножения чисел с удвоенной точностью, когда требуется получить результат с учетверенной точностью, На многих компьютерах это реализуется немного быстрее, чем умножение традиционными методами. Но главное преимущество формулы (2) заключается в том, что ее можно использовать для определения рекурсивного процесса умножения, который значительно быстрее при больших п уже знакомого метода, имеющего время выполнения порядка пг.
Если Т(п) -- время, затрачиваемое на выполнение умножения и-битовых чисел, то для некоторой константы с имеем (3) Т(2п) < ЗТ(п) + оп, так как в правой части формулы (2) требуется выполнить только три операции умножения плюс некоторые операции сдвига и сложения. Из соотношения (3) по индукции следует, что Т(2") < с(3" — 2"), Й > 1, (4) если выбрать константу с достаточно большой, чтобы данное неравенство выполня- лось при Й = 1; поэтому имеем Т(п) < Т(2рэ "1) < с(39э "1 — 2ро")) < Зс 3'э" = Зон~э~. (5) Из соотношении (5) видно, что время порядка пг, затрачиваемое на выполнение операции умножения, можно сократить до величины порядка и'ко - и'оэо, так что рекурсивный метод при больших и обеспечивает гораздо более высокую скорость, чем традиционный. В упр.
18 рассмотрено применение этого метода. (Похожий, но немного более шюжный метод умножения со временем выполнения порядка и'го был впервые предложен А. Карацубой в ДАН СССР 145 (1962), 293-294. Любопытно, что эта идея, по-видимому, до 1962 года не была известна; нет сведений о том, чтобы кто-нибудь из "вундеркиндов-счетчиков", прославившихся своими способностями умножать в уме большие числа, применял когда-либо подобный метод, хотя аналог формулы (2) для десятичной системы счисления, казалось бы, дает довольно легкий способ умножения в уме восьмизначных чисел.) В пределе при и, стремящемся к бесконечности, время выполнения можно сократить еще больше, если учесть, что рассмотренный только что метод является частным случаем т = 1 более общего метода, который для произвольного фиксированного г дает Т((г + 1)п) < (2г + 1)Т(п) + сп.
(6) Этот более общий метод можно получить следуюшим образом. Разобьем «е = (е1„+2)„— г...шее)2 и = (и<„+21„2...м~пе)2 на г + 1 частей и = (7„2'" + ° + 01 2" + Уе, с = К.2'" + + ~'~2" + ~о, (7) где каждое Уу и каждое Ъу является и-битовым числом. Рассмотрим полиномы У(х) = У,х' + ° + 02х + Уе, И(х) = К.х" + .. + Ъ1 х + )ге (8) и положим И' (х) = Цх)Ъ (х) = И2„х + + И1х + ИО.
(9) Так как и = У(2") и е = И(2"), получаем ии = Иг(2"), поэтому при известных коэффициентах Игь в И'(х) можно легко вычислить ис. Задача заключается в поиске хорошего способа вычисления этих коэффициентов в Иг(х), требующем только 2г+ 1 умножений п-битовых чисел и несколько последующих операций, время выполнения которых пропорционально и. Эта может быть достигнуто посредством вычисления У(0)Ъ'(0) = И'(О), У(1)Ъ'(1) = И'(1), ..., П(2г)И(2г) = И'(2г). (10) Теорема А. Для любого е > 0 существуют хакан постояннан с(е) н такой алгоритм умноження, что число элементарных операций Т(п), которые необходимо выпол- нять, чтобы перемножить два и-бнтовых числа, удовлетворяет оценке Т(п) < с(е)п' '.
1 Данная теорема — это еще не тот результат, который нам нужен. Для практических целей он неудовлетворителен, так квк метод резко усложняется, когда е -э 0 (т. е. г — ~ оо). Это приводит к столь быстрому росту с(е), что приходится иметь дело с очень большими значениями и прежде, чем будут внесены какие- либо существенные улучшения в соотношение (5). Теорема неудовлетворительна и с Коэффициенты полинома степени 2г могут быть выражены в виде линейной комбинации значений этого палинома в 2г+ 1 различных точках. Время, необходимое для выполнения этой операции, пропорционально и или меньше.
(В действительности произведения У(1))г(у) не являются в строгом смысле произведениями и-битовых чисел, но являются произведениями (и+с)-битовых чисел, где г есть фиксированное значение, зависящее от г. Программа умножения (и+1)-битовых чисел строится легко. Для ее выполнения требуется лишь Т(п) + с2п операций, где Т(п) -- количество операций, необходимых для умножения и разрядов, так как при фиксированном 1 два произведения г- и и-битовых чисел можно получить за стп операций.) Таким образом, получаем метод умножения, для которого выполняется неравенство (6). Рассуждая так же, как при выводе неравенства (5), и учитывая неравенство (6), приходим к неравенству Т(п) < сэпмэ"+К2"'"0 < сзп'+"вью 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
