Matters computational (algorithms for programmers)

Preface......Page 11
I Low level algorithms......Page 13
Trivia......Page 14
Operations on individual bits......Page 19
Operations on low bits or blocks of a word......Page 20
Extraction of ones, zeros, or blocks near transitions......Page 23
Computing the index of a single set bit......Page 25
Operations on high bits or blocks of a word......Page 26
Functions related to the base-2 logarithm......Page 29
Counting the bits and blocks of a word......Page 30
Words as bitsets......Page 35
Avoiding branches......Page 37
Bit-wise rotation of a word......Page 39
Binary necklaces......Page 41
Reversing the bits of a word......Page 45
Bit-wise zip......Page 50
Gray code and parity......Page 53
Bit sequency......Page 58
Powers of the Gray code......Page 60
Invertible transforms on words......Page 61
Scanning for zero bytes......Page 67
Inverse and square root modulo 2n......Page 68
Radix -2 (minus two) representation......Page 70
A sparse signed binary representation......Page 73
Generating bit combinations......Page 74
Generating bit subsets of a given word......Page 80
Binary words in lexicographic order for subsets......Page 82
Fibonacci words......Page 86
Binary words and parentheses strings......Page 90
Permutations via primitives......Page 92
CPU instructions often missed......Page 94
Some space filling curves......Page 95
Basic definitions and operations......Page 114
Representation as disjoint cycles......Page 116
Compositions of permutations......Page 117
In-place methods to apply permutations to data......Page 121
Random permutations......Page 123
The revbin permutation......Page 130
The radix permutation......Page 133
In-place matrix transposition......Page 134
Rotation by triple reversal......Page 135
The zip permutation......Page 137
The XOR permutation......Page 139
The Gray permutation......Page 140
The reversed Gray permutation......Page 143
Sorting algorithms......Page 146
Binary search......Page 153
Variants of sorting methods......Page 154
Searching in unsorted arrays......Page 159
Determination of equivalence classes......Page 160
Stack (LIFO)......Page 165
Ring buffer......Page 167
Queue (FIFO)......Page 168
Deque (double-ended queue)......Page 170
Heap and priority queue......Page 172
Bit-array......Page 176
Left-right array......Page 178
II Combinatorial generation......Page 183
Ranking, unranking, and counting......Page 184
Characteristics of the algorithms......Page 185
Implementations, demo-programs, and timings......Page 186
Binomial coefficients......Page 188
Lexicographic and co-lexicographic order......Page 189
Order by prefix shifts (cool-lex)......Page 192
Minimal-change order......Page 194
The Eades-McKay strong minimal-change order......Page 195
Two-close orderings via endo/enup moves......Page 198
Recursive generation of certain orderings......Page 203
Co-lexicographic order......Page 206
Co-lexicographic order for compositions into exactly k parts......Page 208
Compositions and combinations......Page 210
Minimal-change orders......Page 211
Lexicographic order......Page 214
Minimal-change order......Page 216
Shifts-order for subsets......Page 220
k-subsets where k lies in a given range......Page 222
Counting (lexicographic) order......Page 229
Minimal-change (Gray code) order......Page 232
gslex order......Page 236
endo order......Page 238
Gray code for endo order......Page 240
Fixed sum of digits......Page 241
Factorial representations of permutations......Page 244
Lexicographic order......Page 254
Co-lexicographic order......Page 255
An order from reversing prefixes......Page 257
Minimal-change order (Heap's algorithm)......Page 260
Lipski's Minimal-change orders......Page 262
Strong minimal-change order (Trotter's algorithm)......Page 266
Star-transposition order......Page 269
Minimal-change orders from factorial numbers......Page 270
Derangement order......Page 276
Orders where the smallest element always moves right......Page 279
Single track orders......Page 283
The number of certain permutations......Page 289
Permutations with distance restrictions......Page 294
Self-inverse permutations (involutions)......Page 296
Cyclic permutations......Page 297
k-permutations......Page 303
Lexicographic order......Page 304
Minimal-change order......Page 305
Subsets of a multiset......Page 307
Permutations of a multiset......Page 308
List recursions......Page 316
Fibonacci words......Page 317
Generalized Fibonacci words......Page 319
Run-length limited (RLL) words......Page 322
Digit x followed by at least x zeros......Page 323
Generalized Pell words......Page 325
Sparse signed binary words......Page 327
Strings with no two consecutive nonzero digits......Page 329
Strings with no two consecutive zeros......Page 330
Binary strings without substrings 1x1 or 1xy1......Page 332
Co-lexicographic order......Page 335
Gray code via restricted growth strings......Page 337
Order by prefix shifts (cool-lex)......Page 342
Catalan numbers......Page 343
Increment-i RGS, k-ary Dyck words, and k-ary trees......Page 345
Solution of a generalized problem......Page 351
Iterative algorithm......Page 353
Partitions into m parts......Page 354
The number of integer partitions......Page 356
Recursive generation......Page 366
The number of set partitions: Stirling set numbers and Bell numbers......Page 370
Restricted growth strings......Page 372
Necklaces and Lyndon words......Page 382
Generating all necklaces......Page 383
Lex-min De Bruijn sequence from necklaces......Page 389
The number of binary necklaces......Page 391
Sums of roots of unity that are zero......Page 395
Hadamard matrices via LFSR......Page 396
Hadamard matrices via conference matrices......Page 398
Conference matrices via finite fields......Page 400
Searching paths in directed graphs......Page 403
Representation of digraphs......Page 404
Searching full paths......Page 405
Conditional search......Page 410
Edge sorting and lucky paths......Page 414
Gray codes for Lyndon words......Page 415
III Fast transforms......Page 421
The discrete Fourier transform......Page 422
Radix-2 FFT algorithms......Page 423
Saving trigonometric computations......Page 428
Higher radix FFT algorithms......Page 430
Split-radix algorithm......Page 437
Symmetries of the Fourier transform......Page 440
Inverse FFT for free......Page 442
Real-valued Fourier transforms......Page 443
Multi-dimensional Fourier transforms......Page 449
The matrix Fourier algorithm (MFA)......Page 450
Convolution......Page 452
Correlation......Page 456
Correlation, convolution, and circulant matrices......Page 459
Weighted Fourier transforms and convolutions......Page 460
Convolution using the MFA......Page 463
The z-transform (ZT)......Page 466
Prime length FFTs......Page 469
Transform with Walsh-Kronecker basis......Page 471
Eigenvectors of the Walsh transform......Page 473
The Kronecker product......Page 474
Higher radix Walsh transforms......Page 477
Localized Walsh transforms......Page 480
Transform with Walsh-Paley basis......Page 485
Sequency-ordered Walsh transforms......Page 486
XOR (dyadic) convolution......Page 493
Slant transform......Page 494
Arithmetic transform......Page 495
Reed-Muller transform......Page 498
The OR-convolution and the AND-convolution......Page 501
The MAX-convolution......Page 503
Weighted arithmetic transform and subset convolution......Page 504
The `standard' Haar transform......Page 509
In-place Haar transform......Page 511
Non-normalized Haar transforms......Page 513
Transposed Haar transforms......Page 515
The reversed Haar transform......Page 517
Relations between Walsh and Haar transforms......Page 519
Prefix transform and prefix convolution......Page 522
Nonstandard splitting schemes......Page 524
Radix-2 FHT algorithms......Page 527
Complex FFT by FHT......Page 533
Complex FFT by complex FHT and vice versa......Page 534
Real FFT by FHT and vice versa......Page 535
Higher radix FHT algorithms......Page 536
Convolution via FHT......Page 537
Localized FHT algorithms......Page 541
2-dimensional FHTs......Page 542
Automatic generation of transform code......Page 543
Eigenvectors of the Fourier and Hartley transform......Page 545
Prime moduli for NTTs......Page 547
Implementation of NTTs......Page 549
Convolution with NTTs......Page 554
Wavelet filters......Page 555
Implementation......Page 556
Moment conditions......Page 558
IV Fast arithmetic......Page 561
Splitting schemes for multiplication......Page 562
Fast multiplication via FFT......Page 570
Radix/precision considerations with FFT multiplication......Page 572
The sum-of-digits test......Page 574
Binary exponentiation......Page 575
Division, square root and cube root......Page 579
Root extraction for rationals......Page 582
Divisionless iterations for the inverse a-th root......Page 584
Initial approximations for iterations......Page 587
Some applications of the matrix square root......Page 588
Goldschmidt's algorithm......Page 593
Products for the a-th root......Page 595
Divisionless iterations for polynomial roots......Page 598
Iterations and their rate of convergence......Page 599
Schröder's formula......Page 600
Householder's formula......Page 604
Dealing with multiple roots......Page 605
More iterations......Page 606
Convergence improvement by the delta squared process......Page 610
The arithmetic-geometric mean (AGM)......Page 611
The elliptic integrals K and E......Page 612
Theta functions, eta functions, and singular values......Page 616
AGM-type algorithms for hypergeometric functions......Page 623
Computation of......Page 627
Logarithm......Page 634
Exponential function......Page 639
Logarithm and exponential function of power series......Page 642
Simultaneous computation of logarithms of small primes......Page 644
Arctangent relations for......Page 645
Shift-and-add algorithms for logb(x) and bx......Page 653
CORDIC algorithms......Page 658
The binary splitting algorithm for rational series......Page 663
Rectangular schemes for evaluation of power series......Page 670
The magic sumalt algorithm for alternating series......Page 674
Recurrences......Page 678
Chebyshev polynomials......Page 688
Definition and basic operations......Page 697
Transformations of hypergeometric series......Page 700
Examples: elementary functions......Page 706
Transformations for elliptic integrals......Page 712
The function xx......Page 714
Cyclotomic polynomials, Möbius inversion, Lambert series......Page 716
Conversion of power series to infinite products......Page 721
Continued fractions......Page 728
A variation of the iteration for the inverse......Page 738
An iteration related to the Thue constant......Page 742
An iteration related to the Golay-Rudin-Shapiro sequence......Page 743
Iteration related to the ruler function......Page 745
An iteration related to the period-doubling sequence......Page 746
An iteration from substitution rules with sign......Page 750
Iterations related to the sum of digits......Page 751
Iterations related to the binary Gray code......Page 753
A function encoding the Hilbert curve......Page 759
Sparse power series......Page 762
An iteration related to the Fibonacci numbers......Page 765
Iterations related to the Pell numbers......Page 769
V Algorithms for finite fields......Page 775
Implementation of the arithmetic operations......Page 776
Modular reduction with structured primes......Page 780
The sieve of Eratosthenes......Page 782
The Chinese Remainder Theorem (CRT)......Page 784
The order of an element......Page 786
Composite modulus: the ring Z/mZ......Page 788
Quadratic residues......Page 793
Computation of a square root modulo m......Page 796
The Rabin-Miller test for compositeness......Page 798
Proving primality......Page 804
Complex modulus: the field GF(p2)......Page 816
Solving the Pell equation......Page 824
Multiplication of hypercomplex numbers......Page 827
The basic arithmetical operations......Page 834
Multiplying binary polynomials of high degree......Page 839
Modular arithmetic with binary polynomials......Page 844
Irreducible polynomials......Page 849
Primitive polynomials......Page 853
The number of irreducible and primitive polynomials......Page 855
Transformations that preserve irreducibility......Page 857
Self-reciprocal polynomials......Page 858
Irreducible and primitive polynomials of special forms......Page 860
Generating irreducible polynomials from Lyndon words......Page 868
Irreducible and cyclotomic polynomials......Page 869
Factorization of binary polynomials......Page 870
Linear feedback shift registers (LFSR)......Page 876
Galois and Fibonacci setup......Page 879
Error detection by hashing: the CRC......Page 880
The number of m-sequences and De Bruijn sequences......Page 885
Auto-correlation of m-sequences......Page 887
Feedback carry shift registers (FCSR)......Page 888
Linear hybrid cellular automata (LHCA)......Page 890
Additive linear hybrid cellular automata......Page 894
Arithmetic and basic properties......Page 898
Minimal polynomials......Page 904
Fast computation of the trace vector......Page 907
Solving quadratic equations......Page 908
Representation by matrices......Page 911
Representation by normal bases......Page 912
Conversion between normal and polynomial representation......Page 922
Optimal normal bases (ONB)......Page 924
Gaussian normal bases......Page 926
The electronic version of the book......Page 933
Machine used for benchmarking......Page 934
The GP language......Page 935
Bibliography......Page 943
Index......Page 963