ISBN: 3-540-63369-3 TITLE: A History of Algorithms AUTHOR: Chabert, Jean-Luc (Ed.) TOC: Introduction 1 1 Algorithms for Arithmetic Operations 7 1.1 Sumerian Division 8 1.2 A Babylonian Algorithm for Calculating Inverses 11 1.3 Egyptian Algorithms for Arithmetic 15 1.4 Tableau Multiplication 20 1.5 Optimising Calculations 28 1.6 Simple Division by Difference on a Counting Board 30 1.7 Division on the Chinese Abacus 35 1.8 Numbers Written as Decimals 37 1.9 Binary Arithmetic 40 1.10 Computer Arithmetic 43 Bibliography 46 2 Magic Squares 49 2.1 Squares with Borders 53 2.2 The Marking Cells Method 58 2.3 Proceeding by 2 and by 3 64 2.4 Arnauld's Borders Method 70 Bibliography 81 3 Methods of False Position 83 3.1 Mesopotamia: a Geometric False Position 86 3.2 Egypt: Problem 26 of the Rhind Papyrus 88 3.3 China: Chapter VII of the Jiuzhang Suanshu 91 3.4 India: Bhaskara and the Rule of Simple False Position 96 3.5 Qusta Ibn Luqa: A Geometric Justification 98 3.6 Ibn al-Banna: The Method of the Scales 101 3.7 Fibonacci: the Elchatayn rule 103 3.8 Pellos: The Rule of Three and The Method of Simple False Position 106 3.9 Clavius: Solving a System of Equations 107 Bibliography 111 4 Euclid's Algorithm 113 4.1 Euclid's Algorithm 113 4.2 Comparing Ratios 118 4.3 Bézout's Identity 122 4.4 Continued Fractions 126 4.5 The Number of Roots of an Equation 132 Bibliography 136 5 From Measuring the Circle to Calculating 139 Geometric Approaches 140 5.1 The Circumference of the Circle 140 5.2 The Area of the Circle in the Jiuzhang Suanshu 146 5.3 The Method of Isoperimeters 152 Analytic Approaches 156 5.4 Arithmetic Quadrature 156 5.5 Using Series 161 5.6 Epilogue 164 Bibliography 166 6 Newton's Methods 169 The Tangent Method 170 6.1 Straight Line Approximations 170 6.2 Recurrence Formulas 175 6.3 Initial Conditions 178 6.4 Measure of Convergence 183 6.5 Complex Roots 188 Newton's Polygon 191 6.6 The Ruler and Small Parallelograms 191 Bibliography 196 7 Solving Equations by Successive Approximations 199 Extraction of Square Roots 200 7.1 The Method of Heron of Alexandria 202 7.2 The Method of Theon of Alexandria 203 7.3 Mediaeval Binomial Algorithms 205 Numerical Solutions of Equations 208 7.4 Al-Tusi's Tables 208 7.5 Vičte's Method 213 7.6 Kepler's Equation 219 7.7 Bernoulli's Method of Recurrent Series 223 7.8 Approximation by Continued Fractions 227 Horner like Transformations of Polynomial Equations 230 7.9 The Ruffini-Budan Schema 230 Bibliography 236 8 Algorithms in Arithmetic 239 Factors and Multiples 240 8.1 The Sieve of Eratosthenes 241 8.2 Criteria For Divisibility 243 8.3 Quadratic Residues 248 Tests for Primality 251 8.4 The Converse of Fermat's Theorem 252 8.5 The Lucas Test 256 8.6 Pépin's Test 260 Factorisation Algorithms 263 8.7 Factorisation by the Difference of Two Squares 264 8.8 Factorisation by Quadratic Residues 267 8.9 Factorisation by Continued Fractions 269 The Pell-Fermat Equation 272 8.10 The Arithmetica of Diophantus 273 8.11 The Lagrange Result 275 Bibliography 280 9 Solving Systems of Linear Equations 283 9.1 Cramer's Rule 284 9.2 The Method of Least Squares 287 9.3 The Gauss Pivot Method 291 9.4 A Gauss Iterative Method 296 9.5 Jacobi's Method 300 9.6 Seidel's Method 302 9.7 Nekrasov and the Rate of Convergence 306 9.8 Cholesky's Method 310 9.9 Epilogue 314 Bibliography 315 10 Tables and Interpolation 319 10.1 Ptolemy's Chord Tables 321 10.2 Briggs and Decimal Logarithms 328 10.3 The Gregory-Newton Formula 332 10.4 Newton's Interpolation Polynomial 336 10.5 The Lagrange Interpolation Polynomial 340 10.6 An Error Upper Bound 345 10.7 Neville's Algorithm 347 Bibliography 350 11 Approximate Quadratures 353 11.1 Gregory's Formula 354 11.2 Newton's Three-Eighths Rule 356 11.3 The Newton-Cotes Formulas 357 11.4 Stirling's Correction Formulas 359 11.5 Simpson's Rule 362 11.6 The Gauss Quadrature Formulas 363 11.7 Chebyshev's Choice 367 11.8 Epilogue 369 Bibliography 370 12 Approximate Solutions of Differential Equations 373 12.1 Euler's Method 374 12.2 The Existence of a Solution 378 12.3 Runge's Methods 381 12.4 Heun's Methods 388 12.5 Kutta's Methods 392 12.6 John Adams and the Use of Finite Differences 396 12.7 Epilogue 401 Bibliography 402 13 Approximation of Functions 405 Uniform Approximation 407 13.1 Taylor's Formula 407 13.2 The Lagrange Remainder 409 13.3 Chebyshev's Polynomial of Best Approximation 412 13.4 Spline-Fitting 418 Mean Quadratic Approximation 420 13.5 Fourier Series 422 13.6 The Fast Fourier Transform 424 Bibliography 427 14 Acceleration of Convergence 429 14.1 Stirling's Method for Series 430 14.2 The Euler-Maclaurin Summation Formula 434 14.3 The Euler Constant 439 14.4 Aitken's Method 443 14.5 Richardson's Extrapolation Method 447 14.6 Romberg's Integration Method 451 Bibliography 453 15 Towards the Concept of Algorithm 455 Recursive Functions and Computable Functions 458 15.1 The 1931 Definition 458 15.2 General Gödel Recursive Functions 460 15.3 Alonzo Church and Effective Calculability 462 15.4 Recursive Functions in the Kleene Sense 466 Machines 468 15.5 The Turing Machine 468 15.6 Post's Machine 474 15.7 Conclusion 479 Bibliography 480 Biographies 481 General Index 517 Index of Names 521 END