Input: Two integers, m and n

Output: The GCD of m and n

BinaryGCD(m,n)

(1) if m = 0 or n = 0
(2)    return 0
(3) s := 0
(4) while m and n are even
(5)       m := m/2
(6)       n := n/2
(7)       s := s + 1
(8) while n is even
(9)       n := n/2
(10) while m != 0
(11)       while m is even
(12)             m := m/2
(13)       if m < n
(14)          Swap(m,n)
(15)       m := m − n
(16)       m := m/2
(17) return 2^s * n