الگوریتم‌ها برای برنامه‌نویسان: ایده‌ها و کد منبع

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