Matters Computational (eBook)

Jörg Arndt: born 1964 in Berlin, Germany. Study of theoretical physics at the University of Bayreuth, and the Technical University of Berlin, Diploma in 1995. PhD in Mathematics, supervised by Richard Brent, at the Australian National University, Canberra, in 2010.

Preface 5
Contents 7
Part I: Low level algorithms 
15 
Chapter 1:Bit wizardry 
16 
Trivia 16
Operations on individual bits 21
Operations on low bits or blocks of a word 22
Extraction of ones, zeros, or blocks near transitions 25
Computing the index of a single set bit 27
Operations on high bits or blocks of a word 28
Functions related to the base-2 logarithm 31
Counting the bits and blocks of a word 32
Words as bitsets 37
Index of the i-th set bit 39
Avoiding branches 39
Bit-wise rotation of a word 41
Binary necklaces 43
Reversing the bits of a word 47
Bit-wise zip 52
Gray code and parity 55
Bit sequency 60
Powers of the Gray code 62
Invertible transforms on words 63
Scanning for zero bytes 69
Inverse and square root modulo 2n 70
Radix -2 (minus two) representation 72
A sparse signed binary representation 75
Generating bit combinations 76
Generating bit subsets of a given word 82
Binary words in lexicographic order for subsets 84
Fibonacci words 88
Binary words and parentheses strings 92
Permutations via primitives 94
CPU instructions often missed 96
Some space filling curves 97
Chapter 2:Permutations and their operations 
116 
Basic definitions and operations 116
Representation as disjoint cycles 118
Compositions of permutations 119
In-place methods to apply permutations to data 123
Random permutations 125
The revbin permutation 132
The radix permutation 135
In-place matrix transposition 136
Rotation by triple reversal 137
The zip permutation 139
The XOR permutation 141
The Gray permutation 142
The reversed Gray permutation 145
Chapter 3:Sorting and searching 
148 
Sorting algorithms 148
Binary search 155
Variants of sorting methods 156
Searching in unsorted arrays 161
Determination of equivalence classes 162
Chapter 4:Data structures 
167 
Stack (LIFO) 167
Ring buffer 169
Queue (FIFO) 170
Deque (double-ended queue) 172
Heap and priority queue 174
Bit-array 178
Left-right array 180
Part II:Combinatorial generation 
185 
Chapter 5: 
186 
Representations and orders 186
Ranking, unranking, and counting 186
Characteristics of the algorithms 187
Optimization techniques 188
Implementations, demo-programs, and timings 188
Chapter 6:Combinations 
190 
Binomial coefficients 190
Lexicographic and co-lexicographic order 191
Order by prefix shifts (cool-lex) 194
Minimal-change order 196
The Eades-McKay strong minimal-change order 197
Two-close orderings via endo/enup moves 200
Recursive generation of certain orderings 205
Chapter 7 :Compositions 
208 
Co-lexicographic order 208
Co-lexicographic order for compositions into exactly k parts 210
Compositions and combinations 212
Minimal-change orders 213
Chapter 8:Subsets 
216 
Lexicographic order 216
Minimal-change order 218
Ordering with De Bruijn sequences 222
Shifts-order for subsets 222
k-subsets where k lies in a given range 224
Chapter 9:Mixed radix numbers 
231 
Counting (lexicographic) order 231
Minimal-change (Gray code) order 234
gslex order 238
endo order 240
Gray code for endo order 242
Fixed sum of digits 243
Chapter 10:Permutations 
246 
Factorial representations of permutations 246
Lexicographic order 256
Co-lexicographic order 257
An order from reversing prefixes 259
Minimal-change order (Heap's algorithm) 262
Lipski's Minimal-change orders 264
Strong minimal-change order (Trotter's algorithm) 268
Star-transposition order 271
Minimal-change orders from factorial numbers 272
Derangement order 278
Orders where the smallest element always moves right 281
Single track orders 285
Chapter 11:Permutations with special properties 
291 
The number of certain permutations 291
Permutations with distance restrictions 296
Self-inverse permutations (involutions) 298
Cyclic permutations 299
Chapter 12:k-permutations 
305 
Lexicographic order 306
Minimal-change order 307
Chapter 13:Multisets 
309 
Subsets of a multiset 309
Permutations of a multiset 310
Chapter 14: 
318 
List recursions 318
Fibonacci words 319
Generalized Fibonacci words 321
Run-length limited (RLL) words 324
Digit x followed by at least x zeros 325
Generalized Pell words 327
Sparse signed binary words 329
Strings with no two consecutive nonzero digits 331
Strings with no two consecutive zeros 332
Binary strings without substrings 1x1 or 1xy1 334
Chapter 15: 
337 
Co-lexicographic order 337
Gray code via restricted growth strings 339
Order by prefix shifts (cool-lex) 344
Catalan numbers 345
Increment-i RGS, k-ary Dyck words, and k-ary trees 347
Chapter 16: 
353 
Solution of a generalized problem 353
Iterative algorithm 355
Partitions into m parts 356
The number of integer partitions 358
Chapter 17: 
368 
Recursive generation 368
The number of set partitions: Stirling set numbers and Bell numbers 372
Restricted growth strings 374
Chapter 18: 
384 
Generating all necklaces 385
Lex-min De Bruijn sequence from necklaces 391
The number of binary necklaces 393
Sums of roots of unity that are zero 397
Chapter 19: 
398 
Hadamard matrices via LFSR 398
Hadamard matrices via conference matrices 400
Conference matrices via finite fields 402
Chapter 20: 
405 
Representation of digraphs 406
Searching full paths 407
Conditional search 412
Edge sorting and lucky paths 416
Gray codes for Lyndon words 417
Part III:Fast transforms 
423 
Chapter 21: 
424 
The discrete Fourier transform 424
Radix-2 FFT algorithms 425
Saving trigonometric computations 430
Higher radix FFT algorithms 432
Split-radix algorithm 439
Symmetries of the Fourier transform 442
Inverse FFT for free 444
Real-valued Fourier transforms 445
Multi-dimensional Fourier transforms 451
The matrix Fourier algorithm (MFA) 452
Chapter 22: 
454 
Convolution 454
Correlation 458
Correlation, convolution, and circulant matrices 461
Weighted Fourier transforms and convolutions 462
Convolution using the MFA 465
The z-transform (ZT) 468
Prime length FFTs 471
Chapter 23: 
473 
Transform with Walsh-Kronecker basis 473
Eigenvectors of the Walsh transform 475
The Kronecker product 476
Higher radix Walsh transforms 479
Localized Walsh transforms 482
Transform with Walsh-Paley basis 487
Sequency-ordered Walsh transforms 488
XOR (dyadic) convolution 495
Slant transform 496
Arithmetic transform 497
Reed-Muller transform 500
The OR-convolution and the AND-convolution 503
The MAX-convolution 505
Weighted arithmetic transform and subset convolution 506
Chapter 24: 
511 
The `standard' Haar transform 511
In-place Haar transform 513
Non-normalized Haar transforms 515
Transposed Haar transforms 517
The reversed Haar transform 519
Relations between Walsh and Haar transforms 521
Prefix transform and prefix convolution 524
Nonstandard splitting schemes 526
Chapter 25: 
529 
Definition and symmetries 529
Radix-2 FHT algorithms 529
Complex FFT by FHT 535
Complex FFT by complex FHT and vice versa 536
Real FFT by FHT and vice versa 537
Higher radix FHT algorithms 538
Convolution via FHT 539
Localized FHT algorithms 543
2-dimensional FHTs 544
Automatic generation of transform code 545
Eigenvectors of the Fourier and Hartley transform 547
Chapter 26: 
549 
Prime moduli for NTTs 549
Implementation of NTTs 551
Convolution with NTTs 556
Chapter 27: 
557 
Wavelet filters 557
Implementation 558
Moment conditions 560
Part IV: Fast arithmetic 
563 
Chapter 28: 
564 
Splitting schemes for multiplication 564
Fast multiplication via FFT 572
Radix/precision considerations with FFT multiplication 574
The sum-of-digits test 576
Binary exponentiation 577
Chapter 29: 
581 
Division, square root and cube root 581
Root extraction for rationals 584
Divisionless iterations for the inverse a-th root 586
Initial approximations for iterations 589
Some applications of the matrix square root 590
Goldschmidt's algorithm 595
Products for the a-th root 597
Divisionless iterations for polynomial roots 600
Chapter 30: 
601 
Iterations and their rate of convergence 601
Schröder's formula 602
Householder's formula 606
Dealing with multiple roots 607
More iterations 608
Convergence improvement by the delta squared process 612
Chapter 31: 
613 
The arithmetic-geometric mean (AGM) 613
The elliptic integrals K and E 614
Theta functions, eta functions, and singular values 618
AGM-type algorithms for hypergeometric functions 625
Computation of 629
Chapter 32: 
636 
Logarithm 636
Exponential function 641
Logarithm and exponential function of power series 644
Simultaneous computation of logarithms of small primes 646
Arctangent relations for 647
Chapter 33: 
655 
Shift-and-add algorithms for logb(x) and bx 655
CORDIC algorithms 660
Chapter 34: 
665 
The binary splitting algorithm for rational series 665
Rectangular schemes for evaluation of power series 672
The magic sumalt algorithm for alternating series 676
Chapter 35: 
680 
Recurrences 680
Chebyshev polynomials 690
Chapter 36: 
699 
Definition and basic operations 699
Transformations of hypergeometric series 702
Examples: elementary functions 708
Transformations for elliptic integrals 714
The function xx 716
Chapter 37: 
718 
Cyclotomic polynomials, Möbius inversion, Lambert series 718
Conversion of power series to infinite products 723
Continued fractions 730
Chapter 38: 
740 
A variation of the iteration for the inverse 740
An iteration related to the Thue constant 744
An iteration related to the Golay-Rudin-Shapiro sequence 745
Iteration related to the ruler function 747
An iteration related to the period-doubling sequence 748
An iteration from substitution rules with sign 752
Iterations related to the sum of digits 753
Iterations related to the binary Gray code 755
A function encoding the Hilbert curve 761
Sparse power series 764
An iteration related to the Fibonacci numbers 767
Iterations related to the Pell numbers 771
Part V: Algorithms for finite fields 
777 
Chapter 39: 
778 
Implementation of the arithmetic operations 778
Modular reduction with structured primes 782
The sieve of Eratosthenes 784
The Chinese Remainder Theorem (CRT) 786
The order of an element 788
Prime modulus: the field Z/pZ=Fp=GF(p) 790
Composite modulus: the ring Z/mZ 790
Quadratic residues 795
Computation of a square root modulo m 798
The Rabin-Miller test for compositeness 800
Proving primality 806
Complex modulus: the field GF(p2) 818
Solving the Pell equation 826
Multiplication of hypercomplex numbers 829
Chapter 40: 
836 
The basic arithmetical operations 836
Multiplying binary polynomials of high degree 841
Modular arithmetic with binary polynomials 846
Irreducible polynomials 851
Primitive polynomials 855
The number of irreducible and primitive polynomials 857
Transformations that preserve irreducibility 859
Self-reciprocal polynomials 860
Irreducible and primitive polynomials of special forms 862
Generating irreducible polynomials from Lyndon words 870
Irreducible and cyclotomic polynomials 871
Factorization of binary polynomials 872
Chapter 41: 
878 
Linear feedback shift registers (LFSR) 878
Galois and Fibonacci setup 881
Error detection by hashing: the CRC 882
Generating all revbin pairs 887
The number of m-sequences and De Bruijn sequences 887
Auto-correlation of m-sequences 889
Feedback carry shift registers (FCSR) 890
Linear hybrid cellular automata (LHCA) 892
Additive linear hybrid cellular automata 896
Chapter 42: 
900 
Arithmetic and basic properties 900
Minimal polynomials 906
Fast computation of the trace vector 909
Solving quadratic equations 910
Representation by matrices 913
Representation by normal bases 914
Conversion between normal and polynomial representation 924
Optimal normal bases (ONB) 926
Gaussian normal bases 928
Appendix A: 
935 
Appendix B 
936 
Appendix C: 
937 
Bibliography 945
Index 965