Programming for Mathematicians

Front Cover
Springer Science & Business Media, 2000 - Computers - 429 pages
0 Reviews
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

Other editions - View all

Common terms and phrases

References to this book