From Mathematics to Generic Programming

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 **Alexander A. Stepanov** has been programming since 1972–first in the Soviet Union and, since emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on the foundations of programming has been supported by GE, Polytechnic University, Bell Labs, HP, SGI, Adobe, and, since 2009, A9.com, Amazon’s search 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, ranging from low-level algorithms for index compression to human—computer interaction. Rose led the Apple team that created desktop search for the Mac. He holds a Ph.D. in cognitive science and computer science from the University of California, San Diego, and a B.A. in philosophy from Harvard. Content: 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 Goettingen 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 Bezout'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 Contents 3 Note 7 What this Book is about 8 Programming and Mathematics 9 A Historical Perspective 9 Prerequisites 10 Roadmap 11 The First Algorithm 13 Egyptian Multiplication 14 Improving the Algorithm 17 Thoughts on the Chapter 21 Ancient Greek Number Theory 22 Geometric Properties of Integers 22 Sifting Primes 25 Implementing and Optimizing the Code 28 Perfect Numbers 33 The Pythagorean Program 37 A Fatal Flaw in the Program 39 Thoughts on the Chapter 43 Euclid’s Algorithm 45 Athens and Alexandria 45 Euclid’s Greatest Common Measure Algorithm 49 A Millennium without Mathematics 54 The Strange History of Zero 55 Remainder and Quotient Algorithms 57 Sharing the Code 61 Validating the Algorithm 63 Thoughts on the Chapter 65 Emergence of Modern Number Theory 66 Mersenne Primes and Fermat Primes 66 Fermat’s Little Theorem 72 Cancellation 75 Proving Fermat’s Little Theorem 80 Euler’s Theorem 82 Applying Modular Arithmetic 86 Thoughts on the Chapter 87 Abstraction in Mathematics 88 Groups 88 Monoids and Semigroups 92 Some Theorems about Groups 95 Subgroups and Cyclic Groups 98 Lagrange’s Theorem 100 Theories and Models 105 Examples of Categorical and Non-categorical Theories 107 Thoughts on the Chapter 110 Deriving a Generic Algorithm 113 Untangling Algorithm Requirements 113 Requirements on A 115 Requirements on N 118 New Requirements 120 Turning Multiply into Power 121 Generalizing the Operation 123 Computing Fibonacci Numbers 126 Thoughts on the Chapter 129 More Algebraic Structures 130 Stevin, Polynomials, and GCD 130 Göttingen and German Mathematics 136 Noether and the Birth of Abstract Algebra 141 Rings 143 Matrix Multiplication and Semirings 146 Application: Social Networks and Shortest Paths 148 Euclidean Domains 151 Fields and Other Algebraic Structures 152 Thoughts on the Chapter 153 Organizing Mathematical Knowledge 156 Proofs 156 The First Theorem 160 Euclid and the Axiomatic Method 162 Alternatives to Euclidean Geometry 165 Hilbert’s Formalist Approach 168 Peano and His Axioms 170 Building Arithmetic 174 Thoughts on the Chapter 177 Fundamental Programming Concepts 178 Aristotle and Abstraction 178 Values and Types 181 Concepts 182 Iterators 185 Iterator Categories, Operations, and Traits 186 Ranges 189 Linear Search 191 Binary Search 192 Thoughts on the Chapter 197 Permutation Algorithms 198 Permutations and Transpositions 198 Swapping Ranges 202 Rotation 205 Using Cycles 208 Reverse 213 Space Complexity 216 Memory-Adaptive Algorithms 217 Thoughts on the Chapter 218 Extensions of GCD 220 Hardware Constraints and a More Efficient Algorithm 220 Generalizing Stein’s Algorithm 223 Bézout’s Identity 226 Extended GCD 230 Applications of GCD 235 Thoughts on the Chapter 235 Real-World Application 237 Cryptology 237 Primality Testing 240 The Miller-Rabin Test 243 The RSA Algorithm: How and Why It Works 245 Thoughts on the Chapter 248 Conclusions 249 Reading 251 Notation 256 Common Proof Techniques 259 Proof by Contradiction 259 Proof by Induction 260 Pigeonhole Principle 261 C++ for Non-C++ Programmers 262 Template Functions 262 Concepts 263 Declaration Syntax & Typed Constants 264 Function Objects 265 Preconditions, Postconditions & Assertions 266 STL Algorithms & Data Structures 266 Iterators & Ranges 267 Type Aliases & Type Functions with 269 Initializer Lists in C++11 269 Lambda Functions in C++11 269 Note about inline 270 Biblio 272 Index 277 In Searching for Algorithms, Alexander Stepanov (creator of C++ STL) and Daniel Rose introduce math that can make any serious programmer more effective - and they do so in an engaging and accessible fashion, revealing how this math was first discovered, how programmers recognized its value, and the many surprising ways they have applied it. The perfect complement to Stepanov's classic Elements of Programming, Searching for Algorithms journeys through three key algorithms: multiplication; division with remainder; and adding 1. Those algorithms may sound pretty basic - even elementary school basic. But the authors show how they have played a profound role in the development of mathematics - and how, at a much deeper level, they are still essential to the work of today's programmers. In exploring these case studies, Stepanov and Rose show how to implement and read algorithms of all kinds, how to generalize them to the broadest possible set of applications, and how to define programming interfaces based on them This book is a great introduction to the core principles of generic programming for the experienced programmer. The authors work through examples showing how to analyse the requirements of an algorithm and make it as general as possible. The book includes several programming ""laws"" of particular interest to those building software components. The authors shsw how programmers can become more effective by learning about the idea of abstraction and the math it relies on. In an engaging and accessible fashion, they describe how these mathematical results were first discovered and are surprisingl