Lably
Skip to content

Binary GCD algorithm

Algorithm for computing the greatest common divisor

  • 10 min read
  • 5 chapters

Related on Lably

Through Greatest common divisor, Bitwise operation and Iteration

LabWhole Numbers & Playing with NumbersLab · Class 5–6Fractions VisualizerLab · Class 1–6PatternsLab · Class 11Binary and Logic Gates

Although the algorithm in its contemporary form was first published by the physicist and programmer Josef Stein in 1967, it was known by the 2nd century BCE, in ancient China.

Algorithm

The algorithm finds the GCD of two nonnegative numbers u and v by repeatedly applying these identities:

  1. gcd(u,0)=u: everything divides zero, and u is the largest number that divides u.
  2. gcd(2u,2v)=2⋅gcd(u,v): 2 is a common divisor.
  3. gcd(u,2v)=gcd(u,v) if u is odd: 2 is then not a common divisor.
  4. gcd(u,v)=gcd(u,v−u) if u,v odd and u≤v.

As GCD is commutative (gcd(u,v)=gcd(v,u)), those identities still apply if the operands are swapped: gcd(0,v)=v, gcd(2u,v)=gcd(u,v) if v is odd, etc.

Sign in to keep reading

4 more chapters are free with a Lably account.

More in Topics in mathematics

DiameterStraight line segment that passes through the centre of a circleSmoothnessDegree of differentiability of a function or mapGroup actionTransformations induced by a mathematical groupMonotonic functionOrder-preserving mathematical functionCountable setMathematical set that can be enumeratedEllipsoidQuadric surface that looks like a deformed sphere