โปรแกรม C++ ใช้ Schonhage-Strassen Algorithm คูณเลขใหญ่

Schonhage-Strassen Algorithm ใช้สำหรับคูณสองจำนวน อัลกอริทึมนี้เป็นการคูณแบบ asymptotically fast สำหรับจำนวนเต็มขนาดใหญ่ ในทางปฏิบัติ Schonhage-Strassen เริ่มเกินกว่าวิธีเก่าๆ เช่น Karatsuba และ Toom-Cook สำหรับตัวเลขเกิน 2^2^15 ถึง 2^2^17 (10,000 ถึง 40,000 หลักสิบ)

อัลกอริทึม

Begin
    function noOfDigit(x)
        ประกาศตัวแปร n กำหนด n = 0
        while (x > 0)
            x = x / 10
            เพิ่ม n
        return n
End

Begin
    Algorithm สำหรับ schonhageStrassenMultiplication:
    schonhageStrassenMultiplication(a, b, n, m)
    กำหนดอาร์เรย์ linearConvolution[n + m - 1]
    for i = 0 ถึง (n + m - 1)-1
        linearConvolution[i] = 0
    long p = a
    for i = 0 ถึง m-1
        a = p
        for j = 0 ถึง n-1
            linearConvolution[i + j] += (b mod 10) * (a mod 10)
            a /= 10
            b /= 10
    for i = (n + m - 2) ถึง 0
        พิมพ์ linearConvolution[i]
        long product = 0
        nextCarry = 0, base = 1
        for i = 0 ถึง (n + m - 1)-1
            linearConvolution[i] += nextCarry
            product = product + (base * (linearConvolution[i] % 10))
            nextCarry = linearConvolution[i] / 10
            base *= 10
        พิมพ์ผลคูณของตัวเลข
End

ตัวอย่างโค้ด

#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 << "The Linear Convolution is: ( ";
    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 << "\nThe Product of the numbers is: " << product;
}

int main(int argc, char **argv) {
    cout << "Enter the numbers:";
    long a, b;
    cin >> a >> b;
    int n = noOfDigit(a);
    int m = noOfDigit(b);
    schonhageStrassenMultiplication(a, b, n, m);
}

ผลลัพธ์

Enter the numbers:1234 5679
The Linear Convolution is: ( 5 16 34 61 63 55 36 )
The Product of the numbers is: 7007886