Algorithms for Programmers

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