On the Ruby issue tracker replacing Euclid's gcd algorithm with Steins (binary) algorithm came up.
https://bugs.ruby-lang.org/issues/13503
Here's the wikipedia article on it.
https://en.wikipedia.org/wiki/Binary_GCD_algorithm
Here's a Nim implementation of the iterative version.
proc gcd(a, b: int): int =
var (a, b) = (a, b)
if a == 0: return b
if b == 0: return a
var k = 0
while ((a or b) and 1) == 0:
a = a shr 1
b = b shr 1
k += 1
while (a and 1) == 0: a = a shr 1
while b != 0:
while (b and 1) == 0: b = b shr 1
if a > b: swap a,b
b -= a
result = a shl k
Here's a Ruby implementation of it.
def gcd(a, b)
return b if a.zero?
return a if b.zero?
k = 0
while (a | b).even?
a >>= 1; b >>= 1; k += 1
end
a >>= 1 while a.even?
until b.zero?
b >>= 1 while b.even?
a, b = b, a if a > b
b -= a
end
a << k
end
Relevant Handbook of Applied Cryptography on page 17 of the this chapter 14 PDF (page 606 - chapter 14.4 of the whole book)
It has the binary GCD, extended binary GCD and Lehmer's GCD algorithm.
Back in the day I had that book, when I wore a younger man's clothes, and also Applied Cryptography. I wonder what happened to them....
https://www.goodreads.com/book/show/351301.Applied_Cryptography