From Mathematics to Generic Programming

From Mathematics to Generic Programming

by Alexander A. Stepanov, Daniel E. Rose
Released November 2014
Publisher(s): Addison-Wesley Professional
ISBN: 9780133491791

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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

  1. About This eBook
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Acknowledgments
  6. About the Authors
  7. Authors’ Note
  8. 1. What This Book Is About
    1. 1.1 Programming and Mathematics
    2. 1.2 A Historical Perspective
    3. 1.3 Prerequisites
    4. 1.4 Roadmap
  9. 2. The First Algorithm
    1. 2.1 Egyptian Multiplication
    2. 2.2 Improving the Algorithm
    3. 2.3 Thoughts on the Chapter
  10. 3. Ancient Greek Number Theory
    1. 3.1 Geometric Properties of Integers
    2. 3.2 Sifting Primes
    3. 3.3 Implementing and Optimizing the Code
    4. 3.4 Perfect Numbers
    5. 3.5 The Pythagorean Program
    6. 3.6 A Fatal Flaw in the Program
    7. 3.7 Thoughts on the Chapter
  11. 4. Euclid’s Algorithm
    1. 4.1 Athens and Alexandria
    2. 4.2 Euclid’s Greatest Common Measure Algorithm
    3. 4.3 A Millennium without Mathematics
    4. 4.4 The Strange History of Zero
    5. 4.5 Remainder and Quotient Algorithms
    6. 4.6 Sharing the Code
    7. 4.7 Validating the Algorithm
    8. 4.8 Thoughts on the Chapter
  12. 5. The Emergence of Modern Number Theory
    1. 5.1 Mersenne Primes and Fermat Primes
    2. 5.2 Fermat’s Little Theorem
    3. 5.3 Cancellation
    4. 5.4 Proving Fermat’s Little Theorem
    5. 5.5 Euler’s Theorem
    6. 5.6 Applying Modular Arithmetic
    7. 5.7 Thoughts on the Chapter
  13. 6. Abstraction in Mathematics
    1. 6.1 Groups
    2. 6.2 Monoids and Semigroups
    3. 6.3 Some Theorems about Groups
    4. 6.4 Subgroups and Cyclic Groups
    5. 6.5 Lagrange’s Theorem
    6. 6.6 Theories and Models
    7. 6.7 Examples of Categorical and Non-categorical Theories
    8. 6.8 Thoughts on the Chapter
  14. 7. Deriving a Generic Algorithm
    1. 7.1 Untangling Algorithm Requirements
    2. 7.2 Requirements on A
    3. 7.3 Requirements on N
    4. 7.4 New Requirements
    5. 7.5 Turning Multiply into Power
    6. 7.6 Generalizing the Operation
    7. 7.7 Computing Fibonacci Numbers
    8. 7.8 Thoughts on the Chapter
  15. 8. More Algebraic Structures
    1. 8.1 Stevin, Polynomials, and GCD
    2. 8.2 Göttingen and German Mathematics
    3. 8.3 Noether and the Birth of Abstract Algebra
    4. 8.4 Rings
    5. 8.5 Matrix Multiplication and Semirings
    6. 8.6 Application: Social Networks and Shortest Paths
    7. 8.7 Euclidean Domains
    8. 8.8 Fields and Other Algebraic Structures
    9. 8.9 Thoughts on the Chapter
  16. 9. Organizing Mathematical Knowledge
    1. 9.1 Proofs
    2. 9.2 The First Theorem
    3. 9.3 Euclid and the Axiomatic Method
    4. 9.4 Alternatives to Euclidean Geometry
    5. 9.5 Hilbert’s Formalist Approach
    6. 9.6 Peano and His Axioms
    7. 9.7 Building Arithmetic
    8. 9.8 Thoughts on the Chapter
  17. 10. Fundamental Programming Concepts
    1. 10.1 Aristotle and Abstraction
    2. 10.2 Values and Types
    3. 10.3 Concepts
    4. 10.4 Iterators
    5. 10.5 Iterator Categories, Operations, and Traits
    6. 10.6 Ranges
    7. 10.7 Linear Search
    8. 10.8 Binary Search
    9. 10.9 Thoughts on the Chapter
  18. 11. Permutation Algorithms
    1. 11.1 Permutations and Transpositions
    2. 11.2 Swapping Ranges
    3. 11.3 Rotation
    4. 11.4 Using Cycles
    5. 11.5 Reverse
    6. 11.6 Space Complexity
    7. 11.7 Memory-Adaptive Algorithms
    8. 11.8 Thoughts on the Chapter
  19. 12. Extensions of GCD
    1. 12.1 Hardware Constraints and a More Efficient Algorithm
    2. 12.2 Generalizing Stein’s Algorithm
    3. 12.3 Bézout’s Identity
    4. 12.4 Extended GCD
    5. 12.5 Applications of GCD
    6. 12.6 Thoughts on the Chapter
  20. 13. A Real-World Application
    1. 13.1 Cryptology
    2. 13.2 Primality Testing
    3. 13.3 The Miller-Rabin Test
    4. 13.4 The RSA Algorithm: How and Why It Works
    5. 13.5 Thoughts on the Chapter
  21. 14. Conclusions
  22. Further Reading
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  23. Appendix A. Notation
    1. Examples
    2. Implication and the Contrapositive
  24. Appendix B. Common Proof Techniques
    1. B.1 Proof by Contradiction
    2. B.2 Proof by Induction
    3. B.3 The Pigeonhole Principle
  25. Appendix C. C++ for Non-C++ Programmers
    1. C.1 Template Functions
    2. C.2 Concepts
    3. C.3 Declaration Syntax and Typed Constants
    4. C.4 Function Objects
    5. C.5 Preconditions, Postconditions, and Assertions
    6. C.6 STL Algorithms and Data Structures
    7. C.7 Iterators and Ranges
    8. C.8 Type Aliases and Type Functions with using in C++11
    9. C.9 Initializer Lists in C++11
    10. C.10 Lambda Functions in C++11
    11. C.11 A Note about inline
  26. Bibliography
  27. Index
  28. Photo Credits
  29. Code Snippets

Product information

  • Title: From Mathematics to Generic Programming
  • Author(s): Alexander A. Stepanov, Daniel E. Rose
  • Release date: November 2014
  • Publisher(s): Addison-Wesley Professional
  • ISBN: 9780133491791