Can you program that formula?

Can you program that formula?

“Can you program that formula?” From the book.

The theme of this book is programming, but unlike most programming books, it includes not only algorithms and code, but also mathematical proofs and historical background on mathematical discoveries from ancient to modern times.

To be more specific, the theme is generic programming. Generic programming is a programming technique that emerged in the 1980s, and the C++ TL (Standard Template Library) was developed in the 1990s. Generic programming is a programming technique that focuses on designing algorithms and data structures to make them work in the most common environments without decreasing efficiency.

Generic programming is more like an attitude towards programming than a collection of specific tools represented by the STL.

The origin of generic programming is mathematics, and more specifically, it originated in a branch of mathematics called abstract algebra. To help you understand this approach, this book describes abstract algebra with a focus on reasoning about objects in terms of the operations that can be performed on them.

In fact, much of this basic programming thinking comes from mathematics. Learning how these ideas came about and how they developed is an important part of learning software design. For example, Euclid’s Elements, written more than 2000 years ago, is still one of the most effective models of how to build complex systems from small, easily understood elements.

At the heart of generic programming is abstraction, but abstraction does not exist in its full form from the start. To understand how to make something law, we need to start with the concrete. To be more specific, in order to get abstractions right, we need to have a concrete understanding of a particular field.

The abstractions that appear in abstract algebra are mainly based on the concrete results of the study of number theory, which is the most ancient part of mathematics. Therefore, this book also introduces the basic ideas of number theory about the properties of integers, especially divisibility.

These thought processes for understanding mathematics will not only improve your programming skills, but also provide hints for building various algorisms.

The contents in this book include
Chapter 1 is an overview of generic programming
In Chapter 2, episodes about ancient multiplier algorithms and how to improve them
In Chapter 3, early views on the properties of numbers and an efficient implementation of an algorithm for finding prime numbers
In Chapter 4, algorithms for finding the greatest common divisor (basics of abstract concepts and applications)
Chapter 5 explains two theorems that play an important role
Chapter 6 discusses the abstract mathematics at the heart of generic programming
Chapter 7 generalizes mathematical concepts to go beyond simple hypnotism and apply information algorithms to practical programming
In Chapter 8, an introduction to new abstract mathematical structures
Chapter 9 describes axiomatic systems, theories, and models (the building blocks of generic programming)
Chapter 10 introduces the concepts that make up generic programming, and presents the subtleties involved in a seemingly simple programming task.
Chapter 11 examines basic programming tasks and shows how theoretical knowledge of the problem can be applied to field implementations.
Chapter 12 shows how hardware constraints can lead to new approaches to old algorithms.
In Chapter 13, we combine mathematical and algorithmic results to build a cryptographic application.
In Chapter 14, we summarize
and the rest of the book.

The table of contents for them is as follows.

CHAPTER1 Contents of this book
Overview
1.1 Programming and Mathematics
1.2 Historical perspective
1.3 Assumptions of this book
1.4 Roadmap
CHAPTER2 The First Algorithm
Introduction
2.1 Egyptian Multiplication
2.2 Improvements to the Algorithm
2.3 Summary
CHAPTER3 Number Theory in Ancient Greece
3.1 Geometric Properties of Integers
3.2 Shift of Prime Numbers
3.3 Code Implementation and Optimization
3.4 Perfect numbers
3.5 Pythagoreanism
3.6 Fatal flaw in the Pythagorean scheme
3.7 Conclusion
CHAPTER4 Euclid's Reciprocal Division
4.1 Athenians and Alexandrians
4.2 Euclid's greatest common divisor algorithm
4.3 The blank millennium of mathematics
4.4 The Curious History of Zero
4.5 Surplus and Quotient Algorithms
4.6 Code Sharing
4.7 Verification of the Algorithm
4.8 Summary
CAHPTER5 The Birth of Modern Number Theory
5.1 Mersenne and Fermat Primes
5.2 Fermat's Little Theorem
5.3 Simplification
5.4 Proof of Fermat's Little Theorem
5.5 Euler's theorem
5.6 Applications of congruence arithmetic
5.7 Conclusion
CHAPTER6 Abstractness in Mathematics
6.1 Groups
6.2 Monoid and Semigroup
6.3 Theorems on groups
6.4 subgroups and cyclic groups
6.5 Lagrange's theorem
6.6 Theories and models
6.7 Examples of sphere theory and non-sphere theory
6.8 Conclusion
CHAPTER7 Generalization of Algorithm
7.1 Organize the Requirements of Algorithm
7.2 Requirements of A
7.3 Requirements of N
7.4 New Requirements
7.5 Converting Multiplication to Power
7.6 Generalization of Operations
7.7 Calculating the Finavocci Sequence
7.8 Summary
CHAPTER8 Other Algebraic Structures
8.1 stevin, polynomial, greatest common divisor
8.2 Göttingen and German mathematics
8.3 Nater and the Birth of Abstract Algebra
8.4 Rings
8.5 Matrix multiplication and semiring
8.6 Applications : Social networks and shortest paths
8.7 Euclidean domains
8.8 Bodies and other algebraic structures
8.9 Conclusion
CHAPTER9 Systematization of mathematical knowledge
9.1 Proof
9.2 The First Theorem
9.3 Euclid and Axiomatic Method
9.4 Alternatives to Euclidean Geometry
9.5 Hilbert's formalist approach
9.6 Peano and Peano's axioms
9.7 The construction of arithmetic
9.8 Conclusion
CHAPTER10 Basic Concepts of Programming
10.1 Aristotle and Abstraction
10.2 Value and Type
10.3 Concept
10.4 Iterators
10.5 iterator categories, operations and treits
10.6 Intervals
10.7 Linear Search
10.8 Binary search
10.9 Summary
CHAPTER11 Substitution Algorithm
11.1 Substitution and transposition
11.2 Replacement of Intervals
11.3 Rotation
11.4 Using cycles
11.5 Inversion
11.6 Spatial Cost
11.7 Memory Application Algorithm
11.8 Summary
CHAPTER12 Extensions of GCD
12.1 Hardware Constraints and More Efficient Algorithms
12.2 Generalization of Stein's Algorithm
12.3 Bezou's Equation
12.4 Extended GCD
12.5 Applications of GCD
12.6 Summary
CHAPTER13 Applications in the Real World
13.1 Cryptology
13.2 Prime Number Judgment
13.3 Miller-Lapin Test
13.4 RSA Algorithm
13.5 Summary
For an in-depth understanding
Chapter 1
Generic Programming
Chapter 2
History of Mathematics
The Lind Math Papyrus
Chapter 3.
Mathematics in Ancient Egypt and Greece
Polygonal Numbers
Fundamental Number Theory
Chapter 4
The greatest common divisor
The Decline of Greek Learning
The History of Zero
Leonardo Pisano (Finavocci)
Surplus and Quotient
Chapter 5
Fermat and Euler's Work on Number Theory
Euler's Books
Chapter 6
Group Theory
Model Theory
Chapter 7
Type requirements
Simplification
Chapter 8
Simon Stebbins
Division of Polynomials and GCD
Origins of Abstract Algebra
Abstract Algebra
Rings
Chapter 9.
The Social Nature of Proofs
Euclid
Axioms of Geometry
Non-Euclidean Geometry
Peano Arithmetic
Chapter 10.
Aristotle's Classification of Knowledge
Concepts
Iterators and Search
Chapter 11.
Substitution and Transitivity
Rotation and Inversion
Chapter 12.
Stein's Algorithm
Recreational Mathematics
Chapter 13.
Cryptography
Number Theory
AKS Prime Number Determination Method
APPENDIX A Mathematical notation
A1 Symbols
A2 Examples
A3 Implication and syllogism
APPENDIX B General Proofs
B1 Proof by Backward Method
B2 Proofs by induction
B3 The Pigeon's Nest Principle
APPENDIX C C++ for Non-C++ Programmers
C1 Template functions
C2 Concepts
C3 Language syntax and constant typing
C4 Function objects
C5 Preconditions, postconditions, and assertions
C6 STL algorithms and data structures
C7 Iterators and intervals
C8 Type aliases and type functions using C++11
C9 C++11 initializer lists
C10 C++11 lambda functions
C11 Notes on Inline
Translated with www.DeepL.com/Translator (free version)