Garner 알고리즘¶
중국인의 나머지 정리에 따르면 작은 정수들의 배열을 사용하여 큰 수를 표현할 수 있습니다. 예를 들어, $p$를 처음 $1000$개 소수의 곱이라고 합시다. $p$는 약 $3000$자리입니다.
$p$보다 작은 모든 수 $a$는 배열 $a_1, \ldots, a_k$로 표현할 수 있으며, 여기서 $a_i \equiv a \pmod{p_i}$입니다. 하지만 이렇게 하려면 당연히 이 표현으로부터 수 $a$를 다시 구하는 방법을 알아야 합니다. 한 가지 방법은 중국인의 나머지 정리에 관한 글에서 다룹니다.
이 글에서는 같은 목적으로 사용할 수 있는 또 다른 방법인 Garner 알고리즘을 다룹니다.
혼합 기수 표현¶
수 $a$를 혼합 기수 표현으로 나타낼 수 있습니다:
혼합 기수 표현은 위치 기수법의 하나로, 이진법이나 십진법 같은 일반적인 기수법을 일반화한 것입니다. 예를 들어, 십진법은 기수(또는 밑)가 10인 위치 기수법입니다. 모든 수는 $0$과 $9$ 사이의 숫자로 이루어진 문자열 $d_1 d_2 d_3 \dots d_n$으로 표현됩니다. 예를 들어, 문자열 $415$는 수 $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$을 나타냅니다. 일반적으로 기수가 $b$인 위치 기수법에서 숫자 문자열 $d_1 d_2 d_3 \dots d_n$은 수 $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$을 나타냅니다.
혼합 기수 체계에서는 더 이상 기수가 하나가 아닙니다. 밑이 자리마다 달라집니다.
Garner 알고리즘¶
Garner 알고리즘은 숫자 $x_1, \ldots, x_k$를 계산합니다. 이 숫자들은 비교적 작다는 점에 주목하십시오. 숫자 $x_i$는 $0$과 $p_i - 1$ 사이의 정수입니다.
$r_{ij}$를 $p_j$를 법으로 하는 $p_i$의 역원이라고 합시다
이는 모듈러 역원에서 설명한 알고리즘을 사용하여 구할 수 있습니다.
혼합 기수 표현의 $a$를 첫 번째 합동 방정식에 대입하면 다음을 얻습니다.
두 번째 방정식에 대입하면 다음과 같습니다.
이는 $x_1$을 빼고 $p_1$로 나누어 다음과 같이 다시 쓸 수 있습니다
마찬가지로 다음을 얻습니다
이제 규칙이 드러나는 것을 분명히 볼 수 있으며, 이는 다음 코드로 표현할 수 있습니다:
for (int i = 0; i < k; ++i) {
x[i] = a[i];
for (int j = 0; j < i; ++j) {
x[i] = r[j][i] * (x[i] - x[j]);
x[i] = x[i] % p[i];
if (x[i] < 0)
x[i] += p[i];
}
}
이렇게 해서 숫자 $x_i$를 $O(k^2)$ 시간에 계산하는 방법을 알아보았습니다. 이제 앞서 언급한 공식을 사용하여 수 $a$를 계산할 수 있습니다
실제로는 답 $a$를 거의 확실히 임의 정밀도 연산으로 계산해야 하지만, 숫자 $x_i$는 작기 때문에 보통 내장 자료형으로 계산할 수 있으므로 Garner 알고리즘은 매우 효율적이라는 점을 짚어 둘 만합니다.
Garner 알고리즘의 구현¶
Java는 BigInteger 클래스를 통해 큰 수를 기본적으로 지원하므로 이 알고리즘을 Java로 구현하면 편리합니다.
여기서는 큰 수를 합동 방정식들의 집합 형태로 저장할 수 있는 구현을 보여 드립니다. 이 구현은 덧셈, 뺄셈, 곱셈을 지원합니다. 그리고 Garner 알고리즘을 사용하면 이 방정식들의 집합을 유일한 정수로 변환할 수 있습니다. 이 코드에서는 $10^9$보다 큰 소수 100개를 사용하며, 이를 통해 최대 $10^{900}$ 크기의 수까지 표현할 수 있습니다.
final int SZ = 100;
int pr[] = new int[SZ];
int r[][] = new int[SZ][SZ];
void init() {
for (int x = 1000 * 1000 * 1000, i = 0; i < SZ; ++x)
if (BigInteger.valueOf(x).isProbablePrime(100))
pr[i++] = x;
for (int i = 0; i < SZ; ++i)
for (int j = i + 1; j < SZ; ++j)
r[i][j] =
BigInteger.valueOf(pr[i]).modInverse(BigInteger.valueOf(pr[j])).intValue();
}
class Number {
int a[] = new int[SZ];
public Number() {
}
public Number(int n) {
for (int i = 0; i < SZ; ++i)
a[i] = n % pr[i];
}
public Number(BigInteger n) {
for (int i = 0; i < SZ; ++i)
a[i] = n.mod(BigInteger.valueOf(pr[i])).intValue();
}
public Number add(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (a[i] + n.a[i]) % pr[i];
return result;
}
public Number subtract(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
return result;
}
public Number multiply(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (int)((a[i] * 1l * n.a[i]) % pr[i]);
return result;
}
public BigInteger bigIntegerValue(boolean can_be_negative) {
BigInteger result = BigInteger.ZERO, mult = BigInteger.ONE;
int x[] = new int[SZ];
for (int i = 0; i < SZ; ++i) {
x[i] = a[i];
for (int j = 0; j < i; ++j) {
long cur = (x[i] - x[j]) * 1l * r[j][i];
x[i] = (int)((cur % pr[i] + pr[i]) % pr[i]);
}
result = result.add(mult.multiply(BigInteger.valueOf(x[i])));
mult = mult.multiply(BigInteger.valueOf(pr[i]));
}
if (can_be_negative)
if (result.compareTo(mult.shiftRight(1)) >= 0)
result = result.subtract(mult);
return result;
}
}