C++로 구현하는 Schönhage-Strassen 알고리즘: 두 숫자의 곱셈 프로그램

Schönhage-Strassen(숀하게-스트라센) 알고리즘은 두 개의 수를 곱하는 데 사용되는 알고리즘으로, 특히 아주 큰 정수에 대해 점근적으로 빠른 성능을 보이는 곱셈 방식입니다.

실제 환경에서 이 알고리즘은 2^2¹⁵ ~ 2^2¹⁷(십진수 약 10,000 ~ 40,000자리) 범위를 넘는 숫자에 대해 카라추바(Karatsuba), 툼-쿡(Toom-Cook)과 같은 기존 방법보다 우수한 성능을 발휘하기 시작합니다.

알고리즘

아래 의사 코드는 각 수의 자릿수를 구하고, 선형 컨볼루션(linear convolution)을 계산한 후, 자릿수 올림(carry)을 반영하여 최종 곱을 구하는 과정을 보여줍니다.

시작
    함수 noOfDigit(x)
    변수 n을 선언하고 n = 0으로 초기화
    while (x > 0)
        x = x / 10
        n 증가
    n 반환
종료

시작
    schonhageStrassenMultiplication 알고리즘:
    schonhageStrassenMultiplication(a, b, n, m)
    배열 linearConvolution[n + m - 1] 선언
    i = 0부터 (n + m - 1) - 1까지
        linearConvolution[i] = 0
        long p = a
    i = 0부터 m - 1까지
        a = p
        j = 0부터 n - 1까지
            linearConvolution[i + j] += (b mod 10) * (a mod 10)
            a /= 10
            b /= 10
    i = (n + m - 2)부터 0까지
        linearConvolution[i] 출력
        long product = 0
        nextCarry = 0, base = 1
    i = 0부터 (n + m - 1) - 1까지
        linearConvolution[i] += nextCarry
        product = product + (base * (linearConvolution[i] % 10))
        nextCarry = linearConvolution[i] / 10
        base *= 10
    두 수의 곱(product) 출력
종료

핵심 단계 요약

1단계: noOfDigit 함수를 통해 입력된 두 수의 자릿수 n, m을 구합니다.
2단계: 길이가 n + m − 1인 선형 컨볼루션 배열을 0으로 초기화합니다.
3단계: 두 수의 각 자릿수를 서로 곱한 값을 인덱스별로 누적하여 선형 컨볼루션을 만듭니다.
4단계: 컨볼루션 배열의 각 항목에 자릿수 올림(nextCarry)을 적용하고, 낮은 자릿수부터 차례대로 더해 최종 곱(product)을 완성합니다.

C++ 예제 코드

#include <iostream>
using namespace std;

// 수의 자릿수를 구하는 함수
int noOfDigit(long x) {
    int n = 0;
    while (x > 0) {
        x /= 10;
        n++;
    }
    return n;
}

// Schonhage-Strassen 곱셈 수행 함수
void schonhageStrassenMultiplication(long a, long b, int n, int m) {
    // 선형 컨볼루션 배열을 0으로 초기화
    int linearConvolution[n + m - 1];
    for (int i = 0; i < (n + m - 1); i++)
        linearConvolution[i] = 0;

    long p = a;

    // 각 자릿수 곱을 누적하여 선형 컨볼루션 계산
    for (int i = 0; i < m; i++) {
        a = p;
        for (int j = 0; j < n; j++) {
            linearConvolution[i + j] += (b % 10) * (a % 10);
            a /= 10;
        }
        b /= 10;
    }

    cout << "선형 컨볼루션: ( ";
    for (int i = (n + m - 2); i >= 0; i--) {
        cout << linearConvolution[i] << " ";
    }
    cout << ")";

    // 자릿수 올림을 처리하여 최종 곱 계산
    long product = 0;
    int nextCarry = 0, base = 1;
    for (int i = 0; i < n + m - 1; i++) {
        linearConvolution[i] += nextCarry;
        product = product + (base * (linearConvolution[i] % 10));
        nextCarry = linearConvolution[i] / 10;
        base *= 10;
    }
    cout << "\n두 수의 곱: " << product;
}

int main(int argc, char **argv) {
    cout << "숫자를 입력하세요: ";
    long a, b;
    cin >> a >> b;
    int n = noOfDigit(a);
    int m = noOfDigit(b);
    schonhageStrassenMultiplication(a, b, n, m);
}

참고: 위 코드의 int linearConvolution[n + m - 1]처럼 크기를 변수로 지정하는 가변 길이 배열(VLA)은 표준 C++ 사양이 아니므로, 이식성을 높이려면 std::vector<int> 사용을 권장합니다.

실행 결과

숫자를 입력하세요: 1234 5679
선형 컨볼루션: ( 5 16 34 61 63 55 36 )
두 수의 곱: 7007886

위 실행 결과에서 선형 컨볼루션 값에 자릿수 올림을 차례로 적용하면 1234 × 5679 = 7007886이라는 최종 곱이 도출됩니다. Schönhage-Strassen 알고리즘의 시간 복잡도는 O(n log n · log log n)으로, 다루는 숫자의 자릿수가 많아질수록 학교식 곱셈(O(n²))이나 카라추바 알고리즘보다 훨씬 유리합니다.