Ebook: 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.

---

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.

---

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.
Content:
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(2n)....Pages 886-920
Back Matter....Pages 921-966

---

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.
Content:
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(2n)....Pages 886-920
Back Matter....Pages 921-966
....