Arndt - Algorithms for Programmers

PDF-файл Arndt - Algorithms for Programmers Численные методы (754): Книга - 6 семестрArndt - Algorithms for Programmers: Численные методы - PDF (754) - СтудИзба2013-09-152013-09-15zzyxelСтудИзба

Arndt - Algorithms for Programmers1208

Описание файла

PDF-файл из архива "Arndt - Algorithms for Programmers", который расположен в категории "". Всё это находится в предмете "численные методы" из 6 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "численные методы и алгоритмы" в общих файлах.

Просмотр PDF-файла онлайн

Текст из PDF

Algorithms for programmersideas and source codeThis document is work in progress: read the ”important remarks” near the beginningJörg Arndtarndt@jjj.deThis document1 was LATEX’d at March 26, 20031This document is online athttp://www.jjj.de/fxt/.It will stay available online for free.ContentsSome important remarks about this document1 The Fourier transform8101.1The discrete Fourier transform . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101.2Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111.3Summary of definitions of Fourier transforms * . . . . . . . . . . . . . . .

. . . . . . . . .121.4Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.4.1A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.4.2Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .141.4.3Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . .17Saving trigonometric computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191.5.1Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .191.5.2Recursive generation of the sin/cos-values . . . . . . . . . . . . . . . . . . . . . . .191.5.3Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20Higher radix DIT and DIF algorithms . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .201.6.1More notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .201.6.2Decimation in time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.6.3Decimation in frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.51.61.6.4xImplementation of radix r = p DIF/DIT FFTs . . .

. . . . . . . . . . . . . . . . .221.7Split radix Fourier transforms (SRFT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .251.8Inverse FFT for free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271.9Real valued Fourier transforms . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .281.9.1Real valued FT via wrapper routines . . . . . . . . . . . . . . . . . . . . . . . . . .291.9.2Real valued split radix Fourier transforms . . . . . . . . . . . . . . . . . . . . . . .311.10 Multidimensional FTs . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .341.10.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .341.10.2 The row column algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .351.11 The matrix Fourier algorithm (MFA) . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .351.12 Automatic generation of FFT codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .361.13 Optimization considerations for fast transforms . . . . . . . . . . . . . . . . . . . . . . . .391.14 Eigenvectors of the Fourier transform * . . . . . . . . . .

. . . . . . . . . . . . . . . . . .401CONTENTS22 Convolutions412.1Definition and computation via FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .412.2Mass storage convolution using the MFA . . . . . . . . . . . . . . . . . . . . . . . . . . . .462.3Weighted Fourier transforms. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .472.4Half cyclic convolution for half the price? . . . . . . . . . . . . . . . . . . . . . . . . . . .492.5Convolution using the MFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .502.5.1The case R = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .502.5.2The case R = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .512.6Convolution of real valued data using the MFA . . . . . . . . . . . . . . . . . . . . . . . .512.7Convolution without transposition using the MFA * . . . . . . . .

. . . . . . . . . . . . .512.8The z-transform (ZT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .532.8.1Definition of the ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .532.8.2Computation of the ZT via convolution . . . . . . . . . . .

. . . . . . . . . . . . .532.8.3Arbitrary length FFT by ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .542.8.4Fractional Fourier transform by ZT . . . . . . . . . . . . . . . . . . . . . . . . . . .543 The Hartley transform (HT)553.1Definition of the HT . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .553.2Radix 2 FHT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .553.2.1Decimation in time (DIT) FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .553.2.2Decimation in frequency (DIF) FHT . . . . . . . . .

. . . . . . . . . . . . . . . . .583.3Complex FT by HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .613.4Complex FT by complex HT and vice versa . . . . . . . . . . . . . . . . . . . . . . . . . .623.5Real FT by HT and vice versa . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .633.6Discrete cosine transform (DCT) by HT . . . . . . . . . . . . . . . . . . . . . . . . . . . .643.7Discrete sine transform (DST) by DCT . . . . . . . . . . . . . . . . . . . . . . . . . . . .653.8Convolution via FHT . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .663.9Negacyclic convolution via FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .684 Number theoretic transforms (NTTs)694.1Prime modulus: Z/pZ = Fp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694.2Composite modulus: Z/mZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. .704.3Pseudocode for NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734.3.1Radix 2 DIT NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734.3.2Radix 2 DIF NTT . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .744.3.3Radix 4 NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.4Convolution with NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .764.5The Chinese Remainder Theorem (CRT) . . . . . . . . . . . . . . . . . . . . .

. . . . . . .764.6A modular multiplication technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .784.7Number theoretic Hartley transform * . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79CONTENTS35 The Walsh transform and its relatives805.1The Walsh transform: Walsh-Kronecker basis .

. . . . . . . . . . . . . . . . . . . . . . . .805.2The Kronecker product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .825.3Computing the Walsh transform faster . . . . . . . . . . . . . . . . . . . . . . . . . . . . .845.4Dyadic convolution . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .865.5The Walsh transform: Walsh-Paley basis . . . . . . . . . . . . . . . . . . . . . . . . . . . .905.6Sequency ordered Walsh transforms. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .915.7The slant transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .975.8The Reed-Muller transform (RMT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .995.9The arithmetic transform . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026 The Haar transform1056.1In-place Haar transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066.2Non-normalized Haar transforms . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . 1096.3Transposed Haar transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116.4The reversed Haar transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.5Relations between Walsh- and Haar- transforms . . . . . .

. . . . . . . . . . . . . . . . . . 1156.66.5.1Walsh transforms from Haar transforms . . . . . . . . . . . . . . . . . . . . . . . . 1156.5.2Haar transforms from Walsh transforms . . . . . . . . . . . . . . . . . . . . . . . . 117Integer to integer Haar transform . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . 1187 Permutations7.1120The revbin permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1207.1.1A naive version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1207.1.2A fast version . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.1.3How many swaps? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1227.1.4A still faster version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1237.1.5The real world version .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1247.2The radix permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1267.3In-place matrix transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1277.4Revbin permutation vs. transposition . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . 1287.5The zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1297.6The reversed zip-permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1317.7The XOR permutation . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1327.8The Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1337.9The reversed Gray code permutation . . . . . . . . . . . . . . . . . . . . . .

Поделитесь ссылкой:

Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.

Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.

Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.

Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.