임의 정밀도 연산¶

임의 정밀도 연산은 "bignum" 또는 간단히 "긴 연산(long arithmetic)"이라고도 합니다. 표준 자료형에 담을 수 있는 것보다 훨씬 큰 수를 처리할 수 있게 해 주는 자료 구조와 알고리즘의 집합입니다. 다음은 임의 정밀도 연산의 몇 가지 유형입니다.

고전적인 정수 긴 연산¶

핵심 아이디어는 수를 어떤 진법의 "자릿수"들로 이루어진 배열로 저장하는 것입니다. 가장 자주 사용되는 진법으로는 10진법, 10의 거듭제곱($10^4$ 또는 $10^9$), 그리고 2진법이 있습니다.

이러한 형태의 수에 대한 연산은 세로셈으로 하는 덧셈, 뺄셈, 곱셈, 나눗셈이라는 "학교에서 배우는" 알고리즘으로 수행합니다. 빠른 곱셈 알고리즘인 고속 푸리에 변환과 Karatsuba 알고리즘을 사용할 수도 있습니다.

여기서는 음이 아닌 정수에 대한 긴 연산만 설명합니다. 음의 정수도 처리하도록 알고리즘을 확장하려면 "음수" 플래그를 추가로 도입하여 관리하거나 2의 보수 정수 표현을 사용해야 합니다.

자료 구조¶

수는 vector<int>로 저장하며, 각 원소는 수의 한 "자릿수"입니다.

typedef vector<int> lnum;

성능을 높이기 위해 $10^9$을 밑으로 사용합니다. 그러면 긴 수의 각 "자릿수"에는 10진 자릿수 9개가 한꺼번에 담깁니다.

const int base = 1000*1000*1000;

자릿수는 가장 낮은 자리부터 가장 높은 자리 순으로 저장합니다. 모든 연산은 피연산자에 선행 0이 없다면 각 연산이 끝난 뒤 결과에도 선행 0이 없도록 구현합니다. 결과에 선행 0이 생길 수 있는 모든 연산 뒤에는 이를 제거하는 코드가 있어야 합니다. 이 표현에서는 수 0을 올바르게 나타내는 표기가 두 가지, 즉 빈 벡터와 0인 자릿수 하나만 담긴 벡터가 있다는 점에 유의하십시오.

출력¶

긴 정수를 출력하는 것은 가장 쉬운 연산입니다. 먼저 벡터의 마지막 원소를 출력하고(벡터가 비어 있으면 0을 출력합니다), 이어서 나머지 원소들을 필요한 경우 선행 0으로 채워 정확히 9자리가 되도록 출력합니다.

printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
    printf ("%09d", a[i]);

벡터의 원소가 2개보다 적을 때 부호 없는 정수 언더플로가 일어나지 않도록 a.size()를 정수로 형변환한다는 점에 유의하십시오.

입력¶

긴 정수를 읽으려면 그 표기를 string으로 읽은 다음 "자릿수"로 변환합니다:

for (int i=(int)s.length(); i>0; i-=9)
    if (i < 9)
        a.push_back (atoi (s.substr (0, i).c_str()));
    else
        a.push_back (atoi (s.substr (i-9, 9).c_str()));

string 대신 char 배열을 사용하면 코드가 더욱 짧아집니다:

for (int i=(int)strlen(s); i>0; i-=9) {
    s[i] = 0;
    a.push_back (atoi (i>=9 ? s+i-9 : s));
}

입력에 선행 0이 있을 수 있다면 다음과 같이 제거할 수 있습니다:

while (a.size() > 1 && a.back() == 0)
    a.pop_back();

덧셈¶

긴 정수 $a$에 $b$를 더하고 결과를 $a$에 저장합니다:

int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    a[i] += carry + (i < b.size() ? b[i] : 0);
    carry = a[i] >= base;
    if (carry)  a[i] -= base;
}

뺄셈¶

긴 정수 $a$에서 $b$를 빼고($a \ge b$) 결과를 $a$에 저장합니다:

int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
    a[i] -= carry + (i < b.size() ? b[i] : 0);
    carry = a[i] < 0;
    if (carry)  a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

긴 정수에는 선행 0이 없다는 전제를 지키기 위해 뺄셈을 수행한 뒤 선행 0을 제거한다는 점에 유의하십시오.

짧은 정수와의 곱셈¶

긴 정수 $a$에 짧은 정수 $b$($b < base$)를 곱하고 결과를 $a$에 저장합니다:

int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    long long cur = carry + a[i] * 1ll * b;
    a[i] = int (cur % base);
    carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

추가 최적화: 실행 시간이 매우 중요하다면, 나눗셈의 정수 결과(변수 carry)만 구한 뒤 이를 이용해 곱셈으로 나머지를 구하는 방식으로 두 번의 나눗셈을 한 번으로 줄여 볼 수 있습니다. 이렇게 하면 극적이지는 않지만 보통 코드가 더 빨라집니다.

긴 정수와의 곱셈¶

긴 정수 $a$와 $b$를 곱하고 그 결과를 $c$에 저장합니다:

lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
    for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
        long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
        c[i+j] = int (cur % base);
        carry = int (cur / base);
    }
while (c.size() > 1 && c.back() == 0)
    c.pop_back();

짧은 정수로 나누기¶

긴 정수 $a$를 짧은 정수 $b$($b < base$)로 나누고, 정수 결과는 $a$에, 나머지는 carry에 저장합니다:

int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
    long long cur = a[i] + carry * 1ll * base;
    a[i] = int (cur / b);
    carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

소인수분해 표현을 이용한 긴 정수 연산¶

이 방법의 아이디어는 정수를 소인수분해 형태, 즉 그 정수를 나누는 소수들의 거듭제곱으로 저장하는 것입니다.

이 방법은 구현하기가 매우 쉽고 곱셈과 나눗셈을 (고전적인 방법보다 점근적으로 더 빠르게) 쉽게 수행할 수 있지만, 덧셈이나 뺄셈은 할 수 없습니다. 또한 고전적인 방법에 비해 메모리 효율이 매우 높습니다.

이 방법은 소수가 아닌 수 M을 법으로 하는 계산에 자주 사용됩니다. 이 경우 수는 M의 약수 중 그 수를 나누는 것들의 거듭제곱과, M을 법으로 한 나머지로 저장됩니다.

소수 모듈러에서의 긴 정수 연산 (Garner 알고리즘)¶

이 방법의 아이디어는 소수들의 집합을 선택하고(보통 이 소수들은 표준 정수 자료형에 들어갈 만큼 작습니다), 정수를 그 각각의 소수로 나눈 나머지들의 벡터로 저장하는 것입니다.

중국인의 나머지 정리에 따르면 이 표현은 0부터 이 소수들의 곱에서 1을 뺀 값까지의 모든 수를 유일하게 복원하기에 충분합니다. Garner 알고리즘을 사용하면 이러한 표현으로부터 수를 일반 정수로 복원할 수 있습니다.

이 방법은 고전적인 방법에 비해 메모리를 절약할 수 있습니다(다만 절약 효과는 소인수분해 표현만큼 극적이지는 않습니다). 또한 모듈러로 사용하는 소수의 개수에 비례하는 시간에 덧셈, 뺄셈, 곱셈을 빠르게 수행할 수 있습니다(구현은 중국인의 나머지 정리 문서를 참고하십시오).

대신 정수를 다시 일반 형태로 변환하는 작업이 상당히 번거롭고, 곱셈을 포함한 고전적인 임의 정밀도 연산을 구현해야 한다는 단점이 있습니다. 게다가 이 방법은 나눗셈을 지원하지 않습니다.

분수 임의 정밀도 연산¶

프로그래밍 대회에서 분수는 정수보다 덜 자주 등장하고, 분수에 대한 긴 연산은 구현하기가 훨씬 까다롭기 때문에 프로그래밍 대회에서는 분수 긴 연산의 아주 작은 일부만 다룹니다.

기약분수에서의 연산¶

수는 기약분수 $\frac{a}{b}$로 표현되며, 여기서 $a$와 $b$는 정수입니다. 분수에 대한 모든 연산은 이 분수들의 정수 분자와 분모에 대한 연산으로 표현할 수 있습니다. 보통 분자와 분모를 저장하려면 고전적인 임의 정밀도 연산을 사용해야 하지만, 때로는 내장 64비트 정수 자료형으로도 충분합니다.

부동소수점 위치를 별도의 자료형으로 저장하기¶

때때로 문제에서 오버플로나 언더플로 없이 매우 작거나 매우 큰 수를 다뤄야 하는 경우가 있습니다. 내장 double 자료형은 8-10바이트를 사용하며 지수 값으로 $[-308; 308]$ 범위를 허용하는데, 이는 때때로 부족할 수 있습니다.

방법은 매우 간단합니다. 별도의 정수 변수를 사용해 지수 값을 저장하고, 각 연산 후에 부동소수점 수를 정규화합니다. 즉, 지수를 적절히 조정하여 수를 $[0.1; 1)$ 구간으로 되돌립니다.

이러한 두 수를 곱하거나 나눌 때는 각각 지수를 더하거나 빼야 합니다. 수를 더하거나 뺄 때는 먼저 둘 중 하나에 지수 값의 차이만큼 10을 거듭제곱한 값을 곱하여 공통 지수로 맞춰야 합니다.

마지막으로, 지수의 밑이 반드시 10일 필요는 없습니다. 부동소수점 수의 내부 표현을 고려하면 지수의 밑으로 2를 사용하는 것이 가장 합리적입니다.