In this substantive yet accessible book, pioneering software designer Alexander Stepanov and his colleague Daniel Rose illuminate the principles of generic programming and the mathematical concept of abstraction on which it is based, helping you write code that is both simpler and more powerful.
If you’re a reasonably proficient programmer who can think logically, you have all the background you’ll need. Stepanov and Rose introduce the relevant abstract algebra and number theory with exceptional clarity. They carefully explain the problems mathematicians first needed to solve, and then show how these mathematical solutions translate to generic programming and the creation of more effective and elegant code. To demonstrate the crucial role these mathematical principles play in many modern applications, the authors show how to use these results and generalized algorithms to implement a real-world public-key cryptosystem.
As you read this book, you’ll master the thought processes necessary for effective programming and learn how to generalize narrowly conceived algorithms to widen their usefulness without losing efficiency. You’ll also gain deep insight into the value of mathematics to programming—insight that will prove invaluable no matter what programming languages and paradigms you use.
You will learn about
- How to generalize a four thousand-year-old algorithm, demonstrating indispensable lessons about clarity and efficiency
- Ancient paradoxes, beautiful theorems, and the productive tension between continuous and discrete
- A simple algorithm for finding greatest common divisor (GCD) and modern abstractions that build on it
- Powerful mathematical approaches to abstraction
- How abstract algebra provides the idea at the heart of generic programming
- Axioms, proofs, theories, and models: using mathematical techniques to organize knowledge about your algorithms and data structures
- Surprising subtleties of simple programming tasks and what you can learn from them
- How practical implementations can exploit theoretical knowledge
Table of Contents:
Acknowledgments ix
About the Authors xi
Authors’ Note xiii
Chapter 1: What This Book Is About 1
1.1 Programming and Mathematics 2
1.2 A Historical Perspective 2
1.3 Prerequisites 3
1.4 Roadmap 4
Chapter 2: The First Algorithm 7
2.1 Egyptian Multiplication 8
2.2 Improving the Algorithm 11
2.3 Thoughts on the Chapter 15
Chapter 3: Ancient Greek Number Theory 17
3.1 Geometric Properties of Integers 17
3.2 Sifting Primes 20
3.3 Implementing and Optimizing the Code 23
3.4 Perfect Numbers 28
3.5 The Pythagorean Program 32
3.6 A Fatal Flaw in the Program 34
3.7 Thoughts on the Chapter 38
Chapter 4: Euclid’s Algorithm 41
4.1 Athens and Alexandria 41
4.2 Euclid’s Greatest Common Measure Algorithm 45
4.3 A Millennium without Mathematics 50
4.4 The Strange History of Zero 51
4.5 Remainder and Quotient Algorithms 53
4.6 Sharing the Code 57
4.7 Validating the Algorithm 59
4.8 Thoughts on the Chapter 61
Chapter 5: The Emergence of Modern Number Theory 63
5.1 Mersenne Primes and Fermat Primes 63
5.2 Fermat’s Little Theorem 69
5.3 Cancellation 72
5.4 Proving Fermat’s Little Theorem 77
5.5 Euler’s Theorem 79
5.6 Applying Modular Arithmetic 83
5.7 Thoughts on the Chapter 84
Chapter 6: Abstraction in Mathematics 85
6.1 Groups 85
6.2 Monoids and Semigroups 89
6.3 Some Theorems about Groups 92
6.4 Subgroups and Cyclic Groups 95
6.5 Lagrange’s Theorem 97
6.6 Theories and Models 102
6.7 Examples of Categorical and Non-categorical Theories 104
6.8 Thoughts on the Chapter 107
Chapter 7: Deriving a Generic Algorithm 111
7.1 Untangling Algorithm Requirements 111
7.2 Requirements on A 113
7.3 Requirements on N 116
7.4 New Requirements 118
7.5 Turning Multiply into Power 119
7.6 Generalizing the Operation 121
7.7 Computing Fibonacci Numbers 124
7.8 Thoughts on the Chapter 127
Chapter 8: More Algebraic Structures 129
8.1 Stevin, Polynomials, and GCD 129
8.2 Göttingen and German Mathematics 135
8.3 Noether and the Birth of Abstract Algebra 140
8.4 Rings 142
8.5 Matrix Multiplication and Semirings 145
8.6 Application: Social Networks and Shortest Paths 147
8.7 Euclidean Domains 150
8.8 Fields and Other Algebraic Structures 151
8.9 Thoughts on the Chapter 152
Chapter 9: Organizing Mathematical Knowledge 155
9.1 Proofs 155
9.2 The First Theorem 159
9.3 Euclid and the Axiomatic Method 161
9.4 Alternatives to Euclidean Geometry 164
9.5 Hilbert’s Formalist Approach 167
9.6 Peano and His Axioms 169
9.7 Building Arithmetic 173
9.8 Thoughts on the Chapter 176
Chapter 10: Fundamental Programming Concepts 177
10.1 Aristotle and Abstraction 177
10.2 Values and Types 180
10.3 Concepts 181
10.4 Iterators 184
10.5 Iterator Categories, Operations, and Traits 185
10.6 Ranges 188
10.7 Linear Search 190
10.8 Binary Search 191
10.9 Thoughts on the Chapter 196
Chapter 11: Permutation Algorithms 197
11.1 Permutations and Transpositions 197
11.2 Swapping Ranges 201
11.3 Rotation 204
11.4 Using Cycles 207
11.5 Reverse 212
11.6 Space Complexity 215
11.7 Memory-Adaptive Algorithms 216
11.8 Thoughts on the Chapter 217
Chapter 12: Extensions of GCD 219
12.1 Hardware Constraints and a More Efficient Algorithm 219
12.2 Generalizing Stein’s Algorithm 222
12.3 Bézout’s Identity 225
12.4 Extended GCD 229
12.5 Applications of GCD 234
12.6 Thoughts on the Chapter 234
Chapter 13: A Real-World Application 237
13.1 Cryptology 237
13.2 Primality Testing 240
13.3 The Miller-Rabin Test 243
13.4 The RSA Algorithm: How and Why It Works 245
13.5 Thoughts on the Chapter 248
Chapter 14: Conclusions 249
Further Reading 251
Appendix A: Notation 257
Appendix B: Common Proof Techniques 261
B.1 Proof by Contradiction 261
B.2 Proof by Induction 262
B.3 The Pigeonhole Principle 263
Appendix C: C++ for Non-C++ Programmers 265
C.1 Template Functions 265
C.2 Concepts 266
C.3 Declaration Syntax and Typed Constants 267
C.4 Function Objects 268
C.5 Preconditions, Postconditions, and Assertions 269
C.6 STL Algorithms and Data Structures 269
C.7 Iterators and Ranges 270
C.8 Type Aliases and Type Functions with using in C++11 272
C.9 Initializer Lists in C++11 272
C.10 Lambda Functions in C++11 272
C.11 A Note about inline 273
Bibliography 275
Index 281
About the Author :
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.
