Live briefing
Everything about Euclidean algorithm
Algorithm for computing greatest common divisors
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Euclidean algorithmA 5-minute orientation
- Skim a recent paper: Incorporating Surprisingly Popular Algorithm and Euclidean distance-based adaptive topology into PSOInfluential work since 2022
- Pick up a classic book: Introduction to Theory of Optimization in Euclidean SpaceThe most-reprinted book on the subject
- Read the landmark paper: Algorithm AS 58: Euclidean Cluster AnalysisCited 58 times
- Go sideways: Extended Euclidean algorithmA closely related topic
- Go sideways: Polynomial greatest common divisorA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Algorithm AS 58: Euclidean Cluster Analysis
The Euclidean algorithm
Editor's Corner: The Euclidean Algorithm Strikes Again
Rational interpolation and the Euclidean algorithm
On a Generalization of the Euclidean Algorithm
A Parallel Euclidean Distance Transformation Algorithm
The Computing Time of the Euclidean Algorithm
Note on the Euclidean Algorithm
🆕 Influential since 2022
Incorporating Surprisingly Popular Algorithm and Euclidean distance-based adaptive topology into PSO
A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation
Discrete Salp Swarm Algorithm for Euclidean Travelling Salesman Problem
Euclidean Direction Search Algorithm Based on Maximum Correntropy Criterion
Point Cloud Segmentation Algorithm Based on Improved Euclidean Clustering
📚 Books worth reading
- 📕Introduction to Theory of Optimization in Euclidean SpaceSamia Challal · 2019
- 📕The Euclidean traveling salesman problem with neighborhoods and a connecting fenceHakån Jonsson · 2000
Euclidean symmetries in mathematicsGidget Haddad · 2012- 📕Rational Sphere MapsJohn D'Angelo · 2021
- 📕Generalizing Euclid's algorithm, via the regular and Moebius knot trees, order-n arithmeticsA. G. Schaake · 1990
The LLL AlgorithmNguyen, Phong, Q. · 2010
Linear algebra, rational approximation, and orthogonal polynomialsAdhemar Bultheel · 1997- 📕Solving medium to large sized euclidean generalized minimum spanning tree problemsDiptesh Ghosh · 2003
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest…
- Polynomial greatest common divisor In algebra, the greatest common divisor (frequently abbreviated GCD or gcd) of two polynomials is a polynomial, of the highest possible degree, which is…
- Greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the…
- Kuṭṭaka Kuṭṭaka is an algorithm for finding integer solutions of linear Diophantine equations. A linear Diophantine equation is an equation of the form ax + by…
- Bézout's identity In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is a theorem which relates two…
- Primitive part and content In algebra, the content of a nonzero polynomial with integer coefficients (or, more generally, with coefficients in a unique factorization domain) is the…
- Factorization In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object…
- Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition…