Contents
Preface p.xi
Part I Low level algorithms p.1
1 Bit wizardry p.2
1.1 Trivia
1.2 Operations on individual bits
1.3 Operations on low bits or blocks of a word
1.4 Extraction of ones, zeros, or blocks near transitions
1.5 Computing the index of a single set bit
1.6 Operations on high bits or blocks of a word
1.7 Functions related to the base-2 logarithm
1.8 Counting the bits and blocks of a word
1.9 Words as bitsets
1.10 Index of the i-th set bit
1.11 Avoiding branches
1.12 Bit-wise rotation of a word
1.13 Binary necklaces z
1.14 Reversing the bits of a word
1.15 Bit-wise zip
1.16 Gray code and parity
1.17 Bit sequency z
1.18 Powers of the Gray code z
1.19 Invertible transforms on words z
1.20 Scanning for zero bytes
1.21 Inverse and square root modulo 2n
1.22 Radix -2 (minus two) representation
1.23 A sparse signed binary representation
1.24 Generating bit combinations
1.25 Generating bit subsets of a given word
1.26 Binary words in lexicographic order for subsets
1.27 Fibonacci words z
1.28 Binary words and parentheses strings z
1.29 Permutations via primitives z
1.30 CPU instructions often missed
1.31 Some space filling curves z
2 Permutations and their operations p.102
2.1 Basic definitions and operations
2.2 Representation as disjoint cycles
2.3 Compositions of permutations
2.4 In-place methods to apply permutations to data
2.5 Random permutations
2.6 The revbin permutation
2.7 The radix permutation
2.8 In-place matrix transposition
2.9 Rotation by triple reversal
2.10 The zip permutation
2.11 The XOR permutation
2.12 The Gray permutation
2.13 The reversed Gray permutation
3 Sorting and searching p.134
3.1 Sorting algorithms
3.2 Binary search
3.3 Variants of sorting methods
3.4 Searching in unsorted arrays
3.5 Determination of equivalence classes
4 Data structures p.153
4.1 Stack (LIFO)
4.2 Ring buffer
4.3 Queue (FIFO)
4.4 Deque (double-ended queue)
4.5 Heap and priority queue
4.6 Bit-array
4.7 Left-right array
Part II Combinatorial generation p.171
5 Conventions and considerations p.172
5.1 Representations and orders
5.2 Ranking, unranking, and counting
5.3 Characteristics of the algorithms
5.4 Optimization techniques
5.5 Implementations, demo-programs, and timings
6 Combinations p.176
6.1 Binomial coefficients
6.2 Lexicographic and co-lexicographic order
6.3 Order by prefix shifts (cool-lex)
6.4 Minimal-change order
6.5 The Eades-McKay strong minimal-change order
6.6 Two-close orderings via endo/enup moves
6.7 Recursive generation of certain orderings
7 Compositions p.194
7.1 Co-lexicographic order
7.2 Co-lexicographic order for compositions into exactly k parts
7.3 Compositions and combinations
7.4 Minimal-change orders
8 Subsets p.202
8.1 Lexicographic order
8.2 Minimal-change order
8.3 Ordering with De Bruijn sequences
8.4 Shifts-order for subsets
8.5 k-subsets where k lies in a given range
9 Mixed radix numbers p.217
9.1 Counting (lexicographic) order
9.2 Minimal-change (Gray code) order
9.3 gslex order
9.4 endo order
9.5 Gray code for endo order
9.6 Fixed sum of digits
10 Permutations p.232
10.1 Factorial representations of permutations
10.2 Lexicographic order
10.3 Co-lexicographic order
10.4 An order from reversing prefixes
10.5 Minimal-change order (Heap's algorithm)
10.6 Lipski's Minimal-change orders
10.7 Strong minimal-change order (Trotter's algorithm)
10.8 Star-transposition order
10.9 Minimal-change orders from factorial numbers
10.10 Derangement order
10.11 Orders where the smallest element always moves right
10.12 Single track orders
11 Permutations with special properties p.277
11.1 The number of certain permutations
11.2 Permutations with distance restrictions
11.3 Self-inverse permutations (involutions)
11.4 Cyclic permutations
12 k-permutations p.291
12.1 Lexicographic order
12.2 Minimal-change order
13 Multisets p.295
13.1 Subsets of a multiset
13.2 Permutations of a multiset
14 Gray codes for strings with restrictions p.304
14.1 List recursions
14.2 Fibonacci words
14.3 Generalized Fibonacci words
14.4 Run-length limited (RLL) words
14.5 Digit x followed by at least x zeros
14.6 Generalized Pell words
14.7 Sparse signed binary words
14.8 Strings with no two consecutive nonzero digits
14.9 Strings with no two consecutive zeros
14.10 Binary strings without substrings 1x1 or 1xy1 z
15 Parentheses strings p.323
15.1 Co-lexicographic order
15.2 Gray code via restricted growth strings
15.3 Order by prefix shifts (cool-lex)
15.4 Catalan numbers
15.5 Increment-i RGS, k-ary Dyck words, and k-ary trees
16 Integer partitions p.339
16.1 Solution of a generalized problem
16.2 Iterative algorithm
16.3 Partitions into m parts
16.4 The number of integer partitions
17 Set partitions p.354
17.1 Recursive generation
17.2 The number of set partitions: Stirling set numbers and Bell numbers
17.3 Restricted growth strings
18 Necklaces and Lyndon words p.370
18.1 Generating all necklaces
18.2 Lex-min De Bruijn sequence from necklaces
18.3 The number of binary necklaces
18.4 Sums of roots of unity that are zero z
19 Hadamard and conference matrices p.384
19.1 Hadamard matrices via LFSR
19.2 Hadamard matrices via conference matrices
19.3 Conference matrices via finite fields
20 Searching paths in directed graphs z p.391
20.1 Representation of digraphs
20.2 Searching full paths
20.3 Conditional search
20.4 Edge sorting and lucky paths
20.5 Gray codes for Lyndon words
Part III Fast transforms p.409
21 The Fourier transform p.410
21.1 The discrete Fourier transform
21.2 Radix-2 FFT algorithms
21.3 Saving trigonometric computations
21.4 Higher radix FFT algorithms
21.5 Split-radix algorithm
21.6 Symmetries of the Fourier transform
21.7 Inverse FFT for free
21.8 Real-valued Fourier transforms
21.9 Multi-dimensional Fourier transforms
21.10 The matrix Fourier algorithm (MFA)
22 Convolution, correlation, and more FFT algorithms p.440
22.1 Convolution
22.2 Correlation
22.3 Correlation, convolution, and circulant matrices z
22.4 Weighted Fourier transforms and convolutions
22.5 Convolution using the MFA
22.6 The z-transform (ZT)
22.7 Prime length FFTs
23 The Walsh transform and its relatives p.459
23.1 Transform with Walsh-Kronecker basis
23.2 Eigenvectors of the Walsh transform z
23.3 The Kronecker product
23.4 Higher radix Walsh transforms
23.5 Localized Walsh transforms
23.6 Transform with Walsh-Paley basis
23.7 Sequency-ordered Walsh transforms
23.8 XOR (dyadic) convolution
23.9 Slant transform
23.10 Arithmetic transform
23.11 Reed-Muller transform
23.12 The OR-convolution and the AND-convolution
23.13 The MAX-convolution z
23.14 Weighted arithmetic transform and subset convolution
24 The Haar transform p.497
24.1 The `standard' Haar transform
24.2 In-place Haar transform
24.3 Non-normalized Haar transforms
24.4 Transposed Haar transforms z
24.5 The reversed Haar transform z
24.6 Relations between Walsh and Haar transforms
24.7 Prefix transform and prefix convolution
24.8 Nonstandard splitting schemes z
25 The Hartley transform p.515
25.1 Definition and symmetries
25.2 Radix-2 FHT algorithms
25.3 Complex FFT by FHT
25.4 Complex FFT by complex FHT and vice versa
25.5 Real FFT by FHT and vice versa
25.6 Higher radix FHT algorithms
25.7 Convolution via FHT
25.8 Localized FHT algorithms
25.9 2-dimensional FHTs
25.10 Automatic generation of transform code
25.11 Eigenvectors of the Fourier and Hartley transform z
26 Number theoretic transforms (NTTs) p.535
26.1 Prime moduli for NTTs
26.2 Implementation of NTTs
26.3 Convolution with NTTs
27 Fast wavelet transforms p.543
27.1 Wavelet filters
27.2 Implementation
27.3 Moment conditions
Part IV Fast arithmetic p.549
28 Fast multiplication and exponentiation p.550
28.1 Splitting schemes for multiplication
28.2 Fast multiplication via FFT
28.3 Radix/precision considerations with FFT multiplication
28.4 The sum-of-digits test
28.5 Binary exponentiation
29 Root extraction p.567
29.1 Division, square root and cube root
29.2 Root extraction for rationals
29.3 Divisionless iterations for the inverse a-th root
29.4 Initial approximations for iterations
29.5 Some applications of the matrix square root
29.6 Goldschmidt's algorithm
29.7 Products for the a-th root z
29.8 Divisionless iterations for polynomial roots
30 Iterations for the inversion of a function p.587
30.1 Iterations and their rate of convergence
30.2 Schr"oder's formula
30.3 Householder's formula
30.4 Dealing with multiple roots
30.5 More iterations
30.6 Convergence improvement by the delta squared process
31 The AGM, elliptic integrals, and algorithms for computing ss p.599
31.1 The arithmetic-geometric mean (AGM)
31.2 The elliptic integrals K and E
31.3 Theta functions, eta functions, and singular values
31.4 AGM-type algorithms for hypergeometric functions
31.5 Computation of ss
32 Logarithm and exponential function p.622
32.1 Logarithm
32.2 Exponential function
32.3 Logarithm and exponential function of power series
32.4 Simultaneous computation of logarithms of small primes
32.5 Arctangent relations for ss z
33 Computing the elementary functions with limited resources p.641
33.1 Shift-and-add algorithms for log b(x) and bx
33.2 CORDIC algorithms
34 Numerical evaluation of power series p.651
34.1 The binary splitting algorithm for rational series
34.2 Rectangular schemes for evaluation of power series
34.3 The magic sumalt algorithm for alternating series
35 Recurrences and Chebyshev polynomials p.666
35.1 Recurrences
35.2 Chebyshev polynomials
36 Hypergeometric series p.685
36.1 Definition and basic operations
36.2 Transformations of hypergeometric series
36.3 Examples: elementary functions
36.4 Transformations for elliptic integrals z
36.5 The function xx z
37 Cyclotomic polynomials, product forms, and continued fractions p.704
37.1 Cyclotomic polynomials, M"obius inversion, Lambert series
37.2 Conversion of power series to infinite products
37.3 Continued fractions
38 Synthetic Iterations z p.726
38.1 A variation of the iteration for the inverse
38.2 An iteration related to the Thue constant
38.3 An iteration related to the Golay-Rudin-Shapiro sequence
38.4 Iteration related to the ruler function
38.5 An iteration related to the period-doubling sequence
38.6 An iteration from substitution rules with sign
38.7 Iterations related to the sum of digits
38.8 Iterations related to the binary Gray code
38.9 A function encoding the Hilbert curve
38.10 Sparse power series
38.11 An iteration related to the Fibonacci numbers
38.12 Iterations related to the Pell numbers
Part V Algorithms for finite fields p.763
39 Modular arithmetic and some number theory p.764
39.1 Implementation of the arithmetic operations
39.2 Modular reduction with structured primes
39.3 The sieve of Eratosthenes
39.4 The Chinese Remainder Theorem (CRT)
39.5 The order of an element
39.6 Prime modulus: the field Z=pZ = Fp = GF (p)
39.7 Composite modulus: the ring Z=mZ
39.8 Quadratic residues
39.9 Computation of a square root modulo m
39.10 The Rabin-Miller test for compositeness
39.11 Proving primality
39.12 Complex modulus: the field GF (p2)
39.13 Solving the Pell equation
39.14 Multiplication of hypercomplex numbers z
40 Binary polynomials p.822
40.1 The basic arithmetical operations
40.2 Multiplying binary polynomials of high degree
40.3 Modular arithmetic with binary polynomials
40.4 Irreducible polynomials
40.5 Primitive polynomials
40.6 The number of irreducible and primitive polynomials
40.7 Transformations that preserve irreducibility
40.8 Self-reciprocal polynomials
40.9 Irreducible and primitive polynomials of special forms z
40.10 Generating irreducible polynomials from Lyndon words
40.11 Irreducible and cyclotomic polynomials z
40.12 Factorization of binary polynomials
41 Shift registers p.864
41.1 Linear feedback shift registers (LFSR)
41.2 Galois and Fibonacci setup
41.3 Error detection by hashing: the CRC
41.4 Generating all revbin pairs
41.5 The number of m-sequences and De Bruijn sequences
41.6 Auto-correlation of m-sequences
41.7 Feedback carry shift registers (FCSR)
41.8 Linear hybrid cellular automata (LHCA)
41.9 Additive linear hybrid cellular automata
42 Binary finite fields: GF (2n ) p.886
42.1 Arithmetic and basic properties
42.2 Minimal polynomials
42.3 Fast computation of the trace vector
42.4 Solving quadratic equations
42.5 Representation by matrices z
42.6 Representation by normal bases
42.7 Conversion between normal and polynomial representation
42.8 Optimal normal bases (ONB)
42.9 Gaussian normal bases
A The electronic version of the book p.921
B Machine used for benchmarking p.922
C The GP language p.923
Bibliography p.931
Part Index p.951