Calculate the Binary GCD
Enter two non-negative whole numbers. The calculator finds their greatest common divisor using Stein's binary GCD algorithm.
Try an example
What Is the Binary GCD Algorithm?
The binary GCD algorithm, also known as Stein's algorithm, computes the greatest common divisor (GCD) of two integers using even/odd checks, division by two, subtraction, and comparisons. It avoids the division-with-remainder operation used by the standard Euclidean algorithm.
Key rules
- Zero: gcd(a, 0) = |a|.
- Both even: gcd(2a, 2b) = 2 × gcd(a, b).
- One even, one odd: gcd(2a, b) = gcd(a, b) when b is odd.
- Both odd: if a and b are odd, gcd(a, b) = gcd(|a − b| / 2, min(a, b)) when applied with the equivalent binary reductions.
In the implementation above, common factors of two are removed first. The working values are then made odd, ordered, and reduced by subtraction until one value becomes zero. The remaining value is multiplied by the common power of two to recover the GCD.
Worked example: gcd(48, 18)
Start with a = 48 and b = 18.
18 = 2 × 32
gcd(48, 18) = 2 × 3 = 6
Both values are even, so divide each by two: (48, 18) → (24, 9). Remove the remaining powers of two from the even value and repeatedly subtract the smaller odd value from the larger. The algorithm eventually leaves 3, and the shared factor of 2 restores the result to 6.
Binary GCD versus Euclidean GCD
| Feature | Binary GCD | Euclidean GCD |
|---|---|---|
| Main operations | Parity checks, shifts/division by two, subtraction | Division with remainder |
| Common powers of two | Handled directly | Handled through remainder steps |
| Best known for | Bit-oriented implementation and avoiding general division | Simple, widely used GCD computation |
| Result | Exact within the supported integer range | Exact within the supported integer range |
Frequently Asked Questions
What does GCD mean?
The greatest common divisor is the largest positive integer that divides both input integers without leaving a remainder. For example, gcd(48, 18) = 6.
Why is it called binary GCD?
The algorithm takes advantage of whether numbers are even or odd, properties that are directly visible in their binary representations. An even integer ends in a zero bit in binary, so dividing it by two is equivalent to shifting right by one bit.
Does the calculator accept zero?
Yes. For a nonzero input a, gcd(a, 0) = |a|. This calculator defines gcd(0, 0) = 0 by convention, although some mathematical contexts leave gcd(0, 0) undefined.
Can I enter negative numbers?
This page accepts non-negative integers. The mathematical GCD is usually defined using absolute values, so negative inputs can be converted to their absolute values before calculating.
Is binary GCD always faster than Euclidean GCD?
Not necessarily. Performance depends on the processor, integer size, programming language, and implementation. Binary GCD can be useful when bit operations are efficient, while the Euclidean algorithm is also highly effective.