A History of Algorithms

Recurrent Series.- 7.8 Approximation by Continued Fractions.- Horner like Transformations of Polynomial Equations.- 7.9 The Ruffini-Budan Schema.- Algorithms in Arithmetic.- Factors and Multiples.- 8.1 The Sieve of Eratosthenes.- 8.2 Criteria For Divisibility.- 8.3 Quadratic Residues.- Tests for Primality.- 8.4 The Converse of Fermat's Theorem.- 8.5 The Lucas Test.- 8.6 Pépin'sTest.- Factorisation Algorithms.- 8.7 Factorisation by the Difference of Two Squares.- 8.8 Factorisation by Quadratic Residues.- 8.9 Factorisation by Continued Fractions.- The Pell-Fermat Equation.- 8.10 The Arithmetica of Diophantus.- 8.11 The Lagrange Result.- Solving Systems of Linear Equations.- 9.1 Cramer's Rule.- 9.2 The Method of Least Squares.- 9.3 The Gauss Pivot Method.- 9.4 A Gauss Iterative Method.- 9.5 Jacobi's Method.- 9.6 Seidel's Method.- 9.7 Nekrasov and the Rate of Convergence.- 9.8 Cholesky's Method.- 9.9 Epilogue.- 10 Tables and Interpolation.- 10.1 Ptolemy's Chord Tables.- 10.2 Briggs and Decimal Logarithms.- 10.3 The Gregory-Newton Formula.- 10.4 Newton's Interpolation Polynomial.- 10.5 The Lagrange Interpolation Polynomial.- 10.6 An Error Upper Bound.- 10.7 Neville's Algorithm.- Approximate Quadratures.- 11.1 Gregory's Formula.- 11.2 Newton's Three-Eighths Rule.- 11.3 The Newton-Cotes Formulas.- 11.4 Stirling's Correction Formulas.- 11.5 Simpson's Rule.- 11.6 The Gauss Quadrature Formulas.- 11.7 Chebyshev's Choice.- 11.8 Epilogue.- Approximate Solutions of Differential Equations.- 12.1 Euler's Method.- 12.2 The Existence of a Solution.- 12.3 Runge's Methods.- 12.4Heun's Methods.- 12.5 Kutta's Methods.- 12.6 John Adams and the Use of Finite Differences.- 12.7 Epilogue.- 13 Approximation of Functions.- Uniform Approximation.- 13.1 Taylor's Formula.- 13.2 The Lagrange Remainder.- 13.3 Chebyshev's Polynomial of Best Approximation.- 13.4 Spline-Fitting.- Mean Quadratic Approximation.- 13.5 Fourier Series.- 13.6 The Fast Fourier Transform.- 14 Acceleration of Convergence.- 14.1 Stirling's Method for Series.- 14.2 The Euler-Maclaurin Summation Formula.- 14.3 The Euler Constant.- 14.4 Aitken's Method.- 14.5 Richardson's Extrapolation Method.- 14.6 Romberg's Integration Method.- 15 Towards the Concept of Algorithm.- Recursive Functions and Computable Functions.- 15.1 The 1931 Definition.- 15.2 General Gödel Recursive Functions.- 15.3 Alonzo Church and Effective Calculability.- 15.4 Recursive Functions in the Kleene Sense.- Machines.- 15.5 The Turing Machine.- 15.6 Post's Machine.- 15.7 Conclusion.- Biographies.- General Index.- Index of Names.