Matters Computational : Ideas, Algorithms, Source Code

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. --Book Jacket Front Matter....Pages i-xiv Front Matter....Pages 1-1 Bit wizardry....Pages 2-101 Permutations and their operations....Pages 102-133 Sorting and searching....Pages 134-152 Data structures....Pages 153-170 Front Matter....Pages 171-171 Conventions and considerations....Pages 172-175 Combinations....Pages 176-193 Compositions....Pages 194-201 Subsets....Pages 202-216 Mixed radix numbers....Pages 217-231 Permutations....Pages 232-276 Permutations with special properties....Pages 277-290 k-permutations....Pages 291-294 Multisets....Pages 295-303 Gray codes for strings with restrictions....Pages 304-322 Parentheses strings....Pages 323-338 Integer partitions....Pages 339-353 Set partitions....Pages 354-369 Necklaces and Lyndon words....Pages 370-383 Hadamard and conference matrices....Pages 384-390 Searching paths in directed graphs....Pages 391-408 Front Matter....Pages 409-409 The Fourier transform....Pages 410-439 Convolution correlation and more FFT algorithms....Pages 440-458 The Walsh transform and its relatives....Pages 459-496 The Haar transform....Pages 497-514 The Hartley transform....Pages 515-534 Number theoretic transforms (NTTs)....Pages 535-542 Fast wavelet transforms....Pages 543-548 Front Matter....Pages 549-549 Fast multiplication and exponentiation....Pages 550-566 Root extraction....Pages 567-586 Iterations for the inversion of a function....Pages 587-598 The AGM, elliptic integrals, and algorithms for computing π....Pages 599-621 Logarithm and exponential function....Pages 622-640 Computing the elementary functions with limited resources....Pages 641-650 Numerical evaluation of power series....Pages 651-665 Recurrences and Chebyshev polynomials....Pages 666-684 Hypergeometric series....Pages 685-703 Cyclotomic polynomials product forms and continued fractions....Pages 704-725 Synthetic Iterations ‡....Pages 726-762 Front Matter....Pages 763-763 Modular arithmetic and some number theory....Pages 764-821 Binary polynomials....Pages 822-863 Front Matter....Pages 763-763 Shift registers....Pages 864-885 Binary finite fields: GF(2 n )....Pages 886-920 Back Matter....Pages 921-966 Aimed at anyone with an interest in computation and algorithms, this comprehensive text explains underlying principles, presents the algorithms, and discusses various optimization techniques as well as the performance of a number of implementations.