* (operator), mathematical convention for, 115
+ (plus sign), mathematical convention for, 115
α. See Aliquot sum
ϕ. See Euler totient function
σ (sum of divisors) formula, 31
Euclidean domains, 150–151, 153
groups, 85–88, 92–95, 108, 152
monoids, 89, 108–109, 152, 154
semigroups, 90–91, 108–109, 152
Abstraction
Addition
commutativity of, 155–156, 174–175
definition, 173
Addition chains, 11
Additive groups, 86
Address, 181
Adleman, Len, 239
advance, 190
Agrawal, Manindra, 244
Ahmes algorithm. See Egyptian multiplication, Egyptian division
Alexander the Great, 43, 178–179
Algebraic integers, 140
Algebraic structures, 85. See also Abstract algebra
Algorithms
definition, 7
domain or setting, 150
first recorded, 8
generalizing, 111, 119–123, 126–127, 151
performance in practice, 211
Aliases, 272
Aliquot sum, 31
Analytical Mechanics, 99
APL, 124
Apology, 43
Archimedes
on acquiring mathematical knowledge, 176
axiom of, 47
place in history, 50
Aristophanes, 42
Aristoxenus, 17
Arithmétique, 132
The Art of Computer Programming, 9
Aryabhata, 51
Aryabhatiya, 51
Assertions, 269
Associative binary operation (), 108
in monoids, 89
in semigroups, 90
Associativity axiom, semigroups, 91
Associativity of addition, 9, 113
definition, 174
visual proof, 156
Associativity of multiplication, visual proof, 157
Asymmetric keys, 238
Automorphism, 104
Averroes. See Ibn Rushd
Axiom of Archimedes, 47
Axioms
definition, 163
Hilbert’s, 167
Bachet de Méziriac, Claude Gaspar, 67, 235
Backus, John, 124
Bartels, Martin, 165
Bernoulli, Johann, 69
Bidirectional iterators, 185
Binary search, 191–196. See also Partition points
Bletchley Park, 238
Bolyai, Farkas, 166
Bolyai, János, 166
Bolzano-Cauchy Theorem. See IVT (Intermediate Value Theorem)
Boolean semirings, 148
bsearch, 192
C++11, 57, 187, 195, 265, 272–273
The C++ Programming Language, 265, 270
C++ Standard Template Library. See STL
Caesar cipher, 237
Cancellation
inverse numbers, 73
Carmichael numbers, 242
Cartesian coordinates, 131, 138
Cataldi, Peter, 64
Categorical theories
vs. STL, 104
definition, 104
Category dispatch, 188, 190, 196, 213
Cayley’s Theorem, 198
Chinese mathematics, 51
Chrystal, George, 34
Cicero, 50
Ciphertext, 238
Closed ranges, 188
Clouds, 42
Cocks, Clifford, 240
Codes, definition, 237
Cogitata Physico Mathematica, 64
Colossus machine, 238
Common measure of segments, 33
Common notions, Euclid’s axiomatic method, 162
Commutative algebra, rings, 143–144
Commutativity of addition, 155–156, 174–175
Commutativity of multiplication, visual proof, 156
Commutativity of powers, semigroups, 91
Compile-time dispatch. See Category dispatch
Completeness, theories, 102
Composite numbers. See also Prime numbers
definition, 21
distinguishing from prime, 240–245
Concepts
and abstract algebra, 141
definition, 181
choosing, 250
naming conventions, 183
requirements on types, 24, 182
Semiregular
, 184
Consistency, theories, 102, 104
Constructivists, 229
Contradiction, proof by, 35, 261–262
Contrapositive, 259
Coprime, 31, 78, 80–81, 246–247
Cosets, 97. See also Lagrange’s Theorem
Cryptology
asymmetric keys, 238
Bletchley Park, 238
Caesar cipher, 237
ciphertext, 238
codes, definition, 237
Colossus machine, 238
cryptography, 237
cryptosystems, 238
Enigma machine, 238
keys, 238
Lorenz machine, 238
plaintext, 238
public-key cryptosystems, 239–240
RSA algorithm, 239–240, 245–247
symmetric keys, 238
trapdoor one-way functions, 239
Cryptosystems, 238
Cycles, of permutations, 200, 207–211
generator, 96
Cyclic subgroups, 96
Datum, 180
Declaration syntax, 267
Degree of polynomials, 133
Dereferencing, iterators, 184–185
Difference of powers formula, 30
Difference type, iterators, 187
difference_type iterator trait, 187
Differential Calculus, 70
Diffie, Whitfield, 239
Dirichlet, Peter Gustav Lejeune, 41, 139–140, 156
Dirichlet principle. See Pigeonhole principle
Disme: The Art of Tenths, 129–131
Disquisitiones Arithmeticae (“Investigations of Arithmetic”), 136–137
distance, 186-188
divides, 240
Dividing polynomials, 133
Domain of algorithm, 150
Domain of definition, 113
Doubly linked lists, 185
Egyptian division, 57
generalizing to power, 120
Elements (of Euclid), 2, 21, 43–45, 161–163
Proposition [VII, 30], 70
Proposition [VII, 32], 21
Proposition [IX, 36], 29, 31–32
Proposition [X, 2], 45
Proposition [X, 117], 37
Elements of Programming, 3, 113–114, 183, 185, 208
Enigma machine, 238
Equational reasoning, 114
Equivalence, 114
Eratosthenes, 22
Euclid. See also Elements
GCM (greatest common measure) algorithm, 45–49
incommensurable quantities, 45–49
on number theory, 21
Euclidean domains (ED), 150–151, 153
Euclidean geometry
vs. hyperbolic geometry, 164–167
Euclidean rings. See Euclidean domains (ED)
and Lagrange, 99
Euler totient function, 80, 245
proof using Lagrange’s Theorem, 101
Even and odd numbers, 9–10, 117
Existence of zero axiom, 172
Extended GCD algorithm, 229–235, 245, 247
extended_gcd, 233
Fast-multiplication algorithm. See Egyptian multiplication
Fermat’s Last Theorem, 67
Fermat’s Little Theorem
description, 69
non-invertibility lemma, 79
proof by Lagrange’s Theorem, 101
proof, 77
testing for prime numbers, 241–242
restatement using modular arithmetic, 84
fermat_test, 242
Fibonacci. See Leonardo Pisano
Fibonacci numbers, computing, 124–127
Fields
characteristic of, 151
extensions, 151
Fifth postulate of Euclidean geometry, 163–164
Figurate numbers
gnomons, 20
oblong numbers, 19
triangular numbers, 19
square numbers, 20
find_if_n, 191
Finite axiomatizability of theories, 102
Flowers, Tommy, 238
Floyd, Robert, 58
Formalist philosophy of mathematics, 167–169
Formulario Mathematico, 170–172
Forward iterators, 185
FP, 124
Function objects, 123–124, 268, 270
Functors. See Function objects
Galois, Évariste
Gauss, Carl Friedrich, 31, 72, 136–140, 166, 240
Gaussian integers, 138–139, 224
applications of, 234
of polynomials, 134
description, 59
computing, 59
extended GCD, 229–235, 245, 247
historical milestones, 222
and rational arithmetic, 234
rotation algorithms, 234
symbolic integration, 234
GCM (greatest common measure) 33, 41
properties, 33
Generator elements in subgroups, 96
Generic programming
concepts, 181
and mathematics, 84
get_temporary_buffer, 217
Gnomons, 20
Gödel, Kurt, 169
Granville, Andrew, 244
Grassman, Hermann, 171
Greatest common divisor (GCD). See GCD (greatest common divisor)
Greatest common measure (GCM). See GCM (greatest common measure)
Gries, David, 205
Gries-Mills algorithm, 204–208
additive, 86
binary operations, 86
definition, 85
discovery of, 85
identity elements, 86
inverse operations, 86
Klein group, 106
order of elements, 94
symmetric, 198
half, 118
Hegel, G.W.F., 111
Hellman, Martin, 239
Hilbert, David, 141, 167–169, 229
Hilbert’s problems, 169
Hilbert’s program, 169
History of Algebra, 129
Horner’s rule, 132
Ibn Rushd, 180
Ideals. See also Rings
definition, 226
ideals in Euclidean domains lemma, 227
linear combination ideal lemma, 227
PID (principal ideal domains), 228
principal elements, 227
Ideals in Euclidean domains lemma, 227
Identity element, 108–109, 121
in groups, 86
in monoids, 89
in rings, 143
Immutable objects, 181
Impossibility of infinite descent, 21
Inclusion-exclusion principle, 82–83
Incommensurable quantities, 45–49
Independence, theories, 102
Indian mathematics, 51
Induction axiom, 21, 170, 172–173
Inman, Bobby Ray, 240
Inner product of two vectors, 145–146
Input iterators, 185
Integral Calculus, 70
Interface refinement, law of, 215
Interfaces, designing, 215
Interlingua, 171
Intermediate Value Theorem (IVT), 131, 192
Introduction to Analysis of the Infinite, 70
Introduction to Arithmetic, 10, 19
Intuitionist philosophy of mathematics, 229
Inverse numbers, 73
inverse_operation, 123
Inverse operation, 86, 119, 121
in groups, 86
Invertibility lemma, 229
Invertibility of successor axiom, 173
Invertible elements. See Units
is_prime, 241
Iterator categories
bidirectional, 185
forward, 185
input, 185
output, 186
random-access, 185
Iterator traits, 187
iterator_category iterator trait, 187
Iterators
in arrays, 185
bidirectional, 185
definition, 184
difference type, 187
finding the distance between, 186–187
forward, 185
input, 185
in noncontiguous data segments, 186
linked, 186
output, 186
random access, 185
segmented, 186
successors, 184
Iverson, Kenneth, 124
IVT (Intermediate Value Theorem), 131, 192
Kapur, Deepak, 124
Kayal, Neeraj, 244
Keys, cryptography, 238
Khayyam, Omar, 164
Kovalevskaya, Sofia, 141
Lagrange, Joseph-Louis, 99–100, 192
Lagrange’s Theorem, 97–99, 100–101
Lambda expressions, 195, 272–273
Laplace, Pierre-Simon, 70
largest_doubling, 54
Latine sine Flexione, 171
Law of interface refinement, 215
Law of separating types, 202–203
Law of useful return, 57–58, 201–202, 213
Lectures on Number Theory (Vorlesungen über Zahlentheorie), 140
Legendre, Adrien-Marie, 155
Lehmer, D. H., 192
introduction of zero, 52
Letters to a German Princess, 70
Liber Abaci, 52
Liber Quadratorum, 52
Library of Alexandra, 43
Lincoln, Abraham, 44
Linear algebra
matrix-matrix product, 146
matrix-vector product, 146
Linear combination ideal lemma, 227
Linear recurrence functions, 127
Linear recurrence sequences, 127
Linked iterators, 186
Liu, Hui, 51
Lorenz machine, 238
Lyceum, 179
mark_sieve, 24
Math notation in this book, 257–259
Matrix multiplication, 145–147
Matrix-matrix product, 146
Matrix-vector product, 146
Mauchly, John, 192
McJones, Paul, 3
Measure of a segment, 33
Memory-adaptive algorithms, 216–217
Meno, 43
Metaphysics, 179
miller_rabin_test, 243
Mills, Harlan, 205
definition, 103
Modern Algebra, 142
Modular arithmetic, 72–74, 83–84
Fermat’s Little Theorem, 83–84
Wilson’s Theorem, 83
modulo_multiply, 241
Monoids. See also Groups
definition, 89
examples of, 89
Mouseion, 43
Multiplication
Russian Peasant Algorithm. 9
Multiplicative functions, 31
multiplicative_inverse, 121, 247
multiplicative_inverse_fermat, 241
Multiplicative monoids, 89
Multiplicative semigroups, 90
Multiply-accumulate function, 11–14
Musser, David R., 124
Mutable objects, 181
Naming conventions, concepts, 183
Natural numbers, 147, 170, 172, 175, 258
Nicomachean Ethics, 179
Nine Chapters on the Mathematical Art, 51
Non-categorical theories, 106–107
Noncommutative additive monoids, 119
Noncommutative additive semigroups, 115
Noncommutative algebra, rings, 143–144
Nonconstructive proofs, 229
Noncontiguous data segments, iterators, 186
Non-Euclidean geometry, 164–167
Non-invertibility lemma, 79
Notation in this book, 257–259
Number line, 131
Number of assignments theorem, 200–201
Number systems, ancient Egypt, 8
Fermat’s Little Theorem 69–78, 101
and GCD, 140
Liber Quadratorum, 53
17th and 18th century, 63–72, 74–84
Object types, definition, 181
Objects
definition, 180
immutable, 181
mutable, 181
remote parts, 181
unrestricted, 181
Oblong numbers, 19
Octonions, 151
odd, 118
Odd numbers. See Even and odd numbers
One-to-one correspondence, 92
Open ranges, 188
“Operators and Algebraic Structures,” 124
Order of group elements, 94
Organon, 180
Output iterators, 186
Palindromic primes, 28
Parallel postulate. See Fifth postulate of Euclidean geometry
Partition points, 193
partition_point, 194
partition_point_n, 193
Peano arithmetic, 170–171, 173–175
Peano curve, 171
Perfect numbers
mathematicians’ interest in, 63
Permutation of remainders lemma, 71–72
Phaedo, 43
Philo of Alexandria, 7
PID (principal ideal domains), 228
Pisano, Leonardo See Leonardo Pisano
Plaintext, 238
Platonic Questions, 20
Playfair’s axiom, 163
Plus sign (+), mathematical convention for, 115
Plutarch, 20
Poincaré, Jules Henri, 85, 229–230, 248
pointer iterator trait, 187
Politics, 179
computing GCD for, 134
degree of, definition, 133
division with remainder, 133
Horner’s rule, 132
polynomial_value, 132
Population count, 10
Postconditions, 269
Postulates, Euclid’s axiomatic method, 162, 163
computing Fibonacci numbers, 126
computing linear recurrence, 127
use in cryptology, 241–243, 246
use in graph applications, 148–149
power_accumulate_semigroup, 121
power_group, 123
power_monoid, 122
power_semigroup, 122
Prime factorization, 29, 31–32, 65, 136, 139–140
definition, 21
distinguishing from composite, 240–245
finding. See sieve of Eratosthenes
infinite number of, 21
Principal element, 227
Principal ideal domains (PID), 228
Proof
nonconstructive, 229
Proper divisor, 32
Ptolemy, 164
Public-key cryptosystems, 239–240
Pythagoras, 17
Pythagorean Theorem, 44
Quadrivium, 18
Quaternions, 151
Quotient, 55–57, 150, 153, 202
for polynomials, 133
quotient_remainder, 57
Random-access iterators, 185
Ranges
closed, 188
definition, 188
open, 188
partition points, 193
semi-open, 188
Rational arithmetic, GCD applications, 234
reciprocal, 124
Recreational mathematics, 225–226
Recursive remainder lemma, 48–49
Reduction algorithm, 124
reference iterator trait, 187
Regius, Hudalricus, 64
Regular functions, 183
Regular types, 114
Rejewski, Marian, 238
Remainder, 47–49, 53–55, 57–59, 150, 153, 222
Floyd-Knuth algorithm, 58
permutation of remainders, 71–72
remainder_fibonacci, 58
Remote parts of objects, 181
Requirements on algorithm, 111–119
reverse_copy, 216
reverse_n, 214
reverse_n_adaptive, 217
reverse_n_with_buffer, 216
reverse_recursive, 214
Reverse permutation, 201, 212–215
Rhind Mathematical Papyrus, 8, 57
Rings. See also Ideals; Semirings
integral domains, 145
summary description, 153
unitary, 143
units, 144
zero divisors, 145
Rivest, Ron, 239
rotate_cycle_from, 208
rotate_transform, 210
rotate_unguarded, 206
Rotation algorithms, GCD applications, 234
RSA algorithm, 239–240, 245–247
Russell, Bertrand, 171
Russian Peasant Algorithm, 9. See also Egyptian multiplication
Saccheri, Giovanni Girolamo, 164
Saxena, Nitin, 244
Scheme, 116
Searches
Segmented iterators, 186
Semantic requirements for generic algorithms, 113
Semigroups. See also Groups
associativity axiom, 91
commutativity of powers, 91
examples, 90
multiplication algorithm, 115
multiplicative, 90
Semi-open ranges, 188
Semiregular concepts, 184
Semirings. See also Rings
Boolean, 148
matrix multiplication, 146
summary description, 153
tracing social networks, 147–148
tropical, 149
weak, 147
Separating types, law of, 202–203
Setting of algorithm, 150
Shamir, Adi, 239
Shortest path, finding, 148–149
sift, 27
smallest_divisor, 240
Social network connections, tracing, 147–148
Socrates, 42
Socratic method, 42
Sophists, 42
Square root of 2, an irrational number, 37–38
Standard Template Library. See STL
stein_gcd, 220
Stepanov, Alexander A., 3, 124
STL (Standard Template Library)
application of generic programming, 1, 186
conventions, 24
non-categorical, 104
Strength reduction, 26
Stroustrup, Bjarne, 265
Subgroups. See also Groups
cyclic, 96
generator elements, 96
trivial, 95
Sum of odd powers formula, 30
swap, 199
Symbolic integration, GCD applications, 234
Symmetric groups, 198
Symmetric keys, 238
Symposium, 43
Syntactic requirements for generic algorithms, 113
Tail-recursive functions, 12–14
Thales of Miletus, 18, 159–161
Theories. See also Models
characteristics of, 102
completeness, 102
definition, 102
determining truth of, 167
finite axiomatizability, 102
independence, 102
univalent, 104
Totality of successor axiom, 172
Totient of an integer, 80
A Tour of C++, 265
Transformation group, 92
Transitive closures, finding, 147–148
Transposition lemma, 199
Trapdoor one-way functions, 239
Triangular numbers, 19
Trichotomy Law, 34
Trivial subgroups, 95
Tropical semirings, 149
Tusculan Disputations, 50
Type dispatch. See Category dispatch
Unitary rings, 143
Units, rings, 144
Univalent theories, 104
Univariate polynomials. See Polynomials
University of Göttingen. See Göttingen, University of
Unrestricted objects, 181
upper_bound, 195
Useful return, law of, 57–58, 201–202, 213
Value types, definition, 180
Values, definition, 180
value_type iterator trait, 187
van der Waerden, Bartel, 129, 142
Veblen, Oswald, 104
vector container, 116,
Vorlesungen über Zahlentheorie (Lectures on Number Theory), 140
Waring, Edward, 76
Weak semirings, 147
Weilert, Andre, 224
Well-ordering principle, 34
Whitehead, Alfred North, 43
Wiles, Andrew, 67
Wilson, John, 76
Wilson’s Theorem
description, 76
using modular arithmetic, 83
Witnesses, primality testing, 242
Zero
in Egyptian number system, 8
introduction of, 52
3.134.76.72