Algorithms for programmers: ideas and source code

Important remarks about this document......Page 11
I Low level algorithms......Page 13
Trivia......Page 15
Operations on individual bits......Page 20
Operations on low bits or blocks of a word......Page 21
Isolating blocks of bits and single bits......Page 24
Computing the index of a single set bit......Page 26
Operations on high bits or blocks of a word......Page 28
Functions related to the base-2 logarithm......Page 30
Counting bits and blocks of a word......Page 31
Bit set lookup......Page 33
Avoiding branches......Page 34
Bit-wise rotation of a word......Page 38
Functions related to bit-wise rotation *......Page 39
Reversing the bits of a word......Page 42
Bit-wise zip......Page 47
Gray code and parity......Page 48
Bit sequency......Page 54
Powers of the Gray code......Page 55
Invertible transforms on words......Page 57
Moves of the Hilbert curve......Page 63
The Z-order......Page 65
Scanning for zero bytes......Page 66
2-adic inverse and square root......Page 67
Radix -2 representation......Page 68
A sparse signed binary representation......Page 71
Generating bit combinations......Page 73
Generating bit subsets of a given word......Page 75
Binary words as subsets in lexicographic order......Page 76
Minimal-change bit combinations......Page 81
Fibonacci words......Page 83
Binary words and parentheses strings *......Page 86
Error detection by hashing: the CRC......Page 89
Permutations via primitives......Page 93
CPU instructions often missed......Page 96
The revbin permutation......Page 97
In-place matrix transposition......Page 101
Revbin permutation and matrix transposition *......Page 103
The zip permutation......Page 105
The reversed zip permutation......Page 107
The XOR permutation......Page 108
The Gray code permutation......Page 109
The reversed Gray code permutation......Page 113
Decomposing permutations *......Page 114
General permutations and their operations......Page 116
Sorting......Page 127
Binary search......Page 129
Index sorting......Page 130
Pointer sorting......Page 132
Sorting by a supplied comparison function......Page 133
Determination of unique elements......Page 136
Unique elements with inexact types......Page 137
Determination of equivalence classes......Page 139
Determination of monotonicity and convexity *......Page 143
Counting sort and radix sort......Page 146
Searching in unsorted arrays......Page 149
Stack (LIFO)......Page 153
Ring buffer......Page 155
Queue (FIFO)......Page 156
Deque (double-ended queue)......Page 158
Heap and priority queue......Page 160
Bit-array......Page 164
Finite-state machines......Page 166
Emulation of coroutines......Page 168
II Combinatorial generation......Page 171
About representations and orders......Page 173
Optimization techniques......Page 174
Remarks about the C++ implementations......Page 176
Combinations......Page 177
Lexicographic and co-lexicographic order......Page 178
Order by prefix shifts (cool-lex)......Page 181
Minimal-change order......Page 182
The Eades-McKay strong minimal-change order......Page 184
Two-close orderings via endo/enup moves......Page 187
Recursive generation of certain orderings......Page 191
Co-lexicographic order......Page 195
Co-lexicographic order for compositions into exactly k parts......Page 197
Compositions and combinations......Page 199
Minimal-change orders......Page 200
Lexicographic order......Page 203
Minimal-change order......Page 205
Ordering with De Bruijn sequences......Page 209
Shifts-order for subsets......Page 211
k-subsets where k lies in a given range......Page 212
Counting order......Page 219
Gray code order......Page 222
gslex order......Page 225
endo order......Page 228
Gray code for endo order......Page 229
Lexicographic order......Page 231
Co-lexicographic order......Page 233
Factorial representations of permutations......Page 234
An order from reversing prefixes......Page 243
Minimal-change order (Heap's algorithm)......Page 246
Lipski's Minimal-change orders......Page 248
Strong minimal-change order (Trotter's algorithm)......Page 251
Minimal-change orders from factorial numbers......Page 256
Orders where the smallest element always moves right......Page 262
Single track orders......Page 266
Star-transposition order......Page 271
Derangement order......Page 272
Recursive algorithm for cyclic permutations......Page 275
Minimal-change order for cyclic permutations......Page 277
Permutations with special properties......Page 279
Subsets of a multiset......Page 287
Permutations of a multiset......Page 288
Gray codes for strings with restrictions......Page 293
Fibonacci words......Page 294
Generalized Fibonacci words......Page 296
Digit x followed by at least x zeros......Page 299
Generalized Pell words......Page 300
Sparse signed binary words......Page 302
Strings with no two successive nonzero digits......Page 304
Strings with no two successive zeros......Page 306
Binary strings without substrings 1x1......Page 307
Binary strings without substrings 1xy1......Page 308
Co-lexicographic order......Page 311
Gray code via restricted growth strings......Page 313
The number of parenthesis strings: Catalan numbers......Page 318
Increment-i RGS and k-ary trees......Page 319
Recursive solution of a generalized problem......Page 323
Iterative algorithm......Page 325
Partitions into m parts......Page 327
The number of integer partitions......Page 328
Set partitions......Page 331
The number of set partitions: Stirling set numbers and Bell numbers......Page 332
Generation in minimal-change order......Page 333
A string substitution engine......Page 343
Necklaces and Lyndon words......Page 347
Generating all necklaces......Page 348
The number of binary necklaces......Page 355
The number of binary necklaces with fixed content......Page 356
Hadamard matrices via LFSR......Page 359
Hadamard matrices via conference matrices......Page 361
Conference matrices via finite fields......Page 363
Searching paths in directed graphs......Page 367
Representation of digraphs......Page 368
Searching full paths......Page 369
Conditional search......Page 374
Edge sorting and lucky paths......Page 378
Gray codes for Lyndon words......Page 379
III Fast orthogonal transforms......Page 385
The discrete Fourier transform......Page 387
Summary of definitions of Fourier transforms *......Page 388
Radix-2 FFT algorithms......Page 390
Saving trigonometric computations......Page 395
Higher radix FFT algorithms......Page 397
Split-radix Fourier transforms......Page 404
Symmetries of the Fourier transform......Page 407
Inverse FFT for free......Page 409
Real valued Fourier transforms......Page 410
Multidimensional Fourier transforms......Page 416
The matrix Fourier algorithm (MFA)......Page 418
Convolution......Page 421
Correlation......Page 426
Weighted Fourier transforms and convolutions......Page 429
Convolution using the MFA......Page 431
The z-transform (ZT)......Page 434
Prime length FFTs......Page 438
The Walsh transform: Walsh-Kronecker basis......Page 441
Eigenvectors of the Walsh transform *......Page 444
The Kronecker product......Page 445
A variant of the Walsh transform *......Page 448
Higher radix Walsh transforms......Page 449
Localized Walsh transforms......Page 452
Dyadic (XOR) convolution......Page 457
The Walsh transform: Walsh-Paley basis......Page 459
Sequency ordered Walsh transforms......Page 460
Slant transform......Page 466
Arithmetic transform......Page 467
Reed-Muller transform......Page 471
The OR-convolution, and the AND-convolution......Page 474
The `standard' Haar transform......Page 477
In-place Haar transform......Page 479
Non-normalized Haar transforms......Page 481
Transposed Haar transforms......Page 483
The reversed Haar transform......Page 485
Relations between Walsh and Haar transforms......Page 487
Nonstandard splitting schemes *......Page 490
Definition and symmetries......Page 495
Radix-2 FHT algorithms......Page 496
Complex FT by HT......Page 501
Complex FT by complex HT and vice versa......Page 502
Real FT by HT and vice versa......Page 503
Higher radix FHT algorithms......Page 504
Convolution via FHT......Page 505
Negacyclic convolution via FHT......Page 508
Localized FHT algorithms......Page 509
Two-dimensional FHTs......Page 511
Discrete cosine transform (DCT) by HT......Page 512
Discrete sine transform (DST) by DCT......Page 513
Automatic generation of transform code......Page 514
Eigenvectors of the Fourier and Hartley transform *......Page 516
Prime moduli for NTTs......Page 519
Implementation of NTTs......Page 521
Convolution with NTTs......Page 526
Wavelet filters......Page 527
Implementation......Page 529
Moment conditions......Page 530
IV Fast arithmetic......Page 533
Asymptotics of algorithms......Page 535
Splitting schemes for multiplication......Page 536
Fast multiplication via FFT......Page 544
Radix/precision considerations with FFT multiplication......Page 546
The sum-of-digits test......Page 548
Binary exponentiation......Page 549
Division, square root and cube root......Page 553
Root extraction for rationals......Page 556
Divisionless iterations for the inverse a-th root......Page 558
Initial approximations for iterations......Page 561
Some applications of the matrix square root......Page 562
Goldschmidt's algorithm......Page 567
Products for the a-th root......Page 570
Divisionless iterations for polynomial roots......Page 572
Iterations and their rate of convergence......Page 575
Schröder's formula......Page 576
Householder's formula......Page 578
Dealing with multiple roots......Page 580
More iterations......Page 581
Improvements by the delta squared process......Page 583
The AGM......Page 585
The elliptic functions K and E......Page 587
AGM-type algorithms for hypergeometric functions......Page 590
Computation of......Page 594
Arctangent relations for  *......Page 602
Logarithm......Page 609
Exponential function......Page 615
Logarithm and exponential function of power series......Page 618
Simultaneous computation of logarithms of small primes......Page 620
The binary splitting algorithm for rational series......Page 623
Rectangular schemes for evaluation of power series......Page 629
The magic sumalt algorithm for alternating series......Page 633
Shift-and-add algorithms for logb(x) and bx......Page 637
CORDIC algorithms......Page 642
Recurrences......Page 647
Chebyshev polynomials......Page 657
Cylotomic polynomials, Möbius inversion, Lambert series......Page 667
Hypergeometric functions......Page 675
Continued fractions......Page 692
A variation of the iteration for the inverse......Page 703
An iteration related to the Thue constant......Page 707
An iteration related to the Golay-Rudin-Shapiro sequence......Page 708
Iterations related to the ruler function......Page 710
An iteration related to the period-doubling sequence......Page 712
Iterations related to the sum of digits......Page 716
Iterations related to the binary Gray code......Page 718
A function that encodes the Hilbert curve......Page 724
Sparse variants of the inverse......Page 727
An iteration related to the Fibonacci numbers......Page 730
Iterations related to the Pell numbers......Page 734
V Algorithms for finite fields......Page 741
Implementation of the arithmetic operations......Page 743
Modular reduction with structured primes......Page 747
The sieve of Eratosthenes......Page 750
The order of an element......Page 751
Composite modulus: the ring Z/mZ......Page 753
The Chinese Remainder Theorem (CRT)......Page 759
Quadratic residues......Page 761
Computation of a square root modulo m......Page 763
The Rabin-Miller test for compositeness......Page 765
Proving primality......Page 771
Complex moduli: GF(p2)......Page 782
Solving the Pell equation......Page 790
Multigrades *......Page 793
Properties of the convergents of 2 *......Page 794
Multiplication of hypercomplex numbers *......Page 799
The basic arithmetical operations......Page 805
Multiplication for polynomials of high degree......Page 811
Modular arithmetic with binary polynomials......Page 817
Irreducible and primitive polynomials......Page 820
The number of irreducible and primitive polynomials......Page 835
Generating irreducible polynomials from necklaces......Page 836
Irreducible and cyclotomic polynomials *......Page 838
Factorization of binary polynomials......Page 839
Linear feedback shift registers (LFSR)......Page 845
Galois and Fibonacci setup......Page 848
Generating all revbin pairs......Page 849
The number of m-sequences and De Bruijn sequences......Page 850
Auto correlation of m-sequences......Page 851
Feedback carry shift register (FCSR)......Page 852
Linear hybrid cellular automata (LHCA)......Page 854
Additive linear hybrid cellular automata......Page 859
Arithmetic and basic properties......Page 863
Minimal polynomials......Page 869
Computation of the trace vector via Newton's formula......Page 871
Solving quadratic equations......Page 873
Representation by matrices *......Page 875
Representation by normal bases......Page 877
Conversion between normal and polynomial representation......Page 885
Optimal normal bases (ONB)......Page 887
Gaussian normal bases......Page 889
Machine used for benchmarking......Page 895
The pseudo language Sprache......Page 897
The pari/gp language......Page 899
Bibliography......Page 907
Index......Page 923