Matters Computational: Ideas, Algorithms, Source Code

Preface
I Low level algorithms
Bit wizardry
Trivia
Operations on individual bits
Operations on low bits or blocks of a word
Extraction of ones, zeros, or blocks near transitions
Computing the index of a single set bit
Operations on high bits or blocks of a word
Functions related to the base-2 logarithm
Counting the bits and blocks of a word
Words as bitsets
Index of the i-th set bit
Avoiding branches
Bit-wise rotation of a word
Binary necklaces
Reversing the bits of a word
Bit-wise zip
Gray code and parity
Bit sequency
Powers of the Gray code
Invertible transforms on words
Scanning for zero bytes
Inverse and square root modulo 2n
Radix -2 (minus two) representation
A sparse signed binary representation
Generating bit combinations
Generating bit subsets of a given word
Binary words in lexicographic order for subsets
Fibonacci words
Binary words and parentheses strings
Permutations via primitives
CPU instructions often missed
Some space filling curves
Permutations and their operations
Basic definitions and operations
Representation as disjoint cycles
Compositions of permutations
In-place methods to apply permutations to data
Random permutations
The revbin permutation
The radix permutation
In-place matrix transposition
Rotation by triple reversal
The zip permutation
The XOR permutation
The Gray permutation
The reversed Gray permutation
Sorting and searching
Sorting algorithms
Binary search
Variants of sorting methods
Searching in unsorted arrays
Determination of equivalence classes
Data structures
Stack (LIFO)
Ring buffer
Queue (FIFO)
Deque (double-ended queue)
Heap and priority queue
Bit-array
Left-right array
II Combinatorial generation
Conventions and considerations
Representations and orders
Ranking, unranking, and counting
Characteristics of the algorithms
Optimization techniques
Implementations, demo-programs, and timings
Combinations
Binomial coefficients
Lexicographic and co-lexicographic order
Order by prefix shifts (cool-lex)
Minimal-change order
The Eades-McKay strong minimal-change order
Two-close orderings via endo/enup moves
Recursive generation of certain orderings
Compositions
Co-lexicographic order
Co-lexicographic order for compositions into exactly k parts
Compositions and combinations
Minimal-change orders
Subsets
Lexicographic order
Minimal-change order
Ordering with De Bruijn sequences
Shifts-order for subsets
k-subsets where k lies in a given range
Mixed radix numbers
Counting (lexicographic) order
Minimal-change (Gray code) order
gslex order
endo order
Gray code for endo order
Fixed sum of digits
Permutations
Factorial representations of permutations
Lexicographic order
Co-lexicographic order
An order from reversing prefixes
Minimal-change order (Heap's algorithm)
Lipski's Minimal-change orders
Strong minimal-change order (Trotter's algorithm)
Star-transposition order
Minimal-change orders from factorial numbers
Derangement order
Orders where the smallest element always moves right
Single track orders
Permutations with special properties
The number of certain permutations
Permutations with distance restrictions
Self-inverse permutations (involutions)
Cyclic permutations
k-permutations
Lexicographic order
Minimal-change order
Multisets
Subsets of a multiset
Permutations of a multiset
Gray codes for strings with restrictions
List recursions
Fibonacci words
Generalized Fibonacci words
Run-length limited (RLL) words
Digit x followed by at least x zeros
Generalized Pell words
Sparse signed binary words
Strings with no two consecutive nonzero digits
Strings with no two consecutive zeros
Binary strings without substrings 1x1 or 1xy1
Parentheses strings
Co-lexicographic order
Gray code via restricted growth strings
Order by prefix shifts (cool-lex)
Catalan numbers
Increment-i RGS, k-ary Dyck words, and k-ary trees
Integer partitions
Solution of a generalized problem
Iterative algorithm
Partitions into m parts
The number of integer partitions
Set partitions
Recursive generation
The number of set partitions: Stirling set numbers and Bell numbers
Restricted growth strings
Necklaces and Lyndon words
Generating all necklaces
Lex-min De Bruijn sequence from necklaces
The number of binary necklaces
Sums of roots of unity that are zero
Hadamard and conference matrices
Hadamard matrices via LFSR
Hadamard matrices via conference matrices
Conference matrices via finite fields
Searching paths in directed graphs
Representation of digraphs
Searching full paths
Conditional search
Edge sorting and lucky paths
Gray codes for Lyndon words
III Fast transforms
The Fourier transform
The discrete Fourier transform
Radix-2 FFT algorithms
Saving trigonometric computations
Higher radix FFT algorithms
Split-radix algorithm
Symmetries of the Fourier transform
Inverse FFT for free
Real-valued Fourier transforms
Multi-dimensional Fourier transforms
The matrix Fourier algorithm (MFA)
Convolution, correlation, and more FFT algorithms
Convolution
Correlation
Correlation, convolution, and circulant matrices
Weighted Fourier transforms and convolutions
Convolution using the MFA
The z-transform (ZT)
Prime length FFTs
The Walsh transform and its relatives
Transform with Walsh-Kronecker basis
Eigenvectors of the Walsh transform
The Kronecker product
Higher radix Walsh transforms
Localized Walsh transforms
Transform with Walsh-Paley basis
Sequency-ordered Walsh transforms
XOR (dyadic) convolution
Slant transform
Arithmetic transform
Reed-Muller transform
The OR-convolution and the AND-convolution
The MAX-convolution
Weighted arithmetic transform and subset convolution
The Haar transform
The `standard' Haar transform
In-place Haar transform
Non-normalized Haar transforms
Transposed Haar transforms
The reversed Haar transform
Relations between Walsh and Haar transforms
Prefix transform and prefix convolution
Nonstandard splitting schemes
The Hartley transform
Definition and symmetries
Radix-2 FHT algorithms
Complex FFT by FHT
Complex FFT by complex FHT and vice versa
Real FFT by FHT and vice versa
Higher radix FHT algorithms
Convolution via FHT
Localized FHT algorithms
2-dimensional FHTs
Automatic generation of transform code
Eigenvectors of the Fourier and Hartley transform
Number theoretic transforms (NTTs)
Prime moduli for NTTs
Implementation of NTTs
Convolution with NTTs
Fast wavelet transforms
Wavelet filters
Implementation
Moment conditions
IV Fast arithmetic
Fast multiplication and exponentiation
Splitting schemes for multiplication
Fast multiplication via FFT
Radix/precision considerations with FFT multiplication
The sum-of-digits test
Binary exponentiation
Root extraction
Division, square root and cube root
Root extraction for rationals
Divisionless iterations for the inverse a-th root
Initial approximations for iterations
Some applications of the matrix square root
Goldschmidt's algorithm
Products for the a-th root
Divisionless iterations for polynomial roots
Iterations for the inversion of a function
Iterations and their rate of convergence
Schröder's formula
Householder's formula
Dealing with multiple roots
More iterations
Convergence improvement by the delta squared process
The AGM, elliptic integrals, and algorithms for computing
The arithmetic-geometric mean (AGM)
The elliptic integrals K and E
Theta functions, eta functions, and singular values
AGM-type algorithms for hypergeometric functions
Computation of
Logarithm and exponential function
Logarithm
Exponential function
Logarithm and exponential function of power series
Simultaneous computation of logarithms of small primes
Arctangent relations for
Computing the elementary functions with limited resources
Shift-and-add algorithms for logb(x) and bx
CORDIC algorithms
Numerical evaluation of power series
The binary splitting algorithm for rational series
Rectangular schemes for evaluation of power series
The magic sumalt algorithm for alternating series
Recurrences and Chebyshev polynomials
Recurrences
Chebyshev polynomials
Hypergeometric series
Definition and basic operations
Transformations of hypergeometric series
Examples: elementary functions
Transformations for elliptic integrals
The function xx
Cyclotomic polynomials, product forms, and continued fractions
Cyclotomic polynomials, Möbius inversion, Lambert series
Conversion of power series to infinite products
Continued fractions
Synthetic Iterations
A variation of the iteration for the inverse
An iteration related to the Thue constant
An iteration related to the Golay-Rudin-Shapiro sequence
Iteration related to the ruler function
An iteration related to the period-doubling sequence
An iteration from substitution rules with sign
Iterations related to the sum of digits
Iterations related to the binary Gray code
A function encoding the Hilbert curve
Sparse power series
An iteration related to the Fibonacci numbers
Iterations related to the Pell numbers
V Algorithms for finite fields
Modular arithmetic and some number theory
Implementation of the arithmetic operations
Modular reduction with structured primes
The sieve of Eratosthenes
The Chinese Remainder Theorem (CRT)
The order of an element
Prime modulus: the field Z/pZ=Fp=GF(p)
Composite modulus: the ring Z/mZ
Quadratic residues
Computation of a square root modulo m
The Rabin-Miller test for compositeness
Proving primality
Complex modulus: the field GF(p2)
Solving the Pell equation
Multiplication of hypercomplex numbers
Binary polynomials
The basic arithmetical operations
Multiplying binary polynomials of high degree
Modular arithmetic with binary polynomials
Irreducible polynomials
Primitive polynomials
The number of irreducible and primitive polynomials
Transformations that preserve irreducibility
Self-reciprocal polynomials
Irreducible and primitive polynomials of special forms
Generating irreducible polynomials from Lyndon words
Irreducible and cyclotomic polynomials
Factorization of binary polynomials
Shift registers
Linear feedback shift registers (LFSR)
Galois and Fibonacci setup
Error detection by hashing: the CRC
Generating all revbin pairs
The number of m-sequences and De Bruijn sequences
Auto-correlation of m-sequences
Feedback carry shift registers (FCSR)
Linear hybrid cellular automata (LHCA)
Additive linear hybrid cellular automata
Binary finite fields: GF(2n)
Arithmetic and basic properties
Minimal polynomials
Fast computation of the trace vector
Solving quadratic equations
Representation by matrices
Representation by normal bases
Conversion between normal and polynomial representation
Optimal normal bases (ONB)
Gaussian normal bases
The electronic version of the book
Machine used for benchmarking
The GP language
Bibliography
Index