Matters Computational: Ideas, Algorithms, Source Code

Cover......Page 1
Matters Computational: Ideas, Algorithms, Source Code......Page 4
9783642147630......Page 5
Preface......Page 6
Contents......Page 8
I Low level algorithms......Page 16
1.1 Trivia......Page 17
1.2 Operations on individual bits......Page 22
1.3 Operations on low bits or blocks of a word......Page 23
1.4 Extraction of ones, zeros, or blocks near transitions......Page 26
1.5 Computing the index of a single set bit......Page 28
1.6 Operations on high bits or blocks of a word......Page 29
1.7 Functions related to the base-2 logarithm......Page 32
1.8 Counting the bits and blocks of a word......Page 33
1.9 Words as bitsets......Page 38
1.11 Avoiding branches......Page 40
1.12 Bit-wise rotation of a word......Page 42
1.13 Binary necklaces......Page 44
1.14 Reversing the bits of a word......Page 48
1.15 Bit-wise zip......Page 53
1.16 Gray code and parity......Page 56
1.17 Bit sequency......Page 61
1.18 Powers of the Gray code......Page 63
1.19 Invertible transforms on words......Page 64
1.20 Scanning for zero bytes......Page 70
1.21 Inverse and square root modulo 2^n......Page 71
1.22 Radix -2 (minus two) representation......Page 73
1.23 A sparse signed binary representation......Page 76
1.24 Generating bit combinations......Page 77
1.25 Generating bit subsets of a given word......Page 83
1.26 Binary words in lexicographic order for subsets......Page 85
1.27 Fibonacci words......Page 89
1.28 Binary words and parentheses strings......Page 93
1.29 Permutations via primitives......Page 95
1.30 CPU instructions often missed......Page 97
1.31 Some space filling curves......Page 98
2.1 Basic de finitions and operations......Page 117
2.2 Representation as disjoint cycles......Page 119
2.3 Compositions of permutations......Page 120
2.4 In-place methods to apply permutations to data......Page 124
2.5 Random permutations......Page 126
2.6 The revbin permutation......Page 133
2.7 The radix permutation......Page 136
2.8 In-place matrix transposition......Page 137
2.9 Rotation by triple reversal......Page 138
2.10 The zip permutation......Page 140
2.11 The XOR permutation......Page 142
2.12 The Gray permutation......Page 143
2.13 The reversed Gray permutation......Page 146
3.1 Sorting algorithms......Page 149
3.2 Binary search......Page 156
3.3 Variants of sorting methods......Page 157
3.4 Searching in unsorted arrays......Page 162
3.5 Determination of equivalence classes......Page 163
4.1 Stack (LIFO)......Page 168
4.2 Ring buer......Page 170
4.3 Queue (FIFO)......Page 171
4.4 Deque (double-ended queue)......Page 173
4.5 Heap and priority queue......Page 175
4.6 Bit-array......Page 179
4.7 Left-right array......Page 181
II Combinatorial generation......Page 186
5.2 Ranking, unranking, and counting......Page 187
5.3 Characteristics of the algorithms......Page 188
5.5 Implementations, demo-programs, and timings......Page 189
6.1 Binomial coefficients......Page 191
6.2 Lexicographic and co-lexicographic order......Page 192
6.3 Order by pre fix shifts (cool-lex)......Page 195
6.4 Minimal-change order......Page 197
6.5 The Eades-McKay strong minimal-change order......Page 198
6.6 Two-close orderings via endo/enup moves......Page 201
6.7 Recursive generation of certain orderings......Page 206
7.1 Co-lexicographic order......Page 209
7.2 Co-lexicographic order for compositions into exactly k parts......Page 211
7.3 Compositions and combinations......Page 213
7.4 Minimal-change orders......Page 214
8.1 Lexicographic order......Page 217
8.2 Minimal-change order......Page 219
8.4 Shifts-order for subsets......Page 223
8.5 k-subsets where k lies in a given range......Page 225
9.1 Counting (lexicographic) order......Page 232
9.2 Minimal-change (Gray code) order......Page 235
9.3 gslex order......Page 239
9.4 endo order......Page 241
9.5 Gray code for endo order......Page 243
9.6 Fixed sum of digits......Page 244
10.1 Factorial representations of permutations......Page 247
10.2 Lexicographic order......Page 257
10.3 Co-lexicographic order......Page 258
10.4 An order from reversing pre fixes......Page 260
10.5 Minimal-change order (Heap's algorithm)......Page 263
10.6 Lipski's Minimal-change orders......Page 265
10.7 Strong minimal-change order (Trotter's algorithm)......Page 269
10.8 Star-transposition order......Page 272
10.9 Minimal-change orders from factorial numbers......Page 273
10.10 Derangement order......Page 279
10.11 Orders where the smallest element always moves right......Page 282
10.12 Single track orders......Page 286
11.1 The number of certain permutations......Page 292
11.2 Permutations with distance restrictions......Page 297
11.3 Self-inverse permutations (involutions)......Page 299
11.4 Cyclic permutations......Page 300
12 k-permutations......Page 306
12.1 Lexicographic order......Page 307
12.2 Minimal-change order......Page 308
13.1 Subsets of a multiset......Page 310
13.2 Permutations of a multiset......Page 311
14.1 List recursions......Page 319
14.2 Fibonacci words......Page 320
14.3 Generalized Fibonacci words......Page 322
14.4 Run-length limited (RLL) words......Page 325
14.5 Digit x followed by at least x zeros......Page 326
14.6 Generalized Pell words......Page 328
14.7 Sparse signed binary words......Page 330
14.8 Strings with no two consecutive nonzero digits......Page 332
14.9 Strings with no two consecutive zeros......Page 333
14.10 Binary strings without substrings 1x1 or 1xy1......Page 335
15.1 Co-lexicographic order......Page 338
15.2 Gray code via restricted growth strings......Page 340
15.3 Order by pre fix shifts (cool-lex)......Page 345
15.4 Catalan numbers......Page 346
15.5 Increment-i RGS, k-ary Dyck words, and k-ary trees......Page 348
16.1 Solution of a generalized problem......Page 354
16.2 Iterative algorithm......Page 356
16.3 Partitions into m parts......Page 357
16.4 The number of integer partitions......Page 359
17.1 Recursive generation......Page 369
17.2 The number of set partitions: Stirling set numbers and Bell numbers......Page 373
17.3 Restricted growth strings......Page 375
18 Necklaces and Lyndon words......Page 385
18.1 Generating all necklaces......Page 386
18.2 Lex-min De Bruijn sequence from necklaces......Page 392
18.3 The number of binary necklaces......Page 394
18.4 Sums of roots of unity that are zero......Page 398
19.1 Hadamard matrices via LFSR......Page 399
19.2 Hadamard matrices via conference matrices......Page 401
19.3 Conference matrices via finite fields......Page 403
20 Searching paths in directed graphs......Page 406
20.1 Representation of digraphs......Page 407
20.2 Searching full paths......Page 408
20.3 Conditional search......Page 413
20.4 Edge sorting and lucky paths......Page 417
20.5 Gray codes for Lyndon words......Page 418
III Fast transforms......Page 424
21.1 The discrete Fourier transform......Page 425
21.2 Radix-2 FFT algorithms......Page 426
21.3 Saving trigonometric computations......Page 431
21.4 Higher radix FFT algorithms......Page 433
21.5 Split-radix algorithm......Page 440
21.6 Symmetries of the Fourier transform......Page 443
21.7 Inverse FFT for free......Page 445
21.8 Real-valued Fourier transforms......Page 446
21.9 Multi-dimensional Fourier transforms......Page 452
21.10 The matrix Fourier algorithm (MFA)......Page 453
22.1 Convolution......Page 455
22.2 Correlation......Page 459
22.3 Correlation, convolution, and circulant matrices......Page 462
22.4 Weighted Fourier transforms and convolutions......Page 463
22.5 Convolution using the MFA......Page 466
22.6 The z-transform (ZT)......Page 469
22.7 Prime length FFTs......Page 472
23.1 Transform with Walsh-Kronecker basis......Page 474
23.2 Eigenvectors of the Walsh transform......Page 476
23.3 The Kronecker product......Page 477
23.4 Higher radix Walsh transforms......Page 480
23.5 Localized Walsh transforms......Page 483
23.6 Transform with Walsh-Paley basis......Page 488
23.7 Sequency-ordered Walsh transforms......Page 489
23.8 XOR (dyadic) convolution......Page 496
23.9 Slant transform......Page 497
23.10 Arithmetic transform......Page 498
23.11 Reed-Muller transform......Page 501
23.12 The OR-convolution and the AND-convolution......Page 504
23.13 The MAX-convolution......Page 506
23.14 Weighted arithmetic transform and subset convolution......Page 507
24.1 The 'standard' Haar transform......Page 512
24.2 In-place Haar transform......Page 514
24.3 Non-normalized Haar transforms......Page 516
24.4 Transposed Haar transforms......Page 518
24.5 The reversed Haar transform......Page 520
24.6 Relations between Walsh and Haar transforms......Page 522
24.7 Prefix transform and prefix convolution......Page 525
24.8 Nonstandard splitting schemes......Page 527
25.2 Radix-2 FHT algorithms......Page 530
25.3 Complex FFT by FHT......Page 536
25.4 Complex FFT by complex FHT and vice versa......Page 537
25.5 Real FFT by FHT and vice versa......Page 538
25.6 Higher radix FHT algorithms......Page 539
25.7 Convolution via FHT......Page 540
25.8 Localized FHT algorithms......Page 544
25.9 2-dimensional FHTs......Page 545
25.10 Automatic generation of transform code......Page 546
25.11 Eigenvectors of the Fourier and Hartley transform......Page 548
26.1 Prime moduli for NTTs......Page 550
26.2 Implementation of NTTs......Page 552
26.3 Convolution with NTTs......Page 557
27.1 Wavelet filters......Page 558
27.2 Implementation......Page 559
27.3 Moment conditions......Page 561
IV Fast arithmetic......Page 564
28.1 Splitting schemes for multiplication......Page 565
28.2 Fast multiplication via FFT......Page 573
28.3 Radix/precision considerations with FFT multiplication......Page 575
28.4 The sum-of-digits test......Page 577
28.5 Binary exponentiation......Page 578
29.1 Division, square root and cube root......Page 582
29.2 Root extraction for rationals......Page 585
29.3 Divisionless iterations for the inverse a-th root......Page 587
29.4 Initial approximations for iterations......Page 590
29.5 Some applications of the matrix square root......Page 591
29.6 Goldschmidt's algorithm......Page 596
29.7 Products for the a-th root......Page 598
29.8 Divisionless iterations for polynomial roots......Page 601
30.1 Iterations and their rate of convergence......Page 602
30.2 Schroder's formula......Page 603
30.3 Householder's formula......Page 607
30.4 Dealing with multiple roots......Page 608
30.5 More iterations......Page 609
30.6 Convergence improvement by the delta squared process......Page 613
31.1 The arithmetic-geometric mean (AGM)......Page 614
31.2 The elliptic integrals K and E......Page 615
31.3 Theta functions, eta functions, and singular values......Page 619
31.4 AGM-type algorithms for hypergeometric functions......Page 626
31.5 Computation of π......Page 630
32.1 Logarithm......Page 637
32.2 Exponential function......Page 642
32.3 Logarithm and exponential function of power series......Page 645
32.4 Simultaneous computation of logarithms of small primes......Page 647
32.5 Arctangent relations for π......Page 648
33.1 Shift-and-add algorithms for log_b(x) and b^x......Page 656
33.2 CORDIC algorithms......Page 661
34.1 The binary splitting algorithm for rational series......Page 666
34.2 Rectangular schemes for evaluation of power series......Page 673
34.3 The magic sumalt algorithm for alternating series......Page 677
35.1 Recurrences......Page 681
35.2 Chebyshev polynomials......Page 691
36.1 Definition and basic operations......Page 700
36.2 Transformations of hypergeometric series......Page 703
36.3 Examples: elementary functions......Page 709
36.4 Transformations for elliptic integrals......Page 715
36.5 The function x^x......Page 717
37.1 Cyclotomic polynomials, Mobius inversion, Lambert series......Page 719
37.2 Conversion of power series to in finite products......Page 724
37.3 Continued fractions......Page 731
38.1 A variation of the iteration for the inverse......Page 741
38.2 An iteration related to the Thue constant......Page 745
38.3 An iteration related to the Golay-Rudin-Shapiro sequence......Page 746
38.4 Iteration related to the ruler function......Page 748
38.5 An iteration related to the period-doubling sequence......Page 749
38.6 An iteration from substitution rules with sign......Page 753
38.7 Iterations related to the sum of digits......Page 754
38.8 Iterations related to the binary Gray code......Page 756
38.9 A function encoding the Hilbert curve......Page 762
38.10 Sparse power series......Page 765
38.11 An iteration related to the Fibonacci numbers......Page 768
38.12 Iterations related to the Pell numbers......Page 772
V Algorithms for finite fields......Page 778
39.1 Implementation of the arithmetic operations......Page 779
39.2 Modular reduction with structured primes......Page 783
39.3 The sieve of Eratosthenes......Page 785
39.4 The Chinese Remainder Theorem (CRT)......Page 787
39.5 The order of an element......Page 789
39.7 Composite modulus: the ring \mathbb{Z}/m\mathbb{Z}......Page 791
39.8 Quadratic residues......Page 796
39.9 Computation of a square root modulo m......Page 799
39.10 The Rabin-Miller test for compositeness......Page 801
39.11 Proving primality......Page 807
39.12 Complex modulus: the field GF(p^2)......Page 819
39.13 Solving the Pell equation......Page 827
39.14 Multiplication of hypercomplex numbers......Page 830
40.1 The basic arithmetical operations......Page 837
40.2 Multiplying binary polynomials of high degree......Page 842
40.3 Modular arithmetic with binary polynomials......Page 847
40.4 Irreducible polynomials......Page 852
40.5 Primitive polynomials......Page 856
40.6 The number of irreducible and primitive polynomials......Page 858
40.7 Transformations that preserve irreducibility......Page 860
40.8 Self-reciprocal polynomials......Page 861
40.9 Irreducible and primitive polynomials of special forms......Page 863
40.10 Generating irreducible polynomials from Lyndon words......Page 871
40.11 Irreducible and cyclotomic polynomials......Page 872
40.12 Factorization of binary polynomials......Page 873
41.1 Linear feedback shift registers (LFSR)......Page 879
41.2 Galois and Fibonacci setup......Page 882
41.3 Error detection by hashing: the CRC......Page 883
41.5 The number of m-sequences and De Bruijn sequences......Page 888
41.6 Auto-correlation of m-sequences......Page 890
41.7 Feedback carry shift registers (FCSR)......Page 891
41.8 Linear hybrid cellular automata (LHCA)......Page 893
41.9 Additive linear hybrid cellular automata......Page 897
42.1 Arithmetic and basic properties......Page 901
42.2 Minimal polynomials......Page 907
42.3 Fast computation of the trace vector......Page 910
42.4 Solving quadratic equations......Page 911
42.5 Representation by matrices......Page 914
42.6 Representation by normal bases......Page 915
42.7 Conversion between normal and polynomial representation......Page 925
42.8 Optimal normal bases (ONB)......Page 927
42.9 Gaussian normal bases......Page 929
A The electronic version of the book......Page 936
B Machine used for benchmarking......Page 937
C The GP language......Page 938
A......Page 946
B......Page 947
C......Page 950
D......Page 952
E, F......Page 953
G......Page 954
H......Page 955
I, J, K......Page 956
L......Page 958
M......Page 959
N, O, P......Page 960
Q, R......Page 961
S......Page 962
T......Page 963
U, V, W......Page 964
X, Y, Z......Page 965
A, B......Page 966
C......Page 967
D, E......Page 969
F......Page 970
G, H, I......Page 971
J, K, L......Page 974
M......Page 975
N......Page 976
O, P......Page 977
Q......Page 978
R, S......Page 979
T, U, V, W, X, Y, Z......Page 981