Главная Промышленная автоматика.

время умножения двух т-разрядных двоичных целых чисел путем рекурсивного применения этого алгоритма. На шаге 4 формируются и умножаются числа йк€ длины ЗЬ log b за об 1(ЗЬ og шагов. Так как (Sfelog для достаточно большого Ь, то

временем, затрачиваемым на шаг 4, можно пренебречь, ибо шаги 1 и 3 занимают об (ь* log b) времени. Шаги 5 и 6 занимают оба 0(п) времени, так что и ими можно пренебречь. Поскольку n-bl и bVn, то

М (п) СП log п + ЬМ (21) (7.9)

для некоторой постоянной с и достаточно больших п. Пусть М (п)= =М(п)/п. Тогда (7.9) можно записать в виде

M{n)clogn + 2M{2l). (7.10)

Поскольку /<2 Уп, то

M(nXclogn + 2M(4/n), (7.11)

откуда следует, что AI(nXclog п log log n при подходящем выборе постоянной с. Чтобы убедиться в этом, подставим в (7.11) clog(4 Уп) log log (4 Уп) вместо М(4 УЯ). Очевидные преобразования дадут неравенство

M(n)<clogn + 4c log (2+1 logn) + сlogn log (2-fi-logn). Для больших n выполняется 2-fi/, log п<*/, log n, и потому М (n) < с logn -f 4c log 3- -f 4c log log n +

-f c log "i log n + c log n log log n. (7.12)

Для больших n и для достаточно большой постоянной с первые три слагаемых не больше абсолютной величины четвертого, а оно отрицательно. Таким образом, М (nXclog п log log п. Отсюда заключаем, что М (п)с п log п log log п. □

УПРАЖНЕНИЯ

7.1. Чему равны примитивные корни п-й степени из единицы в кольце комплексных чисел при п=3, 4, 5?

7.2. Покажите, как реализовать алгоритм 7.2 без временного массива S.

7.3. Вычислите дискретное преобразование Фурье следующих последовательностей в кольце комплексных чисел:

(а) [О, 1, 2, 3],

(б) [1, 2, О, 2, О, О, О, 1].



УПРАЖНЕНИЯ

7.4. Обобщите алгоритм быстрого преобразования Фурье на случай, когда п не является степенью числа 2.

Определение. Тройка целых чисел (со, п, т) называется допустимой, если (О и п имеют обратные и (о - примитивный корень п-й степени из единицы в кольце целых чисел по модулю т.

7.5. Какие из следующих троек допустимы? (а) (3, 4, 5), (б) (2, 6, 21), (в) (2, 6, 7).

7.6. Покажите, что если (ю, п, т) - допустимая тройка, то а"=1 (mod т) и (о1, если 1<р<п.

*7.7. Покажите, что если п - степень числа 2, 2"=1 (mod т) и числа 2-1 и т взаимно просты при 1<р<п, то (2, п, т) - допустимая тройка.

**7.8. Покажите, что если т - простое число, а (о - произвольное положительное целое число, то найдется такое число п, что ((О, п, т) - допустимая тройка.

*7.9. Покажите, что если а и b взаимно просты, то ас=1 (mod b) для некоторого числа с, и обратно. Докажите, что с по модулю b единственно.

7.10. Найдите (10101110011110), по модулю 2+1.

7.11. Пусть t - целое число, заданное своим десятичным представлением. Покажите, что если сложить все цифры числа t, затем сложить все цифры результата и т. д. до тех пор, пока не останется одна цифра,- то в конце концов получится t по модулю 9.

7.12. С помощью теоремы о свертке вычислите свертку последовательностей [1, 2, 3, 4] и [4, 3, 2, 1] по модулю 17, используя допустимую тройку (2, 8, 17).

7.13. Вычислите по алгоритму 7.3 произведение двоичных чисел (1011011), и (10001111),.

7.14. Покажите, что в результате извлечения квадратного корня из п=2* получится log log n раз число 2.

**7.15. Разработайте алгоритм быстрого умножения целых чисел на основе свертки, а не обернутой свертки. Каково асимптотическое время работы вашего алгоритма?

*7.16. Циклической разностью Ла вектора а=[ао, Oi, • • •, fln-J" называется вектор [оо-On-i, «1-Оо, аз-ах, . . ., fln.,]". Пусть

Fia) = [al а[, a; if.

Покажите, что /=(Да) = [0, а{{\-а,), • • •. ««-1(1-w"-)l,

где (О - соответствующий корень п-й степени из единицы. **7.17. С помощью упр. 7.16 покажите, что из Х{п)-К{п-1)=п и Х(0)=0 следует X(n)=n(n+l)/2.



*7.18. Циркулянтом называется матрица, в которой каждая строка получается из строки, стоящей над ней, циклическим сдвигом на одну позицию вправо. Например, матрица

~а b с"

b с а

есть (ЗхЗ)-циркулянт. Покажите, что вычисление дискретного преобразования Фурье п-мерного вектора, где п - простое число, эквивалентно умножению на ((п-1)Х (п-1))-циркулянт.

**7.19. Покажите, что преобразование Фурье над конечным полем для простого числа п можно вычислить за О а (п log п) шагов.

*7.20. Рассмотрите представление полинома значениями всех его производных в некоторой точке. Линейно ли преобразование коэффициентов полинома в значения его производных?

**7.21. Дайте "физическое" объяснение обернутой свертки в терминах операций над полиномами.

*7.22. Используйте БПФ для построения алгоритма сложности О(п logn), который умножал бы тёплицеву матрицу на вектор. Сравните ваш алгоритм с решением упр. 6.26(6).

Проблема для исследования

7.23. Найдите более быстрые алгоритмы умножения целых чисел и дискретного преобразования Фурье. Или, наоборот, покажите, что алгоритм Шёнхаге - Штрассена или БПФ - наилучший из возможных при некоторых ограничениях на модель вычислений. Развивая идеи Кука, Аандераа [1969], Патерсон, Фишер, Мейер [1974] показали, что при определенных ограничениях битовое умножение целых чисел требует Об ((п log n)/(log log n)) шагов. Аналогично Моргенштерн [1973] показал, что при определенных ограничениях дискретное преобразование Фурье требует О а (п log п) шагов.

Замечания по литературе

Кули, Льюис, Уелч [1967] указывают, что способ быстрого преобразования Фурье омсан еще в книге Руиге, Кёнига [1924]. Его применяли Даниелсон, Ланцош [1942] и Гуд [1958, I960]. В фундаментальной работе Кули, Тьюки [1965] проясняется природа этого метода. Николсон [1971] дал алгебраическое описание для него. Трактовка БПФ как задачи деления полиномов, принятая нами, принадлежит Фидуччиа [1972]. Ввиду важности этого алгоритма для вычислений много внимания уделялось его эффективной реализации (см., например, работу Джентльмена, Санде [1966] и многочисленные статьи в сборнике под редакцией Рабинера, Рейдера 1972]). Алгоритм умножения целых чисел разработан Шёнхаге, Штрассеном [197Г Рейдера [1968].

Упр. 7.18 и 7.19 взяты у





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 [99] 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0054