The site's fifteenth Number Theory entry, and the same question
Euclidean Algorithm already answers —
gcd(a, b) — reached by a completely different mechanism. Also called
Stein's Algorithm, after Josef Stein's 1967 description, it never divides and
never takes a remainder. Every step is one of three cheaper primitives instead: check a number's
lowest bit, right-shift it (halve it), or subtract. On hardware with no fast integer divider —
true of early microprocessors, and still true inside some embedded and constant-time bignum
routines that deliberately avoid a variable-latency division instruction — that trade is a real
win.
Whether it's still a win inside a JavaScript engine, where % already compiles to
a single fast instruction, is a different question — and one this page checks directly rather
than assuming the historical reasoning still applies seventy years later. Short answer, measured
below: no. See Complexity.
Enter any two whole numbers and step through the reduction. 1071, 462 and
89, 55 are the same two pairs Euclidean Algorithm's own demo uses — load either
one on both pages side by side and count steps directly. The trail below shows the running
(a, b) pair plus the common power-of-two factor pulled out so far, restored into the
final answer only once b hits zero.
(a, b) pairs, oldest to newest:
Four rules, each shrinking the pair while leaving the true gcd recoverable:
gcd(a, 0) = a base case
gcd(0, b) = b base case
gcd(a, b) = 2·gcd(a/2, b/2) both even
gcd(a, b) = gcd(a/2, b) a even, b odd (symmetric the other way too)
gcd(a, b) = gcd(|a − b|, min(a, b)) both odd
Both even: 2 is a common factor of both numbers, so pull it all the way out —
gcd(a, b) = 2·gcd(a/2, b/2) — and keep a running tally of how many times this
happens. That tally is the shift the demo tracks separately from (a, b):
it only gets multiplied back in once at the very end.
One even, one odd: say a is even and b is odd. 2
cannot be a common divisor here — b has none to share — so dividing the even side by
2 removes a factor neither number needed to keep. gcd(a, b) = gcd(a/2, b) exactly,
no running tally this time, since no shared factor of 2 was ever found.
Both odd: this is the step with no shift available at all, so it falls back to
subtraction — gcd(a, b) = gcd(|a − b|, min(a, b)), the same common-divisor argument
Euclidean Algorithm's own Why it
works section makes for remainder, just with the quotient forced to exactly 1. The payoff:
the difference of two odd numbers is always even, so the very next iteration is guaranteed to
find at least one bit to shift off, never two both-odd steps in a row.
Termination follows because every step strictly shrinks max(a, b) — a shift
halves something, a subtraction between two numbers with no shared power of 2 left strictly
reduces the larger one — so the loop can't run forever, the same style of argument Euclidean
Algorithm's own remainder step relies on.
function binaryGcd(a, b) {
a = Math.abs(a) >>> 0;
b = Math.abs(b) >>> 0;
if (a === 0) return b;
if (b === 0) return a;
let shift = 0;
while (((a | b) & 1) === 0) { // both even: shed a shared factor of 2
a >>>= 1;
b >>>= 1;
shift++;
}
while ((a & 1) === 0) a >>>= 1; // a may still be even; b is now guaranteed odd
while (b !== 0) {
while ((b & 1) === 0) b >>>= 1; // make b odd too
if (a > b) { const t = a; a = b; b = t; }
b -= a; // both odd: subtract, difference is even
}
return a * Math.pow(2, shift); // restore the shared factor of 2
}
>>> and & are 32-bit operators — this
implementation silently stops being correct above 2³² − 1. JavaScript's
bitwise operators coerce both operands through ToUint32/ToInt32 before
doing anything, truncating any bits above the 32nd. Euclidean Algorithm's %-based
loop has no such ceiling — it stays exact up to Number.MAX_SAFE_INTEGER (2⁵³ − 1).
Feed the reference implementation above a genuine mismatch:
// true gcd(4295329114, 18483) = 1 (confirmed via the % loop, safe to 2^53)
binaryGcd(4295329114, 18483) // returns 3 — silently wrong, no error
// true gcd(4295913858, 956346) = 6
binaryGcd(4295913858, 956346) // returns 2 — silently wrong, no error
Both inputs are ordinary-looking numbers just over 2³² (roughly 4.29 billion) —
not an exotic edge case, just large. There's no warning, no thrown error, no NaN:
the function returns a plausible-looking wrong integer every time. If inputs might exceed 32
bits, either switch every operator to its BigInt equivalent or use Euclidean
Algorithm's %-based loop instead, which has no such limit to begin with.
Forgetting to multiply the shift back in is wrong exactly a quarter of the time, not
rarely. Drop the final * Math.pow(2, shift) and return the bare odd-part
a instead:
gcd(12, 18) via the full algorithm: 6 (correct)
gcd(12, 18) with the shift never restored: 3 (wrong)
Checked across every pair in [1, 500]²: the un-restored version disagrees with
the correct answer on exactly 25.0% of pairs — not an approximate figure, an
exact one, because it's wrong precisely when both inputs are even (independent 1-in-2 odds each,
so 1-in-4 pairs), which is also exactly the only case where shift is ever nonzero.
Every pair with at least one odd input happens to come out right regardless, which can hide the
bug in casual testing if the first few inputs tried are odd-heavy.
Trusting "avoids division, so it's faster" without checking. That reasoning is sound on hardware with no fast divider — it's the whole reason this algorithm exists — but it doesn't automatically transfer to every runtime. See Complexity for the real numbers in this one (JavaScript, V8): slower, not faster, on every input shape tested, including the shape that should favor it most.
O(log(min(a, b))) steps — the same asymptotic bound as Euclidean Algorithm, for a related reason: a both-even step removes a bit from both numbers at once, a one-even-one-odd step removes a bit from one, and a both-odd subtraction step is immediately followed by at least one guaranteed shift, so no more than two steps in a row can pass without some bit disappearing somewhere. But the constant factor is visibly larger. Counting every primitive shift and subtraction as one step and averaging over 5,000 random pairs at each bit width:
bits=8: Euclidean ≈ 4.8 steps, Binary GCD ≈ 14.1 steps (2.97×)
bits=16: Euclidean ≈ 9.4 steps, Binary GCD ≈ 30.9 steps (3.30×)
bits=24: Euclidean ≈ 14.2 steps, Binary GCD ≈ 47.9 steps (3.38×)
bits=30: Euclidean ≈ 17.6 steps, Binary GCD ≈ 60.6 steps (3.45×)
The gap holds on Euclidean's own worst case too — consecutive Fibonacci pairs, which force Euclidean's quotient to be exactly 1 every step (see that page's own Complexity section):
fib(20), fib(21) = 6765, 10946: Euclidean 19 steps, Binary GCD 31 steps
fib(30), fib(31) = 832040, 1346269: Euclidean 29 steps, Binary GCD 44 steps
fib(40), fib(41) = 102334155, 165580141: Euclidean 39 steps, Binary GCD 60 steps
More steps doesn't automatically mean slower wall-clock, since a shift and a comparison are
each individually cheaper than a full division — correctness was cross-checked first (20,000
random pairs plus an exhaustive brute-force sweep of every pair in [0, 300]², 0
mismatches either way) before timing anything. Running both reference implementations above
directly, best-of-five timed passes to filter out GC noise, on 500,000 random pairs at each
width:
bits=16: Euclidean 61.4ms, Binary GCD 86.5ms (1.41× slower)
bits=24: Euclidean 79.1ms, Binary GCD 116.2ms (1.47× slower)
bits=30: Euclidean 93.3ms, Binary GCD 138.3ms (1.48× slower)
Binary GCD loses on ordinary random input. The more interesting check is its own theoretical
best case: two numbers that are identical powers of two, which collapses the entire both-odd
subtraction loop to nothing — every single step is a cheap shift, the shape this algorithm was
designed around. Euclidean Algorithm, meanwhile, resolves gcd(2ᵏ, 2ᵏ) in exactly
one division step, for any k, since a % b is
immediately 0 when a === b. Timed directly, one million pairs per width, best of
five:
k=10: Euclidean 14.4ms (1 step always), Binary GCD 110.0ms (10 shifts) — 7.7× slower
k=16: Euclidean 20.0ms (1 step always), Binary GCD 111.9ms (16 shifts) — 5.6× slower
k=20: Euclidean 18.4ms (1 step always), Binary GCD 115.4ms (20 shifts) — 6.3× slower
k=24: Euclidean 18.4ms (1 step always), Binary GCD 118.5ms (24 shifts) — 6.4× slower
k=28: Euclidean 19.4ms (1 step always), Binary GCD 121.9ms (28 shifts) — 6.3× slower
Binary GCD loses by the widest margin on exactly the input it should win on. One
% instruction captures an entire shared power of two in a single step; the
shift-based algorithm still has to walk that power of two off one bit at a time, and V8's
division is fast enough that paying for k loop iterations instead of one isn't
close. The lesson isn't "Binary GCD is a bad algorithm" — it's that "avoids division" is a
hardware-dependent advantage, not a universal one, and it doesn't survive contact with a runtime
that already has a fast divider. Reach for it when the real constraint is an environment with no
division instruction to begin with (certain embedded targets, constant-time cryptographic code
that specifically avoids variable-latency division), not for raw speed in JavaScript.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other fourteen Number Theory entries side by side.