4. Euclid’s Algorithm
The whole structure of number theory rests on a single foundation,namely the algorithm for finding the greatest common divisor.Dirichlet, Lectures on Number Theory
In the previous chapter, we met Pythagoras and the secretive order he founded to study astronomy, geometry, number theory, and music. While the Pythagoreans’ failure to find a common measure of the side and the diagonal of a square ended the dream of reducing the world to numbers, the idea of a greatest common measure (GCM) turned out to be an important one for mathematics—and eventually for programming. In this chapter, we’ll introduce an ancient algorithm for GCM that we’ll be exploring throughout the rest of the book.
4.1 Athens and Alexandria
To set the stage ...
Get From Mathematics to Generic Programming now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
