Contents Preface p.xi Part I Low level algorithms p.1 1 Bit wizardry p.3 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 Space filling curves 1.21 Scanning for zero bytes 1.22 Inverse and square root modulo 2n 1.23 Radix -2 (minus two) representation 1.24 A sparse signed binary representation 1.25 Generating bit combinations 1.26 Generating bit subsets of a given word 1.27 Binary words in lexicographic order for subsets 1.28 Fibonacci words z 1.29 Binary words and parentheses strings z 1.30 Permutations via primitives z 1.31 CPU instructions often missed 2 Permutations and their operations p.97 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.129 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.149 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 4.8 Finite state machines Part II Combinatorial generation p.169 5 Conventions and considerations p.171 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.175 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.193 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.201 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 10 Permutations p.231 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 10.13 Permutations with special properties 10.14 Self-inverse permutations (involutions) 10.15 Cyclic permutations 11 Multisets p.291 11.1 Subsets of a multiset 11.2 Permutations of a multiset 12 Gray codes for strings with restrictions p.301 12.1 List recursions 12.2 Fibonacci words 12.3 Generalized Fibonacci words 12.4 Digit x followed by at least x zeros 12.5 Generalized Pell words 12.6 Sparse signed binary words 12.7 Strings with no two consecutive nonzero digits 12.8 Strings with no two consecutive zeros 12.9 Binary strings without substrings 1x1 or 1xy1 13 Parentheses strings p.319 13.1 Co-lexicographic order 13.2 Gray code via restricted growth strings 13.3 Order by prefix shifts (cool-lex) 13.4 Catalan numbers 13.5 Increment-i RGS and k-ary trees 14 Integer partitions p.333 14.1 Solution of a generalized problem 14.2 Iterative algorithm 14.3 Partitions into m parts 14.4 The number of integer partitions 15 Set partitions p.347 15.1 Recursive generation 15.2 The number of set partitions: Stirling set numbers and Bell numbers 15.3 Restricted growth strings 16 Necklaces and Lyndon words p.363 16.1 Generating all necklaces 16.2 Lex-min De Bruijn sequence from necklaces 16.3 The number of binary necklaces 16.4 Sums of roots of unity that are zero z 17 Hadamard and conference matrices p.377 17.1 Hadamard matrices via LFSR 17.2 Hadamard matrices via conference matrices 17.3 Conference matrices via finite fields 18 Searching paths in directed graphs z p.385 18.1 Representation of digraphs 18.2 Searching full paths 18.3 Conditional search 18.4 Edge sorting and lucky paths 18.5 Gray codes for Lyndon words Part III Fast transforms p.403 19 The Fourier transform p.405 19.1 The discrete Fourier transform 19.2 Radix-2 FFT algorithms 19.3 Saving trigonometric computations 19.4 Higher radix FFT algorithms 19.5 Split-radix algorithm 19.6 Symmetries of the Fourier transform 19.7 Inverse FFT for free 19.8 Real-valued Fourier transforms 19.9 Multi-dimensional Fourier transforms 19.10 The matrix Fourier algorithm (MFA) 20 Convolution, correlation, and more FFT algorithms p.437 20.1 Convolution 20.2 Correlation 20.3 Weighted Fourier transforms and convolutions 20.4 Convolution using the MFA 20.5 The z-transform (ZT) 20.6 Prime length FFTs 21 The Walsh transform and its relatives p.457 21.1 Transform with Walsh-Kronecker basis 21.2 Eigenvectors of the Walsh transform z 21.3 The Kronecker product 21.4 Higher radix Walsh transforms 21.5 Localized Walsh transforms 21.6 Transform with Walsh-Paley basis 21.7 Sequency-ordered Walsh transforms 21.8 XOR (dyadic) convolution 21.9 Slant transform 21.10 Arithmetic transform 21.11 Reed-Muller transform 21.12 The OR-convolution and the AND-convolution 21.13 The MAX-convolution z 21.14 Weighted arithmetic transform and subset convolution 22 The Haar transform p.497 22.1 The `standard' Haar transform 22.2 In-place Haar transform 22.3 Non-normalized Haar transforms 22.4 Transposed Haar transforms z 22.5 The reversed Haar transform z 22.6 Relations between Walsh and Haar transforms 22.7 Prefix transform and prefix convolution 22.8 Nonstandard splitting schemes z 23 The Hartley transform p.515 23.1 Definition and symmetries 23.2 Radix-2 FHT algorithms 23.3 Complex FFT by FHT 23.4 Complex FFT by complex FHT and vice versa 23.5 Real FFT by FHT and vice versa 23.6 Higher radix FHT algorithms 23.7 Convolution via FHT 23.8 Localized FHT algorithms 23.9 2-dimensional FHTs 23.10 Automatic generation of transform code 23.11 Eigenvectors of the Fourier and Hartley transform z 24 Number theoretic transforms (NTTs) p.535 24.1 Prime moduli for NTTs 24.2 Implementation of NTTs 24.3 Convolution with NTTs 25 Fast wavelet transforms p.543 25.1 Wavelet filters 25.2 Implementation 25.3 Moment conditions Part IV Fast arithmetic p.549 26 Fast multiplication and exponentiation p.551 26.1 Splitting schemes for multiplication 26.2 Fast multiplication via FFT 26.3 Radix/precision considerations with FFT multiplication 26.4 The sum-of-digits test 26.5 Binary exponentiation 27 Root extraction p.569 27.1 Division, square root and cube root 27.2 Root extraction for rationals 27.3 Divisionless iterations for the inverse a-th root 27.4 Initial approximations for iterations 27.5 Some applications of the matrix square root 27.6 Goldschmidt's algorithm 27.7 Products for the a-th root z 27.8 Divisionless iterations for polynomial roots 28 Iterations for the inversion of a function p.591 28.1 Iterations and their rate of convergence 28.2 Schröder's formula 28.3 Householder's formula 28.4 Dealing with multiple roots 28.5 More iterations 28.6 Convergence improvement by the delta squared process 29 The AGM, elliptic integrals, and algorithms for computing ß p.605 29.1 The arithmetic-geometric mean (AGM) 29.2 The elliptic integrals K and E 29.3 Theta functions, eta functions, and singular values 29.4 AGM-type algorithms for hypergeometric functions 29.5 Computation of ß 29.6 Arctangent relations for ß z 30 Logarithm and exponential function p.635 30.1 Logarithm 30.2 Exponential function 30.3 Logarithm and exponential function of power series 30.4 Simultaneous computation of logarithms of small primes 31 Computing the elementary functions with limited resources p.649 31.1 Shift-and-add algorithms for log b(x) and bx 31.2 CORDIC algorithms 32 Numerical evaluation of power series p.659 32.1 The binary splitting algorithm for rational series 32.2 Rectangular schemes for evaluation of power series 32.3 The magic sumalt algorithm for alternating series 33 Recurrences and Chebyshev polynomials p.675 33.1 Recurrences 33.2 Chebyshev polynomials 34 Hypergeometric series p.695 34.1 Definition and basic operations 34.2 Transformations of hypergeometric series 34.3 Examples: elementary functions 34.4 Transformations for elliptic integrals z 34.5 The function xx z 35 Cyclotomic polynomials, product forms, and continued fractions p.715 35.1 Cyclotomic polynomials, Möbius inversion, Lambert series 35.2 Conversion of power series to infinite products 35.3 Continued fractions 36 Synthetic Iterations z p.737 36.1 A variation of the iteration for the inverse 36.2 An iteration related to the Thue constant 36.3 An iteration related to the Golay-Rudin-Shapiro sequence 36.4 Iteration related to the ruler function 36.5 An iteration related to the period-doubling sequence 36.6 An iteration from substitution rules with sign 36.7 Iterations related to the sum of digits 36.8 Iterations related to the binary Gray code 36.9 A function encoding the Hilbert curve 36.10 Sparse power series 36.11 An iteration related to the Fibonacci numbers 36.12 Iterations related to the Pell numbers Part V Algorithms for finite fields p.775 37 Modular arithmetic and some number theory p.777 37.1 Implementation of the arithmetic operations 37.2 Modular reduction with structured primes 37.3 The sieve of Eratosthenes 37.4 The Chinese Remainder Theorem (CRT) 37.5 The order of an element 37.6 Prime modulus: the field Z=pZ = Fp = GF (p) 37.7 Composite modulus: the ring Z=mZ 37.8 Quadratic residues 37.9 Computation of a square root modulo m 37.10 The Rabin-Miller test for compositeness 37.11 Proving primality 37.12 Complex modulus: the field GF (p2) 37.13 Solving the Pell equation 37.14 Multiplication of hypercomplex numbers z 38 Binary polynomials p.835 38.1 The basic arithmetical operations 38.2 Multiplying binary polynomials of high degree 38.3 Modular arithmetic with binary polynomials 38.4 Irreducible polynomials 38.5 Primitive polynomials 38.6 The number of irreducible and primitive polynomials 38.7 Transformations that preserve irreducibility 38.8 Self-reciprocal polynomials 38.9 Irreducible and primitive polynomials of special forms z 38.10 Generating irreducible polynomials from Lyndon words 38.11 Irreducible and cyclotomic polynomials z 38.12 Factorization of binary polynomials 39 Shift registers p.879 39.1 Linear feedback shift registers (LFSR) 39.2 Galois and Fibonacci setup 39.3 Error detection by hashing: the CRC 39.4 Generating all revbin pairs 39.5 The number of m-sequences and De Bruijn sequences 39.6 Auto-correlation of m-sequences 39.7 Feedback carry shift registers (FCSR) 39.8 Linear hybrid cellular automata (LHCA) 39.9 Additive linear hybrid cellular automata 40 Binary finite fields: GF (2n ) p.901 40.1 Arithmetic and basic properties 40.2 Minimal polynomials 40.3 Fast computation of the trace vector 40.4 Solving quadratic equations 40.5 Representation by matrices z 40.6 Representation by normal bases 40.7 Conversion between normal and polynomial representation 40.8 Optimal normal bases (ONB) 40.9 Gaussian normal bases A The electronic version of the book p.937 B Machine used for benchmarking p.939 C The GP language p.941 D The pseudo language Sprache p.949 Bibliography p.951 Part Index p.971