Matters Computational

This book provides algorithms and ideas for computationalists. Subjects treated include low-level algorithms, bit wizardry, combinatorial generation, fast transforms like the Fourier transform, and fast arithmetic for both real numbers and finite fields. Various optimization techniques are described and the actual performance of many given implementations is examined. The focus is on material that does not usually appear in textbooks on algorithms. The implementations are done in C++ and the GP language, written for POSIX-compliant platforms such as the Linux and BSD operating systems.

Table of Contents

I Low level algorithms

1 Bit wizardry

2 Permutations and their operations

3 Sorting and searching

4 Data Structures

II Combinatorial generation

5 Conventions and considerations

6 Combinations

7 Compositions

8 Subsets

9 Mixed radix numbers

10 Permutations

11 Permutations with special properties

12 k-permutations

13 Multisets

14 Gray codes for strings with restrictions

15 Parentheses strings

16 Integer partitions

17 Set partitions

18 Necklaces and Lyndon words

19 Hadamard and conference matrices

20 Searching paths in directed graphs

iii Fast transforms

21 The Fourier transform

22 Convolution, correlation, and more FFT algorithms

23 The Walsh transform and its relatives

24 The Haar transform

25 The Hartley transform

26 Number theoretic transforms (NTTs)

27 Fast wavelet transforms

IV Fast a rithmetic

28 Fast multiplication and exponentiation

29 Root extraction

29 Root extraction

30 Iterations for the inversion of a function

31 The AGM, elliptic integrals, and algorithms for computing TI

32 Logarithm and exponential function

33 Computing the elementary functions with limited resources

34 Numerical evaluation of power series

35 Recurrences and Chebyshev polynomials

36 Hypergeometric series

37 Cyclotomic polynomials, product forms, and continued fractions

38 Synthetic Iterations

V Algorithms for fi nite fields

39 Modular arithmetic and some number theory

40 Binary polynomials

41 Shift registers

42 Binary finite fields: GF(2″‘n)

A The electronic version of the book

B Machine used for benchmarking

C The GP language

About the Author

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.