Algorithms for programmers - ideas and source code

rained

觉得还不错得算法书籍,推荐给大家.




1 The Fourier transform 8
1.1 The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.3 Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Saving trigonometric computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.2 Recursive generation of the sin=cos-values . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Higher radix DIT and DIF algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1 More notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Decimation in time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.3 Decimation in frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.4 Implementation of radix r = px DIF/DIT FFTs . . . . . . . . . . . . . . . . . . . . 19
1.6 Split radix Fourier transforms (SRFT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 Inverse FFT for free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.8 Real valued Fourier transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8.1 Real valued FT via wrapper routines . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.8.2 Real valued split radix Fourier transforms . . . . . . . . . . . . . . . . . . . . . . . 27
1.9 Multidimensional FTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.9.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.9.2 The row column algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.10 The matrix Fourier algorithm (MFA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.11 Automatic generation of FFT codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1
CONTENTS 2
2 Convolutions 36
2.1 Definition and computation via FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2 Mass storage convolution using the MFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 Weighted Fourier transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4 Half cyclic convolution for half the price ? . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5 Convolution using the MFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.1 The case R = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.2 The case R = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.6 Convolution of real valued data using the MFA . . . . . . . . . . . . . . . . . . . . . . . . 46
2.7 Convolution without transposition using the MFA . . . . . . . . . . . . . . . . . . . . . . 46
2.8 The z-transform (ZT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.8.1 Definition of the ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.8.2 Computation of the ZT via convolution . . . . . . . . . . . . . . . . . . . . . . . . 48
2.8.3 Arbitrary length FFT by ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.8.4 Fractional Fourier transform by ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 The Hartley transform (HT) 49
3.1 Definition of the HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 radix 2 FHT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.1 Decimation in time (DIT) FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Decimation in frequency (DIF) FHT . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3 Complex FT by HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4 Complex FT by complex HT and vice versa . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5 Real FT by HT and vice versa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.6 Discrete cosine transform (DCT) by HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.7 Discrete sine transform (DST) by DCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.8 Convolution via FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.9 Negacyclic convolution via FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4 Numbertheoretic transforms (NTTs) 63
4.1 Prime modulus: Z=pZ = Fp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Composite modulus: Z=mZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Pseudocode for NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.1 Radix 2 DIT NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.2 Radix 2 DIF NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Convolution with NTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.5 The Chinese Remainder Theorem (CRT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6 A modular multiplication technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.7 Numbertheoretic Hartley transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Walsh transforms 73
CONTENTS 3
5.1 Basis functions of the Walsh transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Dyadic convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3 The slant transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6 The Haar transform 82
6.1 Inplace Haar transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Integer to integer Haar transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7 Some bit wizardry 88
7.1 Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.2 Operations on low bits/blocks in a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.3 Operations on high bits/blocks in a word . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.4 Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.5 Counting the bits in a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.6 Swapping bits/blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.7 Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.8 Generating bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.9 Generating bit subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.10 Bit set lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.11 The Gray code of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.12 Generating minimal-change bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.13 Bitwise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.14 Bitwise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.15 Bit sequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.16 Misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.17 The bitarray class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.18 Manipulation of colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8 Permutations 115
8.1 The revbin permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.1.1 A naive version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.1.2 A fast version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.1.3 How many swaps? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.1.4 A still faster version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.1.5 The real world version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.2 The radix permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.3 Inplace matrix transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.4 Revbin permutation vs. transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.4.1 Rotate and reverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.4.2 Zip and unzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.5 The Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
CONTENTS 4
8.6 General permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8.6.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8.6.2 Compositions of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8.6.3 Applying permutations to data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.7 Generating all Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.7.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.7.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.7.3 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.7.4 Star-transposition order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.7.5 Yet another order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9 Sorting and searching 140
9.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.3 Index sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.4 Pointer sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.5 Sorting by a supplied comparison function . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.6 Unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.7 Misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
10 Selected combinatorical algorithms 152
10.1 Offline functions: funcemu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.2 Combinations in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.3 Combinations in co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
10.4 Combinations in minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
10.5 Combinations in alternative minimal-change order . . . . . . . . . . . . . . . . . . . . . . 160
10.6 Subsets in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
10.7 Subsets in minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
10.8 Subsets ordered by number of elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.9 Subsets ordered with shift register sequences . . . . . . . . . . . . . . . . . . . . . . . . . 166
10.10Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
11 Arithmetical algorithms 170
11.1 Asymptotics of algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
11.2 Multiplication of large numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
11.2.1 The Karatsuba algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.2.2 Fast multiplication via FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.2.3 Radix/precision considerations with FFT multiplication . . . . . . . . . . . . . . . 173
11.3 Division, square root and cube root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
11.3.1 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
11.3.2 Square root extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
CONTENTS 5
11.3.3 Cube root extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
11.4 Square root extraction for rationals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
11.5 A general procedure for the inverse n-th root . . . . . . . . . . . . . . . . . . . . . . . . . 178
11.6 Re-orthogonalization of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
11.7 n-th root by Goldschmidt’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
11.8 Iterations for the inversion of a function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
11.8.1 Householder’s formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
11.8.2 Schr¨oder’s formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
11.8.3 Dealing with multiple roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.8.4 A general scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
11.8.5 Improvements by the delta squared process . . . . . . . . . . . . . . . . . . . . . . 188
11.9 Trancendental functions & the AGM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.9.1 The AGM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.9.2 log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.9.3 exp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.9.4 sin, cos, tan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.9.5 Elliptic K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.9.6 Elliptic E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.10Computation of ¼= log(q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
11.11Iterations for high precison computations of ¼ . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.12The binary splitting algorithm for rational series . . . . . . . . . . . . . . . . . . . . . . . 200
11.13The magic sumalt algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
11.14Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
A Summary of definitions of FTs 206
B The pseudo language Sprache 208
C Optimisation considerations for fast transforms 211
D Properties of the ZT 212
E Eigenvectors of the Fourier transform 214

tmdted

thanks

CheerKwah

Thank for sharing

waforget

Thank you very much!!

fingjjjjjj

xia look

ericxgj

:victory: :victory: :victory: :victory: :victory:

lixqing

Thanks.

ic_qiand

确实是一本好书，但是coding可能要大规模的设计才能用到，初学者就表看了！

数学模型挺多的！

ritel

thanks a lot

songshu123

好书，谢谢分享！