Euclidean algorithm
An iterative algorithm that computes the greatest common divisor by repeatedly subtracting numbers until nothing remains; one of the earliest formally described algorithms
As defined in History of Science and Technology Q&A (February 8, 2023)
Where it comes up · 1
Most important claims · 2 of 2Search all claims for “Euclidean algorithm” →
- Primitive recursion, a concept from early 20th-century mathematical logic, describes operations where you know in advance how many times you will loop; general recursion (which Gödel introduced for his incompleteness theorem work) describes operations where you continue until some criterion is satisfied, as exemplified by the Euclidean algorithm.History of Science and Technology Q&A (February 8, 2023)
- The Euclidean algorithm for computing greatest common divisors, described in Euclid's Elements, is an iterative algorithm where you repeatedly subtract numbers until reaching nothing, and it is one of the earliest formally described algorithms in history.History of Science and Technology Q&A (February 8, 2023)