From Mathematics to Generic Programming

<p>Acknowledgments ix</p> <p>About the Authors xi</p> <p>Authors’ Note xiii</p> <p><strong>Chapter 1: What This Book Is About 1</strong></p> <p>1.1 Programming and Mathematics 2</p> <p>1.2 A Historical Perspective 2</p> <p>1.3 Prerequisites 3</p> <p>1.4 Roadmap 4</p> <p><strong>Chapter 2: The First Algorithm 7</strong></p> <p>2.1 Egyptian Multiplication 8</p> <p>2.2 Improving the Algorithm 11</p> <p>2.3 Thoughts on the Chapter 15</p> <p><strong>Chapter 3: Ancient Greek Number Theory 17</strong></p> <p>3.1 Geometric Properties of Integers 17</p> <p>3.2 Sifting Primes 20</p> <p>3.3 Implementing and Optimizing the Code 23</p> <p>3.4 Perfect Numbers 28</p> <p>3.5 The Pythagorean Program 32</p> <p>3.6 A Fatal Flaw in the Program 34</p> <p>3.7 Thoughts on the Chapter 38</p> <p><strong>Chapter 4: Euclid’s Algorithm 41</strong></p> <p>4.1 Athens and Alexandria 41</p> <p>4.2 Euclid’s Greatest Common Measure Algorithm 45</p> <p>4.3 A Millennium without Mathematics 50</p> <p>4.4 The Strange History of Zero 51</p> <p>4.5 Remainder and Quotient Algorithms 53</p> <p>4.6 Sharing the Code 57</p> <p>4.7 Validating the Algorithm 59</p> <p>4.8 Thoughts on the Chapter 61</p> <p><strong>Chapter 5: The Emergence of Modern Number Theory 63</strong></p> <p>5.1 Mersenne Primes and Fermat Primes 63</p> <p>5.2 Fermat’s Little Theorem 69</p> <p>5.3 Cancellation 72</p> <p>5.4 Proving Fermat’s Little Theorem 77</p> <p>5.5 Euler’s Theorem 79</p> <p>5.6 Applying Modular Arithmetic 83</p> <p>5.7 Thoughts on the Chapter 84</p> <p><strong>Chapter 6: Abstraction in Mathematics 85</strong></p> <p>6.1 Groups 85</p> <p>6.2 Monoids and Semigroups 89</p> <p>6.3 Some Theorems about Groups 92</p> <p>6.4 Subgroups and Cyclic Groups 95</p> <p>6.5 Lagrange’s Theorem 97</p> <p>6.6 Theories and Models 102</p> <p>6.7 Examples of Categorical and Non-categorical Theories 104</p> <p>6.8 Thoughts on the Chapter 107</p> <p><strong>Chapter 7: Deriving a Generic Algorithm 111</strong></p> <p>7.1 Untangling Algorithm Requirements 111</p> <p>7.2 Requirements on A 113</p> <p>7.3 Requirements on N 116</p> <p>7.4 New Requirements 118</p> <p>7.5 Turning Multiply into Power 119</p> <p>7.6 Generalizing the Operation 121</p> <p>7.7 Computing Fibonacci Numbers 124</p> <p>7.8 Thoughts on the Chapter 127</p> <p><strong>Chapter 8: More Algebraic Structures 129</strong></p> <p>8.1 Stevin, Polynomials, and GCD 129</p> <p>8.2 Göttingen and German Mathematics 135</p> <p>8.3 Noether and the Birth of Abstract Algebra 140</p> <p>8.4 Rings 142</p> <p>8.5 Matrix Multiplication and Semirings 145</p> <p>8.6 Application: Social Networks and Shortest Paths 147</p> <p>8.7 Euclidean Domains 150</p> <p>8.8 Fields and Other Algebraic Structures 151</p> <p>8.9 Thoughts on the Chapter 152</p> <p><strong>Chapter 9: Organizing Mathematical Knowledge 155</strong></p> <p>9.1 Proofs 155</p> <p>9.2 The First Theorem 159</p> <p>9.3 Euclid and the Axiomatic Method 161</p> <p>9.4 Alternatives to Euclidean Geometry 164</p> <p>9.5 Hilbert’s Formalist Approach 167</p> <p>9.6 Peano and His Axioms 169</p> <p>9.7 Building Arithmetic 173</p> <p>9.8 Thoughts on the Chapter 176</p> <p><strong>Chapter 10: Fundamental Programming Concepts 177</strong></p> <p>10.1 Aristotle and Abstraction 177</p> <p>10.2 Values and Types 180</p> <p>10.3 Concepts 181</p> <p>10.4 Iterators 184</p> <p>10.5 Iterator Categories, Operations, and Traits 185</p> <p>10.6 Ranges 188</p> <p>10.7 Linear Search 190</p> <p>10.8 Binary Search 191</p> <p>10.9 Thoughts on the Chapter 196</p> <p><strong>Chapter 11: Permutation Algorithms 197</strong></p> <p>11.1 Permutations and Transpositions 197</p> <p>11.2 Swapping Ranges 201</p> <p>11.3 Rotation 204</p> <p>11.4 Using Cycles 207</p> <p>11.5 Reverse 212</p> <p>11.6 Space Complexity 215</p> <p>11.7 Memory-Adaptive Algorithms 216</p> <p>11.8 Thoughts on the Chapter 217</p> <p><strong>Chapter 12: Extensions of GCD 219</strong></p> <p>12.1 Hardware Constraints and a More Efficient Algorithm 219</p> <p>12.2 Generalizing Stein’s Algorithm 222</p> <p>12.3 Bézout’s Identity 225</p> <p>12.4 Extended GCD 229</p> <p>12.5 Applications of GCD 234</p> <p>12.6 Thoughts on the Chapter 234</p> <p><strong>Chapter 13: A Real-World Application 237</strong></p> <p>13.1 Cryptology 237</p> <p>13.2 Primality Testing 240</p> <p>13.3 The Miller-Rabin Test 243</p> <p>13.4 The RSA Algorithm: How and Why It Works 245</p> <p>13.5 Thoughts on the Chapter 248</p> <p><strong>Chapter 14: Conclusions 249</strong></p> <p><strong>Further Reading 251</strong></p> <p><strong>Appendix A: Notation 257</strong></p> <p><strong>Appendix B: Common Proof Techniques 261</strong></p> <p>B.1 Proof by Contradiction 261</p> <p>B.2 Proof by Induction 262</p> <p>B.3 The Pigeonhole Principle 263</p> <p><strong>Appendix C: C++ for Non-C++ Programmers 265</strong></p> <p>C.1 Template Functions 265</p> <p>C.2 Concepts 266</p> <p>C.3 Declaration Syntax and Typed Constants 267</p> <p>C.4 Function Objects 268</p> <p>C.5 Preconditions, Postconditions, and Assertions 269</p> <p>C.6 STL Algorithms and Data Structures 269</p> <p>C.7 Iterators and Ranges 270</p> <p>C.8 Type Aliases and Type Functions with using in C++11 272</p> <p>C.9 Initializer Lists in C++11 272</p> <p>C.10 Lambda Functions in C++11 272</p> <p>C.11 A Note about inline 273</p> <p>Bibliography 275</p> <p>Index 281</p>