Programming for mathematicians (Universitext)/ Raymond Seroul

1. Programming Proverbs 1
1.1. Above all, no tricks! 1
1.2. Do not chewing gum while climbing stairs 2
1.3. Name that which you still don't know 2
1.4. Tomorrow, things will be better; the day after, better still
... 2
1.5. Never execute an order before it is given 3
1.6. Document today to avoid tears tomorrow 3
1.7. Descartes' Discourse on the Method 3
2. Review of Arithmetic 5
2.1. Euclidean Division 5
2.2. Numeration Systems 6
2.3. Prime Numbers 7
2.3.1. The number of primes smaller than a given real number . 8
2.4. The Greatest Common Divisor 9
2.4.1. The Bezout Theorem 10
2.4.2. Gauss's Lemma 10
2.5. Congruences 11
2.6. The Chinese Remainder Theorem 12
2.7. The Euler phi Function 14
2.8. The Theorems of Fermat and Euler 15
2.9. Wilson's Theorem 16
2.10. Quadratic Residues 17
2.11. Prime Number and Sum of Two Squares 18
2.12. The Moebius Function 19
2.13. The Fibonacci Numbers 21
2.14. Reasoning by Induction 22
2.15. Solutions of the Exercises 25
3. An Algorithmic Description Language 29
3.1. Identifiers 30
3.2. Arithmetic Expressions 31
3.2.1. Numbers 31
3.2.2. Operations 31
Table of Contents
3.2.3. Arrays 32
3.2.4. Function calls and parentheses 32
3.3. Boolean Expressions 32
3.4. Statements and their Syntax 33
3.4.1. Assignments 34
3.4.2. Conditionals 34
3.4.3. For loops 35
3.4.4. While loops 35
3.4.5. Repeat loops 35
3.4.6. Sequences of statements 36
3.4.7. Blocks of statements 36
3.4.8. Complex statements 37
3.4.9. Layout on page and control
of syntax 38
3.4.10. To what does the else belong? 40
3.4.11. Semicolons: some classical errors 40
3.5. The Semantics of Statements 42
3.5.1. Assignments 42
3.5.2. Conditionals 42
3.5.3. First translations 43
3.5.4. The boustrophedon order 45
3.5.5. The for loop 47
3.5.6. The while loop 48
3.5.7. The repeat loop 50
3.5.8. Embedded loops 51
3.6. Which Loop to Choose? 51
3.6.1. Choosing a for loop 52
3.6.2. Choosing a while loop 52
3.6.3. Choosing a repeat loop 52
3.6.4. Inspecting entrances and exits 52
3.6.5. Loops with accidents 54
3.6.6. Gaussian elimination 55
3.6.7. How to grab data 56
4. How to Create an Algorithm 59
4.1. The Trace of an Algorithm 59
4.2. First Method: Recycling Known Code 60
4.2.1. Postage stamps 60
4.2.2. How to determine whether a postage is realizable
... 61
4.2.3. Calculating the threshold value 62
4.3. Second Method: Using Sequences 64
4.3.1. Creation of a simple algorithm 66
4.3.2. The exponential series 67
4.3.3. Decomposition into prime factors 69
4.3.4. The least divisor function 71
4.3.5. Cardinality of an intersection 71
Table of Contents xi
4.3.6. The CORDIC Algorithm 74
4.4. Third Method: Deferred Writing 78
4.4.1. Calculating two bizarre functions 80
4.4.2. Storage
of the first N prime numbers 81
4.4.3. Last recommendations 84
4.5. How to Prove an Algorithm 85
4.5.1. Crashes 85
4.5.2. Infinite loops 85
4.5.3. Calculating the CCD of two numbers 86
4.5.4. A more complicated example 86
4.5.5. The validity of a result furnished by a loop 87
4.6. Solutions of the Exercises 88
5. Algorithms and Classical Constructions 91
5.1. Exchanging the Contents of Two Variables 91
5.2. Diverse Sums 92
5.2.1. A very important convention 92
5.2.2. Double sums 93
5.2.3. Sums with exceptions 94
5.3. Searching for a Maximum 95
5.4. Solving a Triangular Cramer System 96
5.5. Rapid Calculation
of Powers 97
5.6. Calculation of the Fibonacci Numbers 98
5.7. The Notion of a Stack 99
5.8. Linear Traversal of a Finite Set 101
5.9. The Lexicographic Order 102
5.9.1. Words of fixed length 102
5.9.2. Words
of variable length 104
5.10. Solutions to the Exercises 105
6. The Pascal Language 109
6.1. Storage of the Usual Objects 109
6.2. Integer Arithmetic in Pascal 110
6.2.1. Storage of integers in Pascal 110
6.3. Arrays in Pascal 113
6.4. Declaration
of an Array 114
6.5. Product Sets and Types 115
6.5.1. Product of equal sets 115
6.5.2. Product
of unequal sets 116
6.5.3. Composite types 116
6.6. The Role of Constants 117
6.7. Litter 119
6.8. Procedures 119
6.8.1. The declarative part of a procedure 120
xii fable of Contents
6.8.2. Procedure calls 121
6.8.3. Communication of a procedure with the exterior ... 122
6.9. Visibility of the Variables in a Procedure 124
6.10. Context Effects 125
6.10.1. Functions 127
6.10.2. Procedure or function? 128
6.11. Procedures: What the Program Seems To Do 129
6.11.1. Using the model 133
6.12. Solutions of the Exercises 134
7. How to Write a Program 135
7.1. Inverse of an Order 4 Matrix 135
7.1.1. The problem 136
7.1.2. Theoretical study 136
7.1.3. Writing the program 138
7.1.4. The function det 140
7.1.5. How to type a program 143
7.2. Characteristic Polynomial
of a Matrix 144
7.2.1. The program Leverrier 147
7.3. How to Write a Program 152
7.4. A Poorly Written Procedure 156
8. The Integers 159
8.1. The Euclidean Algorithm 159
8.1.1. Complexity of the Euclidean algorithm 160
8.2. The Blankinship Algorithm 161
8.3. Perfect Numbers 163
8.4. The Lowest Divisor Function 165
8.5. The Moebius Function 167
8.6. The Sieve of Eratosthenes 169
8.6.1. Formulation of the algorithm 171
8.6.2. Transforming the algorithm to a program 172
8.7. The Function pi(x) 175
8.7.1. Legendre's formula 175
8.7.2. Implementation of Legendre's formula 178
8.7.3. Meissel's formula 179
8.8. Egyptian Fractions 181
8.8.1. The program 183
8.8.2. Numerical results 186
8.9. Operations on Large Integers 187
8.9.1. Addition 187
8.9.2. Subtraction 188
8.9.3. Multiplication 189
8.9.4. Declarations 190
Table of Contents xni
8.9.5. The program 191
8.10. Division in Base b 194
8.10.1. Description of the division algorithm 194
8.10.2. Justification of the division algorithm 196
8.10.3. Effective estimates of integer parts 197
8.10.4. A good division algorithm 200
8.11. Sums of Fibonacci Numbers 200
8.12. Odd Primes as a Sum of Two Squares 203
8.13. Sums of Four Squares 207
8.14. Highly Composite Numbers 208
8.14.1. Several properties of highly composite numbers . . . 210
8.14.2. Practical investigation of highly composite integers . 212
8.15. Permutations: Johnson's'Algorithm 213
8.15.1. The program Johnson 215
8.16. The Count is Good 218
8.16.1. Syntactic trees 219
9. The Complex Numbers 225
9.1. The Gaussian Integers 225
9.1.1. Euclidean division 226
9.1.2. Irreducibles 226
9.1.3. The program 231
9.2. Bases of Numeration in the Gaussian Integers 234
9.2.1. The modulo beta map 234
9.2.2. How to find an exact system of representatives .... 235
9.2.3. Numeration system in base beta 236
9.2.4. An algorithm for expression in base beta 237
9.3. Machin Formulas 240
9.3.1. Uniqueness of a Machin formula 242
9.3.2. Proof of Proposition 9.3.1 243
9.3.3. The Todd condition is necessary 244
9.3.4. The Todd condition is sufficient 244
9.3.5. Kern's algorithm 245
9.3.6. How to get rid of the Arctangent function 249
9.3.7. Examples 251
10. Polynomials 253
10.1. Definitions 253
10.2. Degree of a Polynomial 254
10.3. How to Store a Polynomial 254
10.4. The Conventions we Adopt 256
10.5. Euclidean Division 259
10.6. Evaluation of Polynomials: Homer's Method 261
10.7. Translation and Composition 262
xiv Table of Contents
10.7.1. Change of origin 262
10.7.2. Composing polynomials 265
10.8. Cyclotomic Polynomials 265
10.8.1. First formula 266
10.8.2. Second formula 268
10.9. Lagrange Interpolation 269
10.10. Basis Change 273
10.11. Differentiation
and Discrete Taylor Formulas 275
10.11.1. Discrete differentiation 275
10.12. Newton-Girard Formulas 278
10.13. Stable Polynomials 280
10.14. Factoring a Polynomial with Integral Coefficients 286
10.14.1. Why integer (instead of rational) coefficients? . . . 286
10.14.2. Kronecker's factorization algorithm 288
10.14.3. Use of stable polynomials 290
10.14.4.
The program 291
10.14.5. Last remarks 294
11. Matrices 297
11.1. Z-Linear Algebra 297
11.1.1. The bordered matrix trick 300
11.1.2. Generators of a subgroup 301
11.1.3. The Blankinship algorithm 301
11.1.4. Hermite matrices 303
11.1.5. The program Hermite 305
11.1.6. The incomplete basis theorem 312
11.1.7. Finding a basis
of a subgroup 316
11.2. Linear Systems with Integral Coefficients 318
11.2.1. Theoretical results 318
11.2.2. The case of a matrix in column echelon form .... 318
11.2.3. General case 320
11.2.4. Case of a single equation 321
11.3. Exponential of a Matrix: Putzer's Algorithm 323
11.4. Jordan Reduction 326
11.4.1. Review 326
11.4.2. Reduction of a nilpotent endomorphism 327
11.4.3. The Pittelkow-Runckel algorithm 329
11.4.4. Justification
of the Pittelkow-Runckel algorithm . . . 332
11.4.5. A complete example 333
11.4.6. Programming 336
12. Recursion 337
12.1. Presentation 337
12.1.1. Two simple examples 337
Table of Contents xv
12.1.2. Mutual recursion 339
12.1.3. Arborescence of recursive calls 340
12.1.4. Induction and recursion 340
12.2. The Ackermann function 343
12.3. The Towers of Hanoi 345
12.4. Baguenaudier 348
12.5. The Hofstadter Function 351
12.6. How to Write a Recursive Code 352
12.6.1. Sorting by dichotomy 353
13. Elements of compiler theory 359
13.1. Pseudocode 359
13.1.1. Description of pseudocode 360
13.1.2. How to compile a pseudocode program by hand . . 365
13.1.3. Translation of a conditional 366
13.1.4. Translation of a loop 368
13.1.5. Function calls 369
13.1.6. A very efficient technique 372
13.1.7. Procedure calls 374
13.1.8. The factorial function 377
13.1.9. The Fibonacci numbers 379
13.1.10. The Hofstadter function 381
13.1.11.
The Towers of Hanoi 382
13.2. A Pseudocode Interpreter 385
13.3. How to Analyze an Arithmetic Expression 400
13.3.1. Arithmetic expressions 401
13.3.2. How to recognize an arithmetic expression 404
13.4. How to Evaluate an Arithmetic Expression 410
13.5. How to Compile an Arithmetic Expression 415
13.5.1. Polish notation 415
13.5.2. A Compiler for arithmetic expressions 420