유클리드 호제법보다 빠르게 최대공약수를 구하는 방법 - 스테인 알고리즘

1. Introduction

이번 포스팅에서는 호제법보다 빠른 최대공약수 식별 알고리즘을 소개한다.

스테인 알고리즘 (Stein's algorithm) 이라고도 불리는 알고리즘이며, 기존의 호제법보다 60%의 효율개선을 보이는 획기적인 알고리즘이다.

는 그렇게 대단한 알고리즘이 아니다...

스테인 알고리즘은 이진 GCD 알고리즘이라고도 불리며, 호제법의 이진버전이라고 생각하면된다. 호제법에서 각 루틴마다. $A \bmod B (A>B)$ 를 수행하지만, 스테인 알고리즘에서는 A와 B를 모두 반으로 나눈다.

2. Approach

다음과 같은 규칙을 따른다.

1. 두 수가 짝수일 때는 2로 나눈다. a 변수를 1증가시킨다.
2. 한 수만 짝수일 때는 그 수를 2로 나눈다.
3. 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀다.
4. 0이 되는 수가 있으면 종료한다. 0이 아닌 반대쪽 수를 b변수라 한다.

이 루틴이 끝나면 $2^a*b$를 구한다. 이것이 두 수의 최대공약수이다.

증명은 어렵지 않다.

• 두 수가 짝수일 때 2로 나누는 것은 공약수가 2를 포함하고 있다는 의미이다. 따라서 이를 a변수에 기록한다.
• 한 수만 짝수일 때 2로 나누는 것은 한쪽만 2를 포함하고 있기때문에 이를 날리는 것이다.
• 두 수가 홀수일 때 큰 수에서 작은 수를 빼는 것은 호제법과 같은 수행이므로 증명에 문제가 없다.

스테인 알고리즘을 통해 36과 24의 최대공약수를 찾는 과정은 다음과 같다.

36 → 18 →9 →9 →6 →3 →3 

24 → 12 →6 →3 →3 →3 →0

3. code

def binaryGCD(a, b):
    exp = 0
    
    while (~(a|b)&1):
        exp += 1
        a >>= 1
        b >>= 1
    
    while a and b:
        while ~a & 1:
            a >>= 1
        while ~b & 1:
            b >>= 1
        if a > b:
            a -= b
        else:
            b -= a
    n = a if a else b
    return n << exp