Joerg Arndt: Matters Computational
Springer, 2010


Part I    Low level algorithms  p.1

1   Bit wizardry  p.2
2   Permutations and their operations  p.102
3   Sorting and searching  p.134
4   Data structures  p.153


Part II    Combinatorial generation  p.171

5   Conventions and considerations  p.172
6   Combinations  p.176
7   Compositions  p.194
8   Subsets  p.202
9   Mixed radix numbers  p.217
10  Permutations  p.232
11  Permutations with special properties  p.277
12  k-permutations  p.291
13  Multisets  p.295
14  Gray codes for strings with restrictions  p.304
15  Parentheses strings  p.323
16  Integer partitions  p.339
17  Set partitions  p.354
18  Necklaces and Lyndon words  p.370
19  Hadamard and conference matrices  p.384
20  Searching paths in directed graphs  p.391


Part III    Fast transforms  p.409

21  The Fourier transform  p.410
22  Convolution, correlation, and more FFT algorithms  p.440
23  The Walsh transform and its relatives  p.459
24  The Haar transform  p.497
25  The Hartley transform  p.515
26  Number theoretic transforms (NTTs)  p.535
27  Fast wavelet transforms  p.543


Part IV    Fast arithmetic  p.549

28  Fast multiplication and exponentiation  p.550
29  Root extraction  p.567
30  Iterations for the inversion of a function  p.587
31  The AGM, elliptic integrals, and algorithms for computing Pi  p.599
32  Logarithm and exponential function  p.622
33  Computing the elementary functions with limited resources  p.641
34  Numerical evaluation of power series  p.651
35  Recurrences and Chebyshev polynomials  p.666
36  Hypergeometric series  p.685
37  Cyclotomic polynomials, product forms, and continued fractions  p.704
38  Synthetic Iterations  p.726


Part V    Algorithms for finite fields  p.763

39  Modular arithmetic and some number theory  p.764
40  Binary polynomials  p.822
41  Shift registers  p.864
42  Binary finite fields  p.886