# Programming for Mathematicians

Springer Science & Business Media, 2000 - Computers - 429 pages
The aim of this book is to teach mathematics students how to program using their knowledge of mathematics. For this they require only to know how to construct a proof. The entire book's emphasis is on "how to think" when programming. Three methods for constructing an algorithm or a program are used: a) manipulation and enrichment of existing code; b) use of recurrent sequences; c) deferral of code writing, in order to deal with one difficulty at a time. Many theorems are mathematically proved and programmed. The last chapter explains how a compiler works and shows how to compile "by hand" little (but not trivial--even recursive) programs. The book is intended for anyone who thinks mathematically and wants to program and play with mathematics.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 1 Programming Proverbs 1 12 Do not chewing gum while climbing stairs 2 15 Never execute an order before it is given 3 2 Review of Arithmetic 5 22 Numeration Systems 6 23 Prime Numbers 7 24 The Greatest Common Divisor 9 25 Congruences 11
 862 Transforming the algorithm to a program 172 87 The Function pix 175 872 Implementation of Legendres formula 178 873 Meissels formula 179 88 Egyptian Fractions 181 881 The program 183 882 Numerical results 186 89 Operations on Large Integers 187

 26 The Chinese Remainder Theorem 12 27 The Euler phi Function 14 28 The Theorems of Fermat and Euler 15 29 Wilsons Theorem 16 210 Quadratic Residues 17 211 Prime Number and Sum of Two Squares 18 212 The Moebius Function 19 213 The Fibonacci Numbers 21 214 Reasoning by Induction 22 215 Solutions of the Exercises 25 3 An Algorithmic Description Language 29 31 Identifiers 30 32 Arithmetic Expressions 31 323 Arrays 32 34 Statements and their Syntax 33 341 Assignments 34 343 For loops 35 346 Sequences of statements 36 348 Complex statements 37 349 Layout on page and control of syntax 38 3410 To what does the else belong? 40 35 The Semantics of Statements 42 353 First translations 43 354 The boustrophedon order 45 355 The for loop 47 356 The while loop 48 J 57 The repeat loop 50 358 Embedded loops 51 361 Choosing a for loop 52 365 Loops with accidents 54 366 Gaussian elimination 55 367 How to grab data 56 4 How to Create an Algorithm 59 Recycling Known Code 60 422 How to determine whether a postage is realizable 61 423 Calculating the threshold value 62 Using Sequences 64 431 Creation of a simple algorithm 66 432 The exponential series 67 433 Decomposition into prime factors 69 434 The least divisor function 71 436 The CORDIC Algorithm 74 Defered Writing 78 441 Calculating two bizarre functions 80 442 Storage of the first N prime numbers 81 443 Last recommendations 84 45 How to Prove an Algorithm 85 453 Calculating the GCD of two numbers 86 455 The validity of a result furnished by a loop 87 46 Solutions of the Exercises 88 5 Algorithms and Classical Constructions 91 52 Diverse Sums 92 522 Double sums 93 523 Sums with exceptions 94 53 Searching for a Maximum 95 54 Solving a Triangular Cramer System 96 55 Rapid Calculation of Powers 97 56 Calculation of the Fibonacci Numbers 98 57 The Notion of a Stack 99 58 Linear Traversal of a Finite Set 101 59 The Lexicographic Order 102 592 Words of variable length 104 510 Solutions to the Exercises 105 6 The Pascal Language 109 62 Integer Arithmetic in Pascal 110 63 Arrays in Pascal 113 64 Declaration of an Array 114 65 Product Sets and Types 115 652 Product of unequal sets 116 66 The Role of Constants 117 67 Litter 119 681 The declarative part of a procedure 120 682 Procedure calls 121 683 Communication of a procedure with the exterior 122 69 Visibility of the Variables in a Procedure 124 610 Context Effects 125 6101 Functions 127 6102 Procedure or function? 128 What the Program Seems To Do 129 6111 Using the model 133 612 Solutions of the Exercises 134 7 How to Write a Program 135 711 The problem 136 713 Writing the program 138 714 The function det 140 715 How to type a program 143 72 Characteristic Polynomial of a Matrix 144 721 The program Leverrier 147 73 How to Write a Program 152 74 A Poorly Written Procedure 156 8 The Integers 159 811 Complexity of the Euclidean algorithm 160 82 The Blankinship Algorithm 161 83 Perfect Numbers 163 84 The Lowest Divisor Function 165 85 The Moebius Function 167 86 The Sieve of Eratosthenes 169 861 Formulation of the algorithm 171
 892 Subtraction 188 893 Multiplication 189 894 Declarations 190 895 The program 191 810 Division in Base b 194 8102 Justification of the division algorithm 196 8103 Effective estimates of integer parts 197 8104 A good division algorithm 200 812 Odd Primes as a Sum of Two Squares 203 813 Sums of Four Squares 207 814 Highly Composite Numbers 208 8141 Several properties of highly composite numbers 210 8142 Practical investigation of highly composite integers 212 Johnsons Algorithm 213 8151 The program Johnson 215 816 The Count is Good 218 8161 Syntactic trees 219 9 The Complex Numbers 225 911 Euclidean division 226 913 The program 231 92 Bases of Numeration in the Gaussian Integers 234 922 How to find an exact system of representatives 235 923 Numeration system in base beta 236 93 Machin Formulas 240 931 Uniqueness of a Machin formula 242 932 Proof of Proposition 931 243 933 The Todd condition is necessary 244 935 Kerns algorithm 245 936 How to get rid of the Arctangent function 249 937 Examples 251 10 Polynomials 253 102 Degree of a Polynomial 254 104 The Conventions we Adopt 256 105 Euclidean Division 259 Horners Method 261 107 Translation and Composition 262 1072 Composing polynomials 265 1081 First formula 266 1082 Second formula 268 109 Lagrange Interpolation 269 1010 Basis Change 273 1011 Differentiation and Discrete Taylor Formulas 275 1012 NewtonGirard Formulas 278 1013 Stable Polynomials 280 1014 Factoring a Polynomial with Integral Coefficients 286 10142 Kroneckers factorization algorithm 288 10143 Use of stable polynomials 290 10144 The program 291 10145 Last remarks 294 11 Matrices 297 1111 The bordered matrix trick 300 1112 Generators of a subgroup 301 1114 Hermite matrices 303 1115 The program Hermite 305 1116 The incomplete basis theorem 312 1117 Finding a basis of a subgroup 316 112 Linear Systems with Integral Coefficients 318 1123 General case 320 1124 Case of a single equation 321 Putzers Algorithm 323 114 Jordan Reduction 326 1142 Reduction of a nilpotent endomorphism 327 1143 The PitttelkowRunckel algorithm 329 1144 Justification of the PittelkowRunckel algorithm 332 1145 A complete example 333 1146 Programming 336 12 Recursion 337 1212 Mutual recursion 339 1213 Arborescence of recursive calls 340 122 The Ackermann function 343 123 The Towers of Hanoi 345 124 Baguenaudier 348 125 The Hofstadter Function 351 126 How to Write a Recursive Code 352 1261 Sorting by dichotomy 353 13 Elements of compiler theory 359 1311 Description of pseudocode 360 1312 How to compile a pseudocode program by hand 365 1313 Translation of a conditional 366 1314 Translation of a loop 368 1315 Function calls 369 1316 A very efficient technique 372 1317 Procedure calls 374 1318 The factorial function 377 1319 The Fibonacci numbers 379 13110 The Hofstadter function 381 13111 The Towers of Hanoi 382 132 A Pseudocode Interpreter 385 133 How to Analyze an Arithmetic Expression 400 1331 Arithmetic expressions 401 1332 How to recognize an arithmetic expression 404 134 How to Evaluate an Arithmetic Expression 410 135 How to Compile an Arithmetic Expression 415 1352 A Compiler for arithmetic expressions 420 References 423 Index 425 Copyright