From Mathematics to Generic Programming

by ;
  • ISBN13:


  • ISBN10:


  • Edition: 1st
  • Format: Paperback
  • Copyright: 11/7/2014
  • Publisher: Addison-Wesley Professional
  • Purchase Benefits
  • Free Shipping On Orders Over $59!
    Your order must be $59 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $39.99 Save up to $6.00
  • Buy New


Supplemental Materials

What is included with this book?

  • The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
  • The eBook copy of this book is not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.


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


Author Biography

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 programmer and 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 UC San Diego, and a B.A. in Philosophy from Harvard University.

Table of Contents


About the Authors

Authors’ Note


Chapter 1: What This Book Is About

1.1 Programming and Mathematics

1.2 A Historical Perspective

1.3 Prerequisites

1.4 Roadmap


Chapter 2: The First Algorithm

2.1 Egyptian Multiplication

2.2 Improving the Algorithm

2.3 Thoughts on the Chapter


Chapter 3: Ancient Greek Number Theory

3.1 Geometric Properties of Integers

3.2 Sifting Primes

3.3 Implementing and Optimizing the Code

3.4 Perfect Numbers

3.5 The Pythagorean Program

3.6 A Fatal Flaw in the Program

3.7 Thoughts on the Chapter


Chapter 4: Euclid’s Algorithm

4.1 Athens and Alexandria

4.2 Euclid’s Greatest Common Measure Algorithm

4.3 A Millennium Without Mathematics

4.4 The Strange History of Zero

4.5 Remainder and Quotient Algorithms

4.6 Sharing the Code

4.7 Validating the Algorithm

4.8 Thoughts on the Chapter


Chapter 5: The Emergence of Modern Number Theory

5.1 Mersenne Primes and Fermat Primes

5.2 Fermat’s Little Theorem

5.3 Cancellation

5.4 Proving Fermat’s Little Theorem

5.5 Euler’s Theorem

5.6 Applying Modular Arithmetic

5.7 Thoughts on the Chapter


Chapter 6: Abstraction in Mathematics

6.1 Groups

6.2 Monoids and Semigroups

6.3 Some Theorems About Groups

6.4 Subgroups and Cyclic Groups

6.5 Lagrange’s Theorem

6.6 Theories and Models

6.7 Examples of Categorical and Non-Categorical Theories

6.8 Thoughts on the Chapter


Chapter 7: Deriving a Generic Algorithm

7.1 Untangling Algorithm Requirements

7.2 Requirements on A

7.3 Requirements on N

7.4 New Requirements

7.5 Turning Multiply Into Power

7.6 Generalizing the Operation

7.7 Computing Fibonacci Numbers

7.8 Thoughts on the Chapter


Chapter 8: More Algebraic Structures

8.1 Stevin, Polynomials, and GCD

8.2 Göttingen and German Mathematics

8.3 Noether and the Birth of Abstract Algebra

8.4 Rings

8.5 Matrix Multiplication and Semirings

8.6 Application: Social Networks and Shortest Paths

8.7 Euclidean Domains

8.8 Fields and Other Algebraic Structures

8.9 Thoughts on the Chapter


Chapter 9: Organizing Mathematical Knowledge

9.1 Proofs

9.2 The First Theorem

9.3 Euclid and the Axiomatic Method

9.4 Alternatives to Euclidean Geometry

9.5 Hilbert’s Formalist Approach

9.6 Peano and His Axioms

9.7 Building Arithmetic

9.8 Thoughts on the Chapter


Chapter 10: Fundamental Programming Concepts

10.1 Aristotle and Abstraction

10.2 Values and Types

10.3 Concepts

10.4 Iterators

10.5 Iterator Categories, Operations, and Traits

10.6 Ranges

10.7 Linear Search

10.8 Binary Search

10.9 Thoughts on the Chapter


Chapter 11: Permutation Algorithms

11.1 Permutations and Transpositions

11.2 Swapping Ranges

11.3 Rotation

11.4 Using Cycles

11.5 Reverse

11.6 Space Complexity

11.7 Memory-Adaptive Algorithms

11.8 Thoughts on the Chapter


Chapter 12: Extensions of GCD

12.1 Hardware Constraints and a More Efficient Algorithm

12.2 Generalizing Stein’s Algorithm

12.3 Bézout’s Identity

12.4 Extended GCD

12.5 Applications of GCD

12.6 Thoughts on the Chapter


Chapter 13: A Real-World Application

13.1 Cryptology

13.2 Primality Testing

13.3 The Miller-Rabin Test

13.4 The RSA Algorithm: How and Why It Works

13.5 Thoughts on the Chapter


Chapter 14: Conclusions


Further Reading


Appendix A: Notation


Appendix B: Common Proof Techniques

B.1 Proof by Contradiction

B.2 Proof by Induction

B.3 The Pigeonhole Principle


Appendix C: C++ For Non-C++ Programmers

C.1 Template Functions

C.2 Concepts

C.3 Declaration Syntax and Typed Constants

C.4 Function Objects

C.5 Preconditions, Postconditions, and Assertions

C.6 STL Algorithms and Data Structures

C.7 Iterators and Ranges

C.8 Type aliases and type functions with using in C++11

C.9 Initializer lists in C++11

C.10 Lambda functions in C++11

C.11 A Note About inline




Rewards Program

Write a Review