From Mathematics to Generic Programming

Alexander A. Stepanov studied mathematics at Moscow State University from 1967 to 1972. He has been programming since 1972: first in the Soviet Union and, after emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on foundations of programming has been supported by GE, Polytechnic University, Bell Labs, HP, SGI, Adobe, and, since 2009, A9.com, Amazon’s search technology subsidiary. In 1995 he received the Dr. Dobb’s Journal Excellence in Programming Award for the design of the C++ Standard Template Library.Daniel E. Rose is a research scientist who has held management positions at Apple, AltaVista, Xigo, Yahoo, and A9.com. His research focuses on all aspects of search technology, ranging from low-level algorithms for index compression to human–computer interaction issues in web search. Rose led the team at Apple that created desktop search for the Macintosh. He holds a Ph.D. in cognitive science and computer science from University of California, San Diego, and a B.A. in philosophy from Harvard University.

• Acknowledgments ixAbout the Authors xiAuthors’ Note xiiiChapter 1: What This Book Is About 11.1 Programming and Mathematics 21.2 A Historical Perspective 21.3 Prerequisites 31.4 Roadmap 4Chapter 2: The First Algorithm 72.1 Egyptian Multiplication 82.2 Improving the Algorithm 112.3 Thoughts on the Chapter 15Chapter 3: Ancient Greek Number Theory 173.1 Geometric Properties of Integers 173.2 Sifting Primes 203.3 Implementing and Optimizing the Code 233.4 Perfect Numbers 283.5 The Pythagorean Program 323.6 A Fatal Flaw in the Program 343.7 Thoughts on the Chapter 38Chapter 4: Euclid’s Algorithm 414.1 Athens and Alexandria 414.2 Euclid’s Greatest Common Measure Algorithm 454.3 A Millennium without Mathematics 504.4 The Strange History of Zero 514.5 Remainder and Quotient Algorithms 534.6 Sharing the Code 574.7 Validating the Algorithm 594.8 Thoughts on the Chapter 61Chapter 5: The Emergence of Modern Number Theory 635.1 Mersenne Primes and Fermat Primes 635.2 Fermat’s Little Theorem 695.3 Cancellation 725.4 Proving Fermat’s Little Theorem 775.5 Euler’s Theorem 795.6 Applying Modular Arithmetic 835.7 Thoughts on the Chapter 84Chapter 6: Abstraction in Mathematics 856.1 Groups 856.2 Monoids and Semigroups 896.3 Some Theorems about Groups 926.4 Subgroups and Cyclic Groups 956.5 Lagrange’s Theorem 976.6 Theories and Models 1026.7 Examples of Categorical and Non-categorical Theories 1046.8 Thoughts on the Chapter 107Chapter 7: Deriving a Generic Algorithm 1117.1 Untangling Algorithm Requirements 1117.2 Requirements on A 1137.3 Requirements on N 1167.4 New Requirements 1187.5 Turning Multiply into Power 1197.6 Generalizing the Operation 1217.7 Computing Fibonacci Numbers 1247.8 Thoughts on the Chapter 127Chapter 8: More Algebraic Structures 1298.1 Stevin, Polynomials, and GCD 1298.2 Göttingen and German Mathematics 1358.3 Noether and the Birth of Abstract Algebra 1408.4 Rings 1428.5 Matrix Multiplication and Semirings 1458.6 Application: Social Networks and Shortest Paths 1478.7 Euclidean Domains 1508.8 Fields and Other Algebraic Structures 1518.9 Thoughts on the Chapter 152Chapter 9: Organizing Mathematical Knowledge 1559.1 Proofs 1559.2 The First Theorem 1599.3 Euclid and the Axiomatic Method 1619.4 Alternatives to Euclidean Geometry 1649.5 Hilbert’s Formalist Approach 1679.6 Peano and His Axioms 1699.7 Building Arithmetic 1739.8 Thoughts on the Chapter 176Chapter 10: Fundamental Programming Concepts 17710.1 Aristotle and Abstraction 17710.2 Values and Types 18010.3 Concepts 18110.4 Iterators 18410.5 Iterator Categories, Operations, and Traits 18510.6 Ranges 18810.7 Linear Search 19010.8 Binary Search 19110.9 Thoughts on the Chapter 196Chapter 11: Permutation Algorithms 19711.1 Permutations and Transpositions 19711.2 Swapping Ranges 20111.3 Rotation 20411.4 Using Cycles 20711.5 Reverse 21211.6 Space Complexity 21511.7 Memory-Adaptive Algorithms 21611.8 Thoughts on the Chapter 217Chapter 12: Extensions of GCD 21912.1 Hardware Constraints and a More Efficient Algorithm 21912.2 Generalizing Stein’s Algorithm 22212.3 Bézout’s Identity 22512.4 Extended GCD 22912.5 Applications of GCD 23412.6 Thoughts on the Chapter 234Chapter 13: A Real-World Application 23713.1 Cryptology 23713.2 Primality Testing 24013.3 The Miller-Rabin Test 24313.4 The RSA Algorithm: How and Why It Works 24513.5 Thoughts on the Chapter 248Chapter 14: Conclusions 249Further Reading 251Appendix A: Notation 257Appendix B: Common Proof Techniques 261B.1 Proof by Contradiction 261B.2 Proof by Induction 262B.3 The Pigeonhole Principle 263Appendix C: C++ for Non-C++ Programmers 265C.1 Template Functions 265C.2 Concepts 266C.3 Declaration Syntax and Typed Constants 267C.4 Function Objects 268C.5 Preconditions, Postconditions, and Assertions 269C.6 STL Algorithms and Data Structures 269C.7 Iterators and Ranges 270C.8 Type Aliases and Type Functions with using in C++11 272C.9 Initializer Lists in C++11 272C.10 Lambda Functions in C++11 272C.11 A Note about inline 273Bibliography 275Index 281