이진 최대공약수 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
- 2.1. 기본 알고리즘
- 2.2. 확장된 알고리즘
3. 구현
- 3.1. C 언어
- 3.2. Rust 언어
4. 효율성
5. 확장
6. 역사
참조

1. 개요

이진 최대공약수 알고리즘은 최대공약수를 계산하는 알고리즘으로, 유클리드 호제법과 달리 비트 연산을 사용하여 효율성을 높인 것이 특징이다. 이 알고리즘은 0, 짝수, 홀수 조건에 따라 최대공약수를 계산하는 여러 단계를 반복 적용하며, 확장된 알고리즘은 베주 계수를 제공하기도 한다. C와 Rust 언어로 구현될 수 있으며, 평균적으로 유클리드 호제법보다 더 적은 비트 연산을 사용하지만, 점근적 복잡도는 동일하다. 또한, 확장 유클리드 알고리즘과 유사하게 확장될 수 있으며, 큰 정수, 가우스 정수 등 다양한 영역으로 확장 적용될 수 있다. 이 알고리즘은 고대 중국의 구장산술에 그 기원을 두고 있다.

더 읽어볼만한 페이지

수론 알고리즘 - 유클리드 호제법
유클리드 호제법은 두 정수의 최대공약수를 효율적으로 계산하는 알고리즘으로, 다양한 수학적 대상에 적용되며 베주의 항등식 등 여러 분야에 응용된다.
수론 알고리즘 - 고대 이집트 곱셈법
고대 이집트 곱셈법은 두 열을 사용하여 곱셈을 계산하는 방식으로, 첫 번째 수를 2의 거듭제곱으로 분해하고 두 번째 수에 2의 거듭제곱을 곱하는 방법을 사용했으며, 분배 법칙과 수학적 귀납법으로 정확성이 증명되어 현대 사회에도 응용된다.

이진 최대공약수 알고리즘
기본 정보
분야	알고리즘
문제 해결	최대공약수
자료 구조	없음
특징
발명가	조지 콜린스
발표 연도	1967년
종류	최대공약수 알고리즘
시간 복잡도	O(n)
공간 복잡도	O(1)

2. 알고리즘

이 알고리즘은 다음의 항등식들을 반복적으로 적용하여 두 개의 음이 아닌 정수 $u$ 와 $v$ 의 최대공약수(GCD)를 찾는 방식으로 작동한다.

# $\gcd(u, 0) = u$

# $\gcd(2u, 2v) = 2 \cdot \gcd(u, v)$

# $\gcd(u, 2v) = \gcd(u, v)$ (만약 $u$ 가 홀수일 경우)

# $\gcd(u, v) = \gcd(u, v - u)$ (만약 $u, v$ 가 모두 홀수이고 $u \leq v$ 일 경우)

최대공약수는 교환 법칙( $\gcd(u, v) = \gcd(v, u)$ )이 성립하므로, 위 항등식들은 피연산자의 순서를 바꾼 경우에도 동일하게 적용된다. 예를 들어, $\gcd(0, v) = v$ 이거나, $v$ 가 홀수일 때 $\gcd(2u, v) = \gcd(u, v)$ 와 같이 적용할 수 있다.

2. 1. 기본 알고리즘

이 알고리즘은 다음 규칙들을 반복적으로 적용하여 두 개의 음이 아닌 정수 ''u''와 ''v''의 최대공약수(gcd)를 찾는 문제를 간단하게 만든다. 아래 설명에서 gcd(''u'', ''v'')는 ''u''와 ''v''의 최대공약수를 의미한다.

# gcd(0, ''v'') = ''v'': 0은 모든 수로 나누어떨어지고, ''v''는 자기 자신으로 나누어지는 가장 큰 수이기 때문이다. 마찬가지로 gcd(''u'', 0) = ''u''이다.

# ''u''와 ''v''가 모두 짝수이면, gcd(''u'', ''v'') = 2 · gcd(''u''/2, ''v''/2): 2가 공통 약수이기 때문이다.

# ''u''는 짝수이고 ''v''는 홀수이면, gcd(''u'', ''v'') = gcd(''u''/2, ''v''): 2는 공통 약수가 아니기 때문이다. 마찬가지로 ''u''가 홀수이고 ''v''가 짝수이면, gcd(''u'', ''v'') = gcd(''u'', ''v''/2)이다.

# ''u''와 ''v''가 모두 홀수이고 ''u'' ≥ ''v''이면, gcd(''u'', ''v'') = gcd((''u'' − ''v'')/2, ''v'')이다. 만약 ''u'' < ''v''이면, gcd(''u'', ''v'') = gcd((''v'' − ''u'')/2, ''u'')이다. 이는 유클리드 호제법의 한 단계와 3번 규칙을 조합한 것이다. 두 홀수의 차는 항상 짝수이므로 2로 나눌 수 있다.

# ''u'' = ''v''가 되거나 ''u'' = 0 이 될 때까지 2단계에서 4단계를 반복한다. 두 경우 모두 최종 결과는 2^''k''''v'' 형태가 된다 (여기서 ''k''는 2번 규칙에서 2를 인수로 꺼낸 횟수이다).

이 알고리즘의 시간 복잡도는 최악의 경우 O((log₂ ''uv'')²) 또는 O(log₂² ''uv'')이다. 이는 입력값의 비트 수에 대해 제곱 시간에 해당한다.

2. 2. 확장된 알고리즘

확장된 유클리드 호제법과 유사한 확장된 이진 최대공약수 알고리즘은 《컴퓨터 프로그래밍의 예술》에서 다른 버전들과 함께 제시되어 있다.^[20] 이진 최대공약수 알고리즘은 여러 가지 방법으로 확장될 수 있는데, 추가 정보를 출력하거나, 임의로 큰 정수를 더욱 효율적으로 처리하거나, 정수가 아닌 다른 영역에서 최대공약수를 계산하는 방향으로 발전했다.

주요 확장 중 하나는 확장 유클리드 알고리즘과 유사한 확장 이진 최대공약수 알고리즘이다. 이 알고리즘은 최대공약수(

\gcd(u, v)

)뿐만 아니라,

a\cdot{}u + b\cdot{}v = \gcd(u, v)

방정식을 만족하는 정수

a

와

b

, 즉 베주 계수도 함께 계산한다.^[6]^[7]^[8]

매우 큰 정수를 다루는 경우, 이진 최대공약수 알고리즘은 Schönhage–Strassen 알고리즘의 아이디어를 이용하여 개선될 수 있다.^[10] 이 확장된 알고리즘의 최상의 점근 복잡도는

O(M(n) \log n)

으로, 여기서

M(n)

은

n

비트 정수를 곱하는 데 드는 비용을 의미한다. 이는 거의 선형 시간에 가까운 복잡도로, 기존 이진 최대공약수 알고리즘의

O(n^2)

복잡도보다 훨씬 효율적이다. 그러나 실제 구현에서는 약 64킬로비트(즉, 8×10¹⁹²⁶⁵보다 큰 수) 이상의 매우 큰 정수에 대해서만 기존 알고리즘보다 빠른 성능을 보인다.^[10]

또한, 이진 최대공약수 알고리즘은 정수 외의 다른 수학적 영역으로도 확장되었다. 예를 들어 가우스 정수,^[14] 아이젠슈타인 정수,^[15] 이차 링(quadratic rings),^[16]^[17] 그리고 수체의 대수적 정수환^[18] 등에서도 이 알고리즘의 변형된 형태가 최대공약수를 계산하는 데 사용된다.

3. 구현

이진 최대공약수 알고리즘은 다양한 프로그래밍 언어로 구현될 수 있다. 대표적인 예로 C 언어와 Rust 언어 구현이 있다.

알고리즘의 수학적 원리와 실제 소프트웨어 구현 사이에는 성능 최적화를 위한 몇 가지 차이점이 있다.

비트 연산 활용: 2로 직접 나누는 시도 나누기 대신, 비트 시프트 연산과 후행 0 개수(trailing zeros count) 연산을 사용하는 것이 일반적이다. 이는 기능적으로 동일하지만 훨씬 빠른 성능을 보인다.
구현 방식 최적화: 알고리즘은 반복문 또는 재귀 호출을 사용하여 구현될 수 있으며, 재귀적 구현 시 특정 최적화를 통해 부하를 줄일 수 있다.
분기 없는 코드: 루프(loop) 본문에서 조건문 사용을 최소화하여 분기 예측 실패로 인한 성능 저하를 피하려 한다. 예를 들어, 두 값의 비교 및 교환은 조건부 이동 명령어를 사용하여 구현될 수 있다.^[5] 예측하기 어려운 분기는 성능에 큰 부정적인 영향을 미칠 수 있다.^[3]^[4]

Rust 구현 예시는 [https://github.com/uutils/coreutils/blob/1eabda91cf35ec45c78cb95c77d5463607daed65/src/uu/factor/src/numeric/gcd.rs ''uutils'' coreutils] 프로젝트 등에서 찾아볼 수 있다.

기본 구현은 주로 부호 없는 정수를 다루지만, 두 정수 u, v의 최대공약수는 각 값의 부호에 관계없이 동일하다는 성질(`gcd(u, v) = gcd(±u, ±v)`)을 이용하여 입력값의 절댓값을 취하는 방식으로 부호 있는 정수까지 처리 범위를 확장할 수 있다.

3. 1. C 언어

아래는 이 알고리즘의 C 언어 구현 예시로, 두 양의 정수 ''u''와 ''v''를 입력받아 최대공약수를 반환한다. 이 코드는 먼저 공약수인 2를 효율적으로 처리하고(2단계), 이후 남은 홀수 값들에 대해 반복적으로 차감 및 시프트 연산을 적용하여(3, 4단계) 최대공약수를 계산한 뒤, 마지막으로 처음에 분리했던 2의 거듭제곱을 다시 곱하여 최종 결과를 구한다.

unsigned int gcd(unsigned int u, unsigned int v)

{

int shift;

/* GCD(0, x) = x 라는 성질을 이용한다. u나 v가 0이면, 0이 아닌 값을 반환한다. */

if (u == 0 || v == 0)

return u | v;

/* u와 v에 공통으로 있는 인수 2의 개수(shift)를 센다.

즉, u와 v가 모두 짝수일 동안 오른쪽으로 시프트한다. */

for (shift = 0; ((u | v) & 1) == 0; ++shift) {

u >>= 1;

v >>= 1;

}

/* u가 짝수라면 홀수가 될 때까지 오른쪽 시프트한다.

이후의 루프는 u가 항상 홀수임을 가정한다. */

while ((u & 1) == 0)

u >>= 1;

/* 이 지점에서 u는 홀수이다. */

do {

/* v가 짝수라면 홀수가 될 때까지 오른쪽 시프트한다. */

while ((v & 1) == 0)

v >>= 1;

/* 이제 u와 v는 모두 홀수이다. u와 v 중 큰 수에서 작은 수를 뺀다.

결과는 짝수이므로 오른쪽 시프트하여 2로 나눈다.

항상 u <= v 가 되도록 값을 교환한다. */

if (u < v) {

v -= u;

} else {

unsigned int diff = u - v;

u = v;

v = diff;

}

v >>= 1;

} while (v != 0); /* v가 0이 될 때까지 반복한다. GCD(u, 0) = u */

/* 처음에 계산했던 공통 인수 2의 개수(shift)만큼 왼쪽 시프트하여 최종 결과를 얻는다. */

return u << shift;

}

3. 2. Rust 언어

알고리즘에 대한 수학적 설명과 실제 효율적인 소프트웨어 구현 사이에는 몇 가지 차이점이 있다.

$2$ 로 나누는 시도 나누기 대신, 비트 시프트 연산과 후행 0 개수(trailing zeros count) 연산을 사용하는 것이 일반적이다. 이는 알고리즘의 세 번째 항등식(gcd(2u, 2v) = 2 gcd(u, v))을 반복적으로 적용하는 것과 기능적으로 동일하지만 훨씬 빠르다.
알고리즘을 반복문보다는 재귀적으로 표현하는 경우가 많다. 구현 시에는 재귀 호출을 최적화하여 반복적인 작업 부하를 줄일 수 있다. 예를 들어, 시작 시 두 번째 항등식(gcd(u, 0) = u, gcd(0, v) = v)을 처리하고, 루프에 진입할 때는 두 입력값이 모두 홀수라는 불변 조건을 유지하며 세 번째와 네 번째 항등식(gcd(u, 2v) = gcd(u, v) if u is odd, gcd(u, v) = gcd(u, |u-v|))만 처리하도록 구현할 수 있다.
루프 본문은 종료 조건( $v = 0$ )을 제외하고 분기 예측 오류를 줄이기 위해 분기 없는 코드로 작성하는 경향이 있다. 아래 예시 코드에서 $u$ 와 $v$ 를 교환하여 항상 $u \leq v$ 를 만족시키는 부분은 조건부 이동 명령어로 컴파일될 수 있다.^[5] 예측하기 어려운 분기는 프로그램 성능에 큰 부정적인 영향을 줄 수 있기 때문이다.^[3]^[4]

다음은 이러한 점들을 반영하여 Rust 언어로 작성된 이진 최대공약수 알고리즘의 예시이다. 이 코드는 [https://github.com/uutils/coreutils/blob/1eabda91cf35ec45c78cb95c77d5463607daed65/src/uu/factor/src/numeric/gcd.rs ''uutils'' coreutils] 프로젝트에서 가져왔다.

use std::cmp::min;

use std::mem::swap;

pub fn gcd(mut u: u64, mut v: u64) -> u64 {

// 기본 케이스: gcd(n, 0) = gcd(0, n) = n

if u == 0 {

return v;

} else if v == 0 {

return u;

}

// 항등식 2와 3 활용:

// gcd(2ⁱ u, 2ʲ v) = 2ᵏ gcd(u, v) 여기서 u, v는 홀수이고 k = min(i, j)

// 2ᵏ는 2ⁱ u 와 2ʲ v 모두를 나누는 2의 가장 큰 거듭제곱이다.

let i = u.trailing_zeros(); u >>= i; // u에서 2의 인수를 모두 제거하고 그 개수(i)를 센다.

let j = v.trailing_zeros(); v >>= j; // v에서 2의 인수를 모두 제거하고 그 개수(j)를 센다.

let k = min(i, j); // 공통된 2의 인수 개수 k를 구한다.

loop {

// 루프 시작 시 u와 v는 항상 홀수이다.

debug_assert!(u % 2 == 1, "u = {} should be odd", u);

debug_assert!(v % 2 == 1, "v = {} should be odd", v);

// 필요하다면 u ≤ v 가 되도록 교환한다. (분기 없는 코드로 최적화될 수 있음)

if u > v {

swap(&mut u, &mut v);

}

// 이제 u ≤ v 이다.

// 항등식 4: gcd(u, v) = gcd(u, v-u) (u ≤ v 이고 u, v 모두 홀수)

v -= u;

// v는 이제 짝수이다. (홀수 - 홀수 = 짝수)

if v == 0 {

// 항등식 1: gcd(u, 0) = u

// 최종 결과에 앞서 제거했던 공통 인수 2ᵏ를 다시 곱해준다. (왼쪽 시프트 연산)

return u << k;

}

// 항등식 3: gcd(u, 2ʲ v) = gcd(u, v) (u는 홀수)

// v에서 2의 인수를 모두 제거한다. (오른쪽 시프트 연산)

v >>= v.trailing_zeros();

// v는 다시 홀수가 된다.

}

}

'''참고''': 위의 `gcd` 함수는 부호 없는(음수가 아닌) 64비트 정수(`u64`)를 입력으로 받는다. 만약 부호 있는 정수의 최대공약수를 구해야 한다면,

\gcd(u, v) = \gcd(\pm{}u, \pm{}v)

라는 성질을 이용하여 다음과 같이 처리할 수 있다. 입력값들의 절댓값을 취한 후, 위의 `gcd` 함수를 호출하면 된다.

/// 두 개의 부호 있는 64비트 정수(i64)의 최대공약수를 계산한다.

/// 결과는 부호 없는 64비트 정수(u64)로 반환된다.

/// 참고: gcd(i64::MIN, i64::MIN) 결과는 1 << 63 이므로 i64로 표현되지 않을 수 있다.

pub fn signed_gcd(u: i64, v: i64) -> u64 {

// 입력값들의 절댓값(부호 없는 값)을 구한 뒤, 위의 gcd 함수를 호출한다.

gcd(u.unsigned_abs(), v.unsigned_abs())

}

4. 효율성

브리지트 발레(Brigitte Vallée)는 이진 최대공약수 알고리즘이 비트 연산 횟수 측면에서 평균적으로 유클리드 호제법보다 약 60% 더 효율적임을 증명했다.^[21]^[22]^[23]^[11]

그러나 점근적 복잡도 측면에서는 유클리드 호제법과 동일하다. 점근적으로 이 알고리즘은 ''O''(n) 단계를 필요로 한다. 여기서 n은 입력된 두 숫자 중 더 큰 숫자의 비트 수이다. 이는 두 단계마다 최소한 하나의 피연산자가 2로 나누어지기 때문이다. 각 단계는 뺄셈, 시프트 등 몇 가지 기본적인 산술 연산만 포함하므로 상수 시간, 즉 ''O''(1) 시간이 걸린다. 입력 숫자가 컴퓨터의 워드 크기에 맞는 경우, 각 산술 연산은 단일 기계 명령으로 처리될 수 있으므로 전체 기계 연산 횟수는 ''O''(n), 즉 ''O''(log₂(max(u, v)))에 비례한다.

임의의 크기를 가진 큰 숫자를 다룰 경우, 각 산술 연산(뺄셈 및 시프트)은 숫자의 크기(비트 수)에 비례하는 기계 연산을 필요로 한다. 따라서 알고리즘의 전체 점근적 복잡도는 ''O''(n²)이 된다.^[9] 이는 유클리드 호제법과 동일한 복잡도이다. 만약 숫자가 기계의 메모리에 표시될 수 있다면, 이 경계는 ''O''(n²/log₂ n)으로 줄어들 수 있다.

일반적으로 C 코드 등으로 구현된 이진 최대공약수 알고리즘은 현대 마이크로프로세서에서 나눗셈 연산이 상대적으로 효율적으로 처리되기 때문에, 이론적인 예상보다 실제 성능 향상이 적을 수 있다.

5. 확장

이진 최대공약수 알고리즘은 여러 방법으로 확장될 수 있다. 이를 통해 추가 정보를 출력하거나, 임의로 큰 정수를 더 효율적으로 처리하거나, 정수가 아닌 다른 영역에서 최대공약수를 계산할 수 있다.

확장 유클리드 알고리즘과 유사한 ''확장 이진 최대공약수'' 알고리즘은 최대공약수 외에 베주 계수도 제공한다. 베주 계수는 $a\cdot{}u + b\cdot{}v = \gcd(u, v)$ 를 만족하는 정수 $a$ 와 $b$ 이다.^[6]^[7]^[8]

큰 정수의 경우, 최상의 점근 복잡도는 $O(M(n) \log n)$ 인데, 여기서 $M(n)$ 은 $n$ 비트 곱셈의 비용이다. 이는 거의 선형적이어서 이진 최대공약수 알고리즘의 $O(n^2)$ 보다 훨씬 작다. 하지만 실제 구현에서는 약 64킬로비트(즉, 8×10¹⁹²⁶⁵보다 큰)보다 큰 숫자에서만 기존 알고리즘보다 성능이 뛰어나다. 이는 빠른 정수 곱셈을 위한 Schönhage–Strassen 알고리즘의 아이디어를 사용하여 이진 최대공약수 알고리즘을 확장함으로써 달성된다.^[10]

이진 최대공약수 알고리즘은 또한 가우스 정수,^[14] 아이젠슈타인 정수,^[15] 이차 링,^[16]^[17] 및 수체의 대수적 정수환과 같은 자연수가 아닌 다른 영역으로도 확장되었다.^[18]

6. 역사

고대 한나라 시대 중국에서는 두 수의 최대공약수를 계산하는 알고리즘이 분수를 약분하는 방법으로 알려져 있었다. 수학책인 《구장산술》에는 다음과 같은 방법이 제시되어 있다.

: 가능하다면 반으로 나누어라. 그렇지 않다면 분모와 분자를 가져와서 더 작은 수에서 더 큰 수를 빼고, 그 둘을 같게 만들기 위해 번갈아 가면서 그렇게 하라. 같은 수로 줄여라.

여기서 "가능하다면 반으로 나누어라"라는 구절의 해석은 명확하지 않다.^[2]

만약 두 수 중 어느 하나라도 짝수일 때 이 규칙을 적용한다면, 이 알고리즘은 이진 최대공약수 알고리즘이 된다.
반면, 두 수 모두 짝수인 경우에만 이 규칙을 적용한다면, 이 알고리즘은 유클리드 호제법과 유사해진다.

참조

_[1] 논문 Computational problems associated with Racah algebra 1967-02
_[2] 서적 Seminumerical Algorithms Addison-Wesley
_[3] 웹사이트 Avoiding the Cost of Branch Misprediction https://software.int[...] 2009-02-21
_[4] 웹사이트 Mispredicted branches can multiply your running times https://lemire.me/bl[...] 2019-10-15
_[5] 웹사이트 Compiler Explorer https://rust.godbolt[...] 2024-02-04
_[6] 기타
_[7] 서적 Handbook of Applied Cryptography http://cacr.uwaterlo[...] CRC Press 1996-10
_[8] 서적 A Course In Computational Algebraic Number Theory https://books.google[...] Springer-Verlag
_[9] 웹사이트 GNU MP 6.1.2: Binary GCD http://gmplib.org/ma[...]
_[10] 간행물 Algorithmic number theory Springer, Berlin
_[11] 논문 Average Bit-Complexity of Euclidean Algorithms https://vallee.users[...]
_[12] 학회자료 Twenty years' analysis of the Binary Euclidean Algorithm http://wwwmaths.anu.[...] 1999-09-13/15
_[13] 기술보고서 Further analysis of the Binary Euclidean algorithm https://www.cs.ox.ac[...] Oxford University Computing Laboratory 1999-11
_[14] 학술지 (1+i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm 2000-07
_[15] 학회자료 Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers 2003-08-12/15
_[16] 학회자료 Binary GCD Like Algorithms for Some Complex Quadratic Rings 2004-06-13/18
_[17] 학회자료 A New GCD Algorithm for Quadratic Number Rings with Unique Factorization 2006-03-20/24
_[18] 학회자료 On the l-Ary GCD-Algorithm in Rings of Integers 2005-07-11/15
_[19] 서적 The Art of Computer Programming, 제2권: Seminumerical Algorithms Addison-Wesley
_[20] 서적 앞의 책
_[21] 웹인용 보관된 사본 http://users.info.un[...] 2008-11-07
_[22] URL http://web.comlab.ox[...]
_[23] 기타 Notes on Programming http://www.stepanovp[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com