Chương trình C++ triển khai thuật toán Schonhage-Strassen nhân hai số

Thuật toán Schonhage-Strassen được dùng để nhân hai số. Thuật toán Schonhage-Strassen là một thuật toán nhân nhanh tiệm cận (asymptotically fast) cho các số nguyên lớn. Trong thực tế, thuật toán Schonhage-Strassen bắt đầu vượt trội hơn các phương pháp cũ như Karatsuba và Toom-Cook cho các số vượt quá 2²¹⁵ đến 2²¹⁷ (10,000 đến 40,000 chữ số thập phân).

Thuật toán

Bắt đầu
    hàm noOfDigit(x)
    Khai báo biến n và gán n = 0;
    Khi (x > 0)
        x = x / 10
        Tăng n
    Trả về n
Kết thúc
Bắt đầu
    Thuật toán cho schonhageStrassenMultiplication:
    schonhageStrassenMultiplication(a, b, n, m)
    Định nghĩa mảng linearConvolution[n + m - 1]
    Với i = 0 đến (n + m - 1) - 1
        linearConvolution[i] = 0;
        long p = a
    Với i = 0 đến m-1
        a = p
        Với j = 0 đến n-1
            linearConvolution[i + j] += (b mod 10) * (a mod 10);
            a /= 10
            b /= 10
    Với i = (n + m - 2) đến 0
        In linearConvolution[i]
        long product = 0
        nextCarry = 0, base = 1
        Với i = 0 đến (n + m - 1) - 1
            linearConvolution[i] += nextCarry;
            product = product + (base * (linearConvolution[i] % 10));
            nextCarry = linearConvolution[i] / 10;
            base *= 10;
        In tích của các số.
Kết thúc

Mã ví dụ

#include <iostream> 
using namespace std; 

int noOfDigit(long x) { 
    int n = 0; 
    while (x > 0) { 
        x /= 10; 
        n++; 
    } 
    return n; 
} 

void schonhageStrassenMultiplication(long a, long b, int n, int m) { 
    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 << "Tích chập tuyến tính (Linear Convolution) là: ( "; 
    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 << "\nTích của các số là: " << product; 
} 

int main(int argc, char **argv) { 
    cout << "Nhập các số: "; 
    long a, b; 
    cin >> a >> b; 
    int n = noOfDigit(a); 
    int m = noOfDigit(b); 
    schonhageStrassenMultiplication(a, b, n, m); 
}

Kết quả

Nhập các số: 1234 5679 
Tích chập tuyến tính (Linear Convolution) là: ( 5 16 34 61 63 55 36 ) 
Tích của các số là: 7007886