Programming for Mathematicians

1. Programming Proverbs.- 1.1. Above all, no tricks!.- 1.2. Do not chewing gum while climbing stairs.- 1.3. Name that which you still don't know.- 1.4. Tomorrow, things will be better; the day after, better still.- 1.5. Never execute an order before it is given.- 1.6. Document today to avoid tears tomorrow.- 1.7. Descartes' Discourse on the Method.- 2. Review of Arithmetic.- 2.1. Euclidean Division.- 2.2. Numeration Systems.- 2.3. Prime Numbers.- 2.3.1. The number of primes smaller than a given real number.- 2.4. The Greatest Common Divisor.- 2.4.1. The Bezout Theorem.- 2.4.2. Gauss's Lemma.- 2.5. Congruences.- 2.6. The Chinese Remainder Theorem.- 2.7. The Euler phi Function.- 2.8. The Theorems of Fermat and Euler.- 2.9. Wilson's Theorem.- 2.10. Quadratic Residues.- 2.11. Prime Number and Sum of Two Squares.- 2.12. The Moebius Function.- 2.13. The Fibonacci Numbers.- 2.14. Reasoning by Induction.- 2.15. Solutions of the Exercises.- 3. An Algorithmic Description Language.- 3.1. Identifiers.- 3.2. Arithmetic Expressions.- 3.2.1. Numbers.- 3.2.2. Operations.- 3.2.3. Arrays.- 3.2.4. Function calls and parentheses.- 3.3. Boolean Expressions.- 3.4. Statements and their Syntax.- 3.4.1. Assignments.- 3.4.2. Conditionals.- 3.4.3. For loops.- 3.4.4. While loops.- 3.4.5. Repeat loops.- 3.4.6. Sequences of statements.- 3.4.7. Blocks of statements.- 3.4.8. Complex statements.- 3.4.9. Layout on page and control of syntax.- 3.4.10. To what does the else belong?.- 3.4.11. Semicolons: some classical errors.- 3.5. The Semantics of Statements.- 3.5.1. Assignments.- 3.5.2. Conditionals.- 3.5.3. First translations.- 3.5.4. The boustrophedon order.- 3.5.5. The for loop.- 3.5.6. The while loop.- 3.5.7. The repeat loop.- 3.5.8. Embedded loops.- 3.6. Which Loop to Choose?.- 3.6.1. Choosing a for loop.- 3.6.2. Choosing a while loop.- 3.6.3. Choosing a repeat loop.- 3.6.4. Inspecting entrances and exits.- 3.6.5. Loops with accidents.- 3.6.6. Gaussian elimination.- 3.6.7. How to grab data.- 4. How to Create an Algorithm.- 4.1. The Trace of an Algorithm.- 4.2. First Method: Recycling Known Code.- 4.2.1. Postage stamps.- 4.2.2. How to determine whether a postage is realizable.- 4.2.3. Calculating the threshold value.- 4.3. Second Method: Using Sequences.- 4.3.1. Creation of a simple algorithm.- 4.3.2. The exponential series.- 4.3.3. Decomposition into prime factors.- 4.3.4. The least divisor function.- 4.3.5. Cardinality of an intersection.- 4.3.6. The CORDIC Algorithm.- 4.4. Third Method: Defered Writing.- 4.4.1. Calculating two bizarre functions.- 4.4.2. Storage of the first N prime numbers.- 4.4.3. Last recommendations.- 4.5. How to Prove an Algorithm.- 4.5.1. Crashes.- 4.5.2. Infinite loops.- 4.5.3. Calculating the GCD of two numbers.- 4.5.4. A more complicated example.- 4.5.5. The validity of a result furnished by a loop.- 4.6. Solutions of the Exercises.- 5. Algorithms and Classical Constructions.- 5.1. Exchanging the Contents of Two Variables.- 5.2. Diverse Sums.- 5.2.1. A very important convention.- 5.2.2. Double sums.- 5.2.3. Sums with exceptions.- 5.3. Searching for a Maximum.- 5.4. Solving a Triangular Cramer System.- 5.5. Rapid Calculation of Powers.- 5.6. Calculation of the Fibonacci Numbers.- 5.7. The Notion of a Stack.- 5.8. Linear Traversal of a Finite Set.- 5.9. The Lexicographic Order.- 5.9.1. Words of fixed length.- 5.9.2. Words of variable length.- 5.10. Solutions to the Exercises.- 6. The Pascal Language.- 6.1. Storage of the Usual Objects.- 6.2. Integer Arithmetic in Pascal.- 6.2.1. Storage of integers in Pascal.- 6.3. Arrays in Pascal.- 6.4. Declaration of an Array.- 6.5. Product Sets and Types.- 6.5.1. Product of equal sets.- 6.5.2. Product of unequal sets.- 6.5.3. Composite types.- 6.6. The Role of Constants.- 6.7. Litter.- 6.8. Procedures.- 6.8.1. The declarative part of a procedure.- 6.8.2. Procedure calls.- 6.8.3. Communication of a procedure with the exterior.- 6.9. Visibility of the Variables in a Procedure.- 6.10. Context Effects.- 6.10.1. Functions.- 6.10.2. Procedure or function?.- 6.11. Procedures: What the Program Seems To Do.- 6.11.1. Using the model.- 6.12. Solutions of the Exercises.- 7. How to Write a Program.- 7.1. Inverse of an Order 4 Matrix.- 7.1.1. The problem.- 7.1.2. Theoretical study.- 7.1.3. Writing the program.- 7.1.4. The function det.- 7.1.5. How to type a program.- 7.2. Characteristic Polynomial of a Matrix.- 7.2.1. The program Leverrier.- 7.3. How to Write a Program.- 7.4. A Poorly Written Procedure.- 8. The Integers.- 8.1. The Euclidean Algorithm.- 8.1.1. Complexity of the Euclidean algorithm.- 8.2. The Blankinship Algorithm.- 8.3. Perfect Numbers.- 8.4. The Lowest Divisor Function.- 8.5. The Moebius Function.- 8.6. The Sieve of Eratosthenes.- 8.6.1. Formulation of the algorithm.- 8.6.2. Transforming the algorithm to a program.- 8.7. The Function pi(x).- 8.7.1. Legendre's formula.- 8.7.2. Implementation of Legendre's formula.- 8.7.3. Meissel's formula.- 8.8. Egyptian Fractions.- 8.8.1. The program.- 8.8.2. Numerical results.- 8.9. Operations on Large Integers.- 8.9.1. Addition.- 8.9.2. Subtraction.- 8.9.3. Multiplication.- 8.9.4. Declarations.- 8.9.5. The program.- 8.10. Division in Base b.- 8.10.1. Description of the division algorithm.- 8.10.2. Justification of the division algorithm.- 8.10.3. Effective estimates of integer parts.- 8.10.4. A good division algorithm.- 8.11. Sums of Fibonacci Numbers.- 8.12. Odd Primes as a Sum of Two Squares.- 8.13. Sums of Four Squares.- 8.14. Highly Composite Numbers.- 8.14.1. Several properties of highly composite numbers.- 8.14.2. Practical investigation of highly composite integers.- 8.15. Permutations: Johnson's' Algorithm.- 8.15.1. The program Johnson.- 8.16. The Count is Good.- 8.16.1. Syntactic trees.- 9. The Complex Numbers.- 9.1. The Gaussian Integers.- 9.1.1. Euclidean division.- 9.1.2. Irreducibles.- 9.1.3. The program.- 9.2. Bases of Numeration in the Gaussian Integers.- 9.2.1. The modulo beta map.- 9.2.2. How to find an exact system of representatives.- 9.2.3. Numeration system in base beta.- 9.2.4. An algorithm for expression in base beta.- 9.3. Machin Formulas.- 9.3.1. Uniqueness of a Machin formula.- 9.3.2. Proof of Proposition 9.3.1.- 9.3.3. The Todd condition is necessary.- 9.3.4. The Todd condition is sufficient.- 9.3.5. Kern's algorithm.- 9.3.6. How to get rid of the Arctangent function.- 9.3.7. Examples.- 10. Polynomials.- 10.1. Definitions.- 10.2. Degree of a Polynomial.- 10.3. How to Store a Polynomial.- 10.4. The Conventions we Adopt.- 10.5. Euclidean Division.- 10.6. Evaluation of Polynomials: Horner's Method.- 10.7. Translation and Composition.- 10.7.1. Change of origin.- 10.7.2. Composing polynomials.- 10.8. Cyclotomic Polynomials.- 10.8.1. First formula.- 10.8.2. Second formula.- 10.9. Lagrange Interpolation.- 10.10. Basis Change.- 10.11. Differentiation and Discrete Taylor Formulas.- 10.11.1. Discrete differentiation.- 10.12. Newton-Girard Formulas.- 10.13. Stable Polynomials.- 10.14. Factoring a Polynomial with Integral Coefficients.- 10.14.1. Why integer (instead of rational) coefficients?.- 10.14.2. Kronecker's factorization algorithm.- 10.14.3. Use of stable polynomials.- 10.14.4. The program.- 10.14.5. Last remarks.- 11. Matrices.- 11.1. Z-Linear Algebra.- 11.1.1. The bordered matrix trick.- 11.1.2. Generators of a subgroup.- 11.1.3. The Blankinship algorithm.- 11.1.4. Hermite matrices.- 11.1.5. The program Hermite.- 11.1.6. The incomplete basis theorem.- 11.1.7. Finding a basis of a subgroup.- 11.2. Linear Systems with Integral Coefficients.- 11.2.1. Theoretical results.- 11.2.2. The case of a matrix in column echelon form.- 11.2.3. General case.- 11.2.4. Case of a single equation.- 11.3. Exponential of a Matrix: Putzer's Algorithm.- 11.4. Jordan Reduction.- 11.4.1. Review.- 11.4.2. Reduction of a nilpotent endomorphism.- 11.4.3. The Pitttelkow-Runckel algorithm.- 11.4.4. Justification of the Pittelkow-Runckel algorithm.- 11.4.5. A complete example.- 11.4.6. Programming.- 12. Recursion.- 12.1. Presentation.- 12.1.1. Two simple examples.- 12.1.2. Mutual recursion.- 12.1.3. Arborescence of recursive calls.- 12.1.4. Induction and recursion.- 12.2. The Ackermann function.- 12.3. The Towers of Hanoi.- 12.4. Baguenaudier.- 12.5. The Hofstadter Function.- 12.6. How to Write a Recursive Code.- 12.6.1. Sorting by dichotomy.- 13. Elements of compiler theory.- 13.1. Pseudocode.- 13.1.1. Description of pseudocode.- 13.1.2. How to compile a pseudocode program by hand.- 13.1.3. Translation of a conditional.- 13.1.4. Translation of a loop.- 13.1.5. Function calls.- 13.1.6. A very efficient technique.- 13.1.7. Procedure calls.- 13.1.8. The factorial function.- 13.1.9. The Fibonacci numbers.- 13.1.10. The Hofstadter function.- 13.1.11. The Towers of Hanoi.- 13.2. A Pseudocode Interpreter.- 13.3. How to Analyze an Arithmetic Expression.- 13.3.1. Arithmetic expressions.- 13.3.2. How to recognize an arithmetic expression.- 13.4. How to Evaluate an Arithmetic Expression.- 13.5. How to Compile an Arithmetic Expression.- 13.5.1. Polish notation.- 13.5.2. A Compiler for arithmetic expressions.- References.