1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 61
Текст из файла (страница 61)
е. точное значение и11. С) Теорема 7.8. Алгоритм 7.3 тратит Ов (л1оя л!Оя 1оя и) времении. Д о к а з а т е л ь с т в о. В силу следствия теоремы 7.6 шаги 1 — 3 выполняются за время Оз[Ы 1оя Ь+ЬМ(21)), где М(т)— 307 гл. т. БыстРОИ пРВОБРА3ОВАнии ФРРЬЕ время умножения двух т-разрядных двоичных целых чисел путем рекурсивного применения этого алгоритма. На шаге 4 формируются и умножаются числа й и б длины ЗЬ!Оя Ь за Ов [(ЗЬ )оя Ь)' м) шагов.
Так как (ЗЫоя Ь)'"~Ь' для достаточно большого Ь, то временем, затрачиваемым на шаг 4, можно пренебречь, нбо шаги 1 и 3 занимают ОБ (Ь' )оя Ь) времени. Шаги 5 и б занимают оба 0(а) времени, так что и ими можно пренебречь. Поскольку и=М и Ь«)/а, то М (п) (сп!Ояи+ЬМ (2!) (7.9) для некоторой постоянной с и достаточно больших п. Пусть М' (п) = =М(п)!и. Тогда (7.9) можно записать в виде М' (п) ~ (с )оя а+ 2М' (2!). (7.10) Поскольку ! =2 3/й, то М' (п) ~ с !оя п+ 2М' (4Рсй), (7.11) откуда следует, что М'(и~с')од п )оц )оя а при подходящем выборе постоянной с'. Чтобы убедиться в этом, подставим в (7.11) с')од(4 )~й) )оя !Ой (4 У'й) вместо М'(4 Уи). Очевидные преобразования дадут неравенство М' (п) ( с ) они+ 4с' !оя (2 + — )оя п) + с'! Оя п )оя (2 + — )оя п ) . Для больших а выполняется 2+'(,!Оя и~*1, )оя п, и потому М' (и) ..
с)они+ 4с' )ое — + 4с' )оя )оя п+ +с !оя — )они+с )ояи )оя)ояп. (7.12) Для больших п и для достаточно большой постоянной с' первые три слагаемых не больше абсолютной величины четвертого, а оио отрицательно. Таким образом, М' (и)~с')оя и )оя )оя п. Отсюда заключаем, что М (п)(с' п )оя и )оя )оя п. ):) УПРАЖНЕНИЯ 7.1. Чему равны примитивные корни а-й степени из единицы в кольце комплексных чисел при п=З, 4, 57 7.2. Покажите, как реализовать алгоритм 7.2 без временного массива 5.
7.3. Вычислите дискретное преобразование Фурье следукхцих последовательностей в кольце комплексных чисел: (а) [О, 1, 2, 3[, (б) П, 2, О, 2, О, О, О, 1]. зва УПРАЖНЕНИЯ 7.4. Обобщите алгоритм быстрого преобразования Фурье иа случай, когда л не является степенью числа 2. Определение. Тройка целых чисел (в, л, т) называется допусти- мой, если в и л имеют обратные и в — примитивный корень л-й степени из единицы в кольце целых чисел по модулю т. 7.5.
Какие из следующих троек допустимы? (а) (3, 4, 5), (б) (2, 6, 21), (в) (2, 6, 7). 7.6. Покажите, что если (в, л, т) — допустимая тройка, то в"=1 (шоб т) и вРФ1, если 1<р«л. "7.7. Покажите, что если л — степень числа 2, 2'*= — 1(шод т) и числа 2Р— 1 и т взаимно просты при 1 =р~л, то (2, л, т) — допу- стимая тройка. **7.8. Покажите, что если т — простое число, а в — произволь- ное положительное целое число, то найдется такое число л, что (в, л, т) — допустимая тройка.
7.9. Покажите, что если а и Ь взаимно просты, то ас 1 (шоб Ь) для некоторого числа с, и обратно. Докажите, что с по модулю Ь единственно. 7.10. Найдите (10101110011110), по модулю 2'+1. 7.11. Пусть ! — целое число, заданное своим десятичным пред- ставлением. Покажите, что если сложить все цифры числа 1, затем сложить все цифры результата и т. д. до тех пор, пока не останется одна цифра; то в конце концов получится ! по модулю 9.
7.12. С помощью теоремы о свертке вычислите свертку последо- вательностей П, 2. 3, 4! и [4, 3, 2, 1[ по модулю 17, используя допу- стимую тройку (2, 8, 17). 7.13. Вычислите по алгоритму 7.3 произведение двоичных чисел (1011011), и (10001111),. 7.14. Покажите, что в результате извлечения квадратного нория из л 2АА получится 1ок 1ой л раз число 2. *"7.15. Разработайте алгоритм быстрого умножения целых чисел на основе свертки, а не обернутой свертки. Каково асимптотиче- ское время работы вашего алгоритма? ь7.16, Циклической разностью Ла вектора а=[а„а„..., а„,)г называется вектор [а,— а„„а,— а„а,— а„..., а„,— а„,р. Пусть р(а) =!а'„а'„..., о„',!г, Покажите, что с (Ла) =[О, а,'(1 — в), а', (1 — в'),..., а„',(1 — в"-1)], где в — соответствующий корень л-й степени из единицы.
7,!7. С помощью упр. 7.16 покажите, что из Х(л) — Х(л — 1)=л и Х(0)=0 следует Х(п)=л(п+1)/2. Заа Гл. т. БыстРОе пРеОБРАЗОВАНИБ ФуРье *7.18. Циркулянтом называется матрица, в которой каждая строка получается нз строки, стоящей над ней, циклическим сдвигом на одну позицию вправо. Например, матрица Е1 есть (Зх 3)-цнркулянт. Покажнте, что вычисление дискретного преобразования Фурье л-мерного вектора, где а — простое число, зквнвалентно умножению на ((а — 1) х (л — 1))-цнркулянт.
е*7.19. Покажите, что преобразование Фурье над конечным полем для простого числа и можно вычислить за Ое (а!Оя а) шагов. *7.26. Рассмотрите представление полннома значениями всех его производных в некоторой точке. Линейно лн преобразование коэффициентов полннома в значения его пронзводныхр *"7.21. Дайте "физическое" объяснение обернутой свертки в терминах операций над полнномамн.
*7.22. Используйте БПФ для построения алгоритма сложности 0(н [опл), который умножал бы теплнцеву матрицу на вектор. Сравните ваш алгоритм с решеннем упр. 6.26(б). Проблема для исследования 7.23. Найдите более быстрые алгоритмы умножения целых чнсел н дискретного преобразования Фурье. Илн, наоборот, покажите, что алгоритм Шйнхаге — Штрассена нлн БПФ вЂ” наилучший нз возможных прн некоторых ограничениях на модель вычислений. Развивая идеи Кука, Аандераа [1969), Патерсон, Фишер, Мейер [1974[ показали, что прн определенных ограничениях битовое умножение целых чисел требует ОБ((а [оп я)/([оя!Ока)) шагов.
Аналогично Моргенштерн [19731 показал, что прн определенных ограннченнях дискретное преобразование Фурье требует ОА(л [оя л) шагов. Замечания по лмтературе Кули, Льюис, Уелч [1967! указывают, что способ быстрого преобразования Фурье описан еше в книге Рунге, Кеннга [19241. Его прнменялн Даннелсон, Ланцош [1942) н Гуд [1968, 1960). В фундаментальной работе Кули, Тьюкн [1965) проясняется природа етого метода. Николсон [1971) дал алгебранческое опнсанне для него.
Трактовка БГ[Ф как задачи деления полнномов, принятая немн, прннадлежнт Фндуччна 119721. Ввиду важности иого алгорнтма для вычнсленнй много вннманнн уделялось его зффектнвной реалнзацнн (см., напрнмер, работу Джентльмене, Санде [1966) н многочнсленные статья в сбор. нике под редакцней Рабннера, Рейдера [19721). Алгорнтм умножения целых чисел разработан Шенхаге, Штрассеном [1971). Упр. 7.18 н 7.19 взяты у Рейдера [19681. 249 АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ в НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ Арифметические операции над целыми числами и полнномами целесообразно изучать вместе потому, что многие алгоритмы, работающие с целыми числами, по существу совпадают с алгоритмами, работающими с полиномами от одной переменной.
Это верно не только для таких операций, как умножение и деление, но также и для более сложно описываемых операций. Например, нахождение вычета целого числа по модулю, задаваемому другим целым числом, эквивалентно вычислению полинома в точке. Представление целого числа его вычетами эквивалентно представлению полинома его значениями в нескольких точках.
Восстановление целого числа по его вычетам (" китайская теорема об остатках") эквивалентно интерполированию полинома. В этой главе мы покажем, что для некоторых операций над целыми числами и полиномами, таких, как деление и возведение в квадрат, требуется время того же порядка, что и для умножения. Время выполнения других операций, таких, как упомянутые выше операции с вычетами или вычисление наибольших общих делителей, может превосходить время умножения не более чем в (оя п раз, где п — длина двоичного представления целого числа или степень полннома. Наша стратегия будет состоять в том, чтобы чередовать результаты для целых чисел с соответствующими результатами для полиномов, причем обычно мы будем доказывать зти результаты только для чего-то одного, а доказательство для другого будем оставлять в качестве упражнения.
Как и в остальных главах, основное внимание будет уделяться алгоритмам, асимптотически наиболее эффективным среди известных. В конце главы кратко обсудим различие между моделью полиномои, в которой предполагается, что большинство коэффициентов отличны от нуля (плотная модель), и моделью, где большинство коэффициентов равны нулю (разреженная модель). Разреженная модель особенно полезна в случае полнномов от многих переменных (этот случай мы не рассматриваем).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
