Title | A History of Algorithms [electronic resource] : From the Pebble to the Microchip / edited by Jean-Luc Chabert |
---|---|
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1999 |
Connect to | http://dx.doi.org/10.1007/978-3-642-18192-4 |
Descript | IX, 524 p. 46 illus. online resource |
1 Algorithms for Arithmetic Operations -- 1.1 Sumerian Division -- 1.2 A Babylonian Algorithm for Calculating Inverses -- 1.3 Egyptian Algorithms for Arithmetic -- 1.4 Tableau Multiplication -- 1.5 Optimising Calculations -- 1.6 Simple Division by Difference on a Counting Board -- 1.7 Division on the Chinese Abacus -- 1.8 Numbers Written as Decimals -- 1.9 Binary Arithmetic -- 1.10 Computer Arithmetic -- 2 Magic Squares -- Squares with Borders -- The Marking Cells Method -- Proceeding by 2 and by 3 -- Arnauld's Borders Method -- 3 Methods of False Position -- 3.1 Mesopotamia: a Geometric False Position -- 3.2 Egypt: Problem 26 of the Rhind Papyrus -- 3.3 China: Chapter VII of the Jiuzhang Suanshu -- 3.4 India: Bh?skara and the Rule of Simple False Position -- 3.5 Qust? Ibn L?q?: A Geometric Justification -- 3.6 Ibn al-Bann?: The Method of the Scales -- 3.7 Fibonacci: the Elchatayn rule -- 3.8 Pellos: The Rule of Three and The Method of Simple False Position -- 3.9 Clavius: Solving a System of Equations -- 4 Euclid's Algorithm -- 4.1 Euclid's Algorithm -- 118 Comparing Ratios -- 4.3 Bรฉzout's Identity -- 4.4 Continued Fractions -- 4.5 The Number of Roots of an Equation -- 5 From Measuring the Circle to Calculating ? -- Geometric Approaches -- 5.1 The Circumference of the Circle -- 5.2 The Area of the Circle in the Jiuzhang Suanshu -- 5.3 The Method of Isoperimeters -- Analytic Approaches -- 5.4 Arithmetic Quadrature -- 5.5 Using Series -- 5.6 Epilogue -- 6 Newton's Methods -- The Tangent Method -- 6.1 Straight Line Approximations -- 6.2 Recurrence Formulas -- 6.3 Initial Conditions -- 6.4 Measure of Convergence -- 6.5 Complex Roots -- Newton's Polygon -- 6.6 The Ruler and Small Parallelograms -- Solving Equations by Successive Approximations -- Extraction of Square Roots -- 7.1 The Method of Heron of Alexandria -- 7.2 The Method of Theon of Alexandria -- 7.3 Mediaeval Binomial Algorithms -- Numerical Solutions of Equations -- 7.4 Al-T?siโs Tables -- 7.5 Viรจte's Method -- 7.6 Kepler's Equation -- 7.7 Bernoulli's Method of 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.4 Heun'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