Algorithms for programmers. Ideas and source code

Algorithms for Programmers......Page 1
Contents......Page 2
Some Important Remarks......Page 7
List of Important Symbols......Page 8
1.1 Discrete Fourier Transform......Page 9
1.2 Symmetries of Fourier transform......Page 10
1.3.2 Decimation in time (DIT) FFT......Page 11
1.3.3 Decimation in frequency (DIF) FFT......Page 14
1.4 Saving Trigonometric Computations......Page 16
1.4.2 Recursive generation of the sin=cos-values......Page 17
1.5.2 Decimation in time......Page 18
1.5.3 Decimation in frequency......Page 19
1.5.4 Implementation of radix r = px DIF/DIT FFTs......Page 20
1.6 Split Radix Fourier Transforms (SRFT)......Page 23
1.7 Inverse FFT for Free......Page 24
1.8 Real Valued Fourier Transforms......Page 25
1.8.1 Real valued FT via wrapper routines......Page 26
1.8.2 Real valued split radix Fourier transforms......Page 28
1.9.2 The row column algorithm......Page 32
1.10 Matrix Fourier Algorithm (MFA)......Page 33
1.11 Automatic Generation of FFT Codes......Page 34
2.1 Definition & Computation via FFT......Page 37
2.2 Mass Storage Convolution using MFA......Page 41
2.3 Weighted Fourier Transforms......Page 43
2.5 Convolution using MFA......Page 45
2.5.2 The case R = 3......Page 46
2.7 Convolution without Transposition using MFA......Page 47
2.8.1 Definition of the ZT......Page 48
2.8.4 Fractional Fourier transform by ZT......Page 49
3.2.1 Decimation in time (DIT) FHT......Page 50
3.2.2 Decimation in frequency (DIF) FHT......Page 53
3.3 Complex FT by HT......Page 56
3.4 Complex FT by Complex HT & Vice Versa......Page 57
3.5 Real FT by HT & Vice Versa......Page 58
3.6 Discrete Cosine Transform (DCT) by HT......Page 59
3.7 Discrete Sine Transform (DST) by DCT......Page 60
3.8 Convolution via FHT......Page 61
3.9 Negacyclic Convolution via FHT......Page 63
4.1 Prime Modulus: Z/pZ = Fp......Page 64
4.2 Composite Modulus: Z/mZ......Page 65
4.3.1 Radix 2 DIT NTT......Page 68
4.3.2 Radix 2 DIF NTT......Page 69
4.5 Chinese Remainder Theorem (CRT)......Page 70
4.6 A Modular Multiplication Technique......Page 72
4.7 Number-Theoretic Hartley Transform......Page 73
Ch5 Walsh Transforms......Page 74
5.1 Basis Functions of Walsh Transforms......Page 78
5.2 Dyadic Convolution......Page 79
5.3 Slant transform......Page 81
Ch6 Haar transform......Page 83
6.1 In-Place Haar Transform......Page 84
6.2 Integer to Integer Haar Transform......Page 87
7.1 Trivia......Page 89
7.2 Operations on Low Bits/Blocks in a Word......Page 90
7.3 Operations on High Bits/Blocks in a Word......Page 92
7.4 Functions Related to Base-2 Logarithm......Page 95
7.5 Counting Bits in a Word......Page 96
7.6 Swapping Bits/Blocks of a Word......Page 97
7.7 Reversing Bits of a Word......Page 99
7.8 Generating Bit Combinations......Page 100
7.10 Bit Set Lookup......Page 102
7.11 Gray Code of a Word......Page 103
7.12 Generating Minimal-Change Bit Combinations......Page 105
7.13 Bitwise Rotation of a Word......Page 107
7.14 Bitwise Zip......Page 109
7.15 Bit Sequency......Page 110
7.16 Misc......Page 111
7.17 Bitarray Class......Page 113
7.18 Manipulation of Colors......Page 114
8.1.1 A naive version......Page 116
8.1.3 How many swaps?......Page 117
8.1.4 A still faster version......Page 118
8.1.5 The real world version......Page 120
8.2 Radix Permutation......Page 121
8.3 In-Place Matrix Transposition......Page 122
8.4.1 Rotate and reverse......Page 123
8.4.2 Zip and unzip......Page 124
8.5 Gray Code Permutation......Page 125
8.6.1 Basic definitions......Page 128
8.6.2 Compositions of permutations......Page 129
8.6.3 Applying permutations to data......Page 132
8.7.1 Lexicographic order......Page 133
8.7.2 Minimal-change order......Page 135
8.7.3 Derangement order......Page 137
8.7.4 Star-transposition order......Page 138
8.7.5 Yet another order......Page 139
9.1 Sorting......Page 141
9.2 Searching......Page 143
9.3 Index Sorting......Page 144
9.4 Pointer Sorting......Page 145
9.5 Sorting by Supplied Comparison Function......Page 146
9.6 Unique......Page 147
9.7 Misc......Page 149
10.1 Offline Functions: funcemu......Page 153
10.2 Combinations in Lexicographic Order......Page 156
10.3 Combinations in Co-Lexicographic Order......Page 158
10.4 Combinations in Minimal-Change Order......Page 159
10.5 Combinations in Alternative Minimal-Change Order......Page 161
10.6 Subsets in Lexicographic Order......Page 162
10.7 Subsets in Minimal-Change Order......Page 164
10.8 Subsets Ordered by Number of Elements......Page 166
10.9 Subsets Ordered with Shift Register Sequences......Page 167
10.10 Partitions......Page 168
11.2 Multiplication of Large Numbers......Page 171
11.2.2 Fast Multiplication via FFT......Page 172
11.2.3 Radix/Precision Considerations with FFT Multiplication......Page 174
11.3.1 Division......Page 175
11.3.2 Square root extraction......Page 176
11.4 Square Root Extraction for Rationals......Page 177
11.5 General Procedure for Inverse n-th Root......Page 179
11.6 Re-Orthogonalization of Matrices......Page 181
11.7 n-th Root by Goldschmidt's Algorithm......Page 182
11.8 Iterations for Inversion of Function......Page 183
11.8.1 Householder's formula......Page 184
11.8.2 Schroeder's formula......Page 185
11.8.3 Dealing with multiple roots......Page 186
11.8.4 A general scheme......Page 187
11.8.5 Improvements by the delta squared process......Page 189
11.9.1 AGM......Page 190
11.9.2 log......Page 192
11.9.3 exp......Page 193
11.9.6 Elliptic E......Page 194
11.10 Computation of pi/log(q)......Page 195
11.11 Iterations for High Precison Computations of pi......Page 196
11.12 Binary Splitting Algorithm for Rational Series......Page 201
11.13 Magic Sumalt Algorithm......Page 203
11.14 Continued Fractions......Page 205
App A Summary of Definitions of FTs......Page 207
AppB Pseudo Language Sprache......Page 209
AppC Optimization Considerations for Fast Transforms......Page 212
AppD Properties of ZT......Page 213
AppE Eigenvectors of Fourier Transform......Page 215
Bibliography......Page 216
Index......Page 219