A History of Algorithms: From the Pebble to the Microchip

Contents......Page 4
Introduction......Page 10
1 Algorithms for Arithmetic Operations......Page 16
1.1 Sumerian Division......Page 17
1.2 A Babylonian Algorithm for Calculating Inverses......Page 20
1.3 Egyptian Algorithms for Arithmetic......Page 24
1.4 Tableau Multiplication......Page 29
1.5 Optimising Calculations......Page 37
1.6 Simple Division by Difference on a Counting Board......Page 39
1.7 Division on the Chinese Abacus......Page 44
1.8 Numbers Written as Decimals......Page 46
1.9 Binary Arithmetic......Page 49
1.10 Computer Arithmetic......Page 52
Bibliography......Page 55
2 Magic Squares......Page 58
2.1 Squares with Borders......Page 62
2.2 The Marking Cells Method......Page 67
2.3 Proceeding by 2 and by 3......Page 73
2.4 Arnauld\'s Borders Method......Page 79
Bibliography......Page 90
3 Methods of False Position......Page 92
3.1 Mesopotamia: a Geometric False Position......Page 95
3.2 Egypt: Problem 26 of the Rhind Papyrus......Page 97
3.3 China: Chapter VII of the Jiuzhang Suanshu......Page 100
3.4 India: Bhaskara and the Rule of Simple False Position......Page 105
3.5 Qusta lbn Luqa: A Geometric Justification......Page 107
3.6 lbn al-Banna: The Method of the Scales......Page 110
3.7 Fibonacci: the Elchatayn rule......Page 112
3.8 Pellos:The Rule of Three and The Method of Simple False Position......Page 115
3.9 Clavius: Solving a System of Equations......Page 116
Bibliography......Page 120
4.1 Euclid\'s Algorithm......Page 122
4.2 Comparing Ratios......Page 127
4.3 Bezout\'s Identity......Page 131
4.4 Continued Fractions......Page 135
4.5 The Number of Roots of an Equation......Page 141
Bibliography......Page 145
5 From Measuring the Circle to Calculating π......Page 148
5.1 The Circumference of the Circle......Page 149
5.2 The Area of the Circle in the Jiuzhang Suanshu......Page 155
5.3 The Method of lsoperimeters......Page 160
5.4 Arithmetic Quadrature......Page 165
5.5 Using Series......Page 170
5.6 Epilogue......Page 173
Bibliography......Page 175
6 Newton\'s Methods......Page 178
6.1 Straight Line Approximations......Page 179
6.2 Recurrence Formulas......Page 184
6.3 Initial Conditions......Page 187
6.4 Measure of Convergence......Page 192
6.5 Complex Roots......Page 197
6.6 The Ruler and Small Parallelograms......Page 200
Bibliography......Page 205
7 Solving Equations by Successive Approximations......Page 208
Extraction of Square Roots......Page 209
7.1 The Method of Heron of Alexandria......Page 211
7.2 The Method of Theon of Alexandria......Page 212
7.3 Mediaeval Binomial Algorithms......Page 214
7.4 Al-Tusi\'s Tables......Page 217
7.5 Viete\'s Method......Page 222
7.6 Kepler\'s Equation......Page 228
7.7 Bernoulli\'s Method of Recurrent Series......Page 232
7.8 Approximation by Continued Fractions......Page 236
7.9 The Ruffini-Budan Schema......Page 239
Bibliography......Page 245
8 Algorithms in Arithmetic......Page 248
Factors and Multiples......Page 249
8.1 The Sieve of Eratosthenes......Page 250
8.2 Criteria for Divisibility......Page 252
8.3 Quadratic Residues......Page 257
Tests for Primality......Page 260
8.4 The Converse of Fermat\'s Theorem......Page 261
8.5 The Lucas Test......Page 265
8.6 Pepin\'s Test......Page 269
Factorisation Algorithms......Page 272
8.7 Factorisation by the Difference of Two Squares......Page 273
8.8 Factorisation by Quadratic Residues......Page 276
8.9 Factorisation by Continued Fractions......Page 278
The Pell-Fermat Equation......Page 281
8.10 The Arithmetica of Diophantus......Page 282
8.11 The Lagrange Result......Page 284
Bibliography......Page 289
9 Solving Systems of Linear Equations......Page 292
9.1 Cramer\'s Rule......Page 293
9.2 The Method of Least Squares......Page 296
9.3 The Gauss Pivot Method......Page 300
9.4 A Gauss Iterative Method......Page 305
9.5 Jacobi\'s Method......Page 309
9.6 Seidel\'s Method......Page 311
9.7 Nekrasov and the Rate of Convergence......Page 315
9.8 Cholesky\'s Method......Page 319
9.9 Epilogue......Page 323
Bibliography......Page 324
10 Tables and Interpolation......Page 328
10.1 Ptolemy\'s Chord Tables......Page 330
10.2 Briggs and Decimal Logarithms......Page 337
10.3 The Gregory-Newton Formula......Page 341
10.4 Newton\'s Interpolation Polynomial......Page 345
10.5 The Lagrange Interpolation Polynomial......Page 349
10.6 An Error Upper Bound......Page 354
10.7 Neville\'s Algorithm......Page 356
Bibliography......Page 359
11 Approximate Quadratures......Page 362
11.1 Gregory\'s Formula......Page 363
11.2 Newton\'s Three-Eighths Rule......Page 365
11.3 The Newton-Cotes Formulas......Page 366
11.4 Stirling\'s Correction Formulas......Page 368
11.5 Simpson\'s Rule......Page 371
11.6 The Gauss Quadrature Formulas......Page 372
11.7 Chebyshev\'s Choice......Page 376
11.8 Epilogue......Page 378
Bibliography......Page 379
12 Approximate Solutions of Differential Equations......Page 382
12.1 Euler\'s Method......Page 383
12.2 The Existence of a Solution......Page 387
12.3 Runge\'s Methods......Page 390
12.4 Heun\'s Methods......Page 397
12.5 Kutta\'s Methods......Page 401
12.6 John Adams and the Use of Finite Differences......Page 405
12.7 Epilogue......Page 410
Bibliography......Page 411
13 Approximation of Functions......Page 414
13.1 Taylor\'s Formula......Page 416
13.2 The Lagrange Remainder......Page 418
13.3 Chebyshev\'s Polynomial of Best Approximation......Page 421
13.4 Spline-Fitting......Page 427
Mean Quadratic Approximation......Page 429
13.5 Fourier Series......Page 431
13.6 The Fast Fourier Transform......Page 433
Bibliography......Page 436
14 Acceleration of Convergence......Page 438
14.1 Stirling\'s Method for Series......Page 439
14.2 The Euler-Maclaurin Summation Formula......Page 443
14.3 The Euler Constant......Page 448
14.4 Aitken\'s Method......Page 452
14.5 Richardson\'s Extrapolation Method......Page 456
14.6 Romberg\'s Integration Method......Page 460
Bibliography......Page 462
15 Towards the Concept of Algorithm......Page 464
15.1 The 1931 Definition......Page 467
15.2 General Godel Recursive Functions......Page 469
15.3 Alonzo Church and Effective Calculability......Page 471
15.4 Recursive Functions in the Kleene Sense......Page 475
15.5 The Turing Machine......Page 477
15.6 Post\'s Machine......Page 483
15.7 Conclusion......Page 488
Bibliography......Page 489
Biographies......Page 490
A History of Algorithms General Index......Page 526
A History of Algorithms Index of Names......Page 530