Ideas, Algorithms, Source Code
1234567

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.

You can also buy a printed version.

Jörg Arndt

Interests

  • Basic combinatorics (generation and enumeration)
  • Basic number theory and finite fields (computational and algebraic aspects)
  • q-series, modular equations, functional equations
  • Iteration schemes for root-finding (Newton's method and higher order algorithms)
  • Fast orthogonal transforms (Fourier-, Hartley-, Walsh-Hadamard-, and similar transforms)
  • Low level and arithmetical algorithms

  1. Bit wizardry p.2
  2. Permutations and their operations p.102
  3. Sorting and searching p.134
  4. Data structures p.153
  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
  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
  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
  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