C++ প্রোগ্রাম: শোনহেজ-স্ট্রাসেন অ্যালগরিদম বাস্তবায়ন দুটি নম্বর গুণ করার জন্য

শোনহেজ-স্ট্রাসেন অ্যালগরিদম দুটি নম্বর গুণ করতে ব্যবহৃত হয়। শোনহেজ-স্ট্রাসেন অ্যালগরিদম বড় ইন্টিজারের জন্য একটি অ্যাসিম্পটটিক্যালি ফাস্ট মাল্টিপ্লিকেশন অ্যালগরিদম। প্র্যাকটিসে শোনহেজ-স্ট্রাসেন অ্যালগরিদম ২²¹⁵ থেকে ২²¹⁷ (১০,০০০ থেকে ৪০,০০০ ডেসিমেল) ডিজিটের বড় নম্বরের জন্য করাতসুবা এবং টুম-কুক পদ্ধতির চেয়ে আউটপারফর্ম করা শুরু করে।

অ্যালগরিদম

শুরু
  function noOfDigit( x)
    একটি ভেরিয়েবল n ডিক্লেয়ার করুন এবং n = 0 অ্যাসাইন করুন
    while (x > 0)
      x = x /10
      n ইনক্রিমেন্ট করুন
    return n
শেষ
শুরু
  Algorithm for schonhageStrassenMultiplication:
  schonhageStrassenMultiplication(a, b, n, m)
  linearConvolution[n + m - 1] নামক একটি অ্যারে ডিফাইন করুন
  for i = 0 to (n + m - 1)-1
    linearConvolution[i] = 0;
    long p = a
    for i = 0 to m-1
      a = p
      for j = 0 to n-1
        linearConvolution[i + j] += (b mod 10) * (a mod 10);
        a /= 10
        b /= 10
  for i = (n + m - 2) to 0
    Print linearConvolution[i]
    long product = 0
    nextCarry = 0, base = 1
    for i = 0 to (n + m - 1)-1
      linearConvolution[i] += nextCarry;
      product = product + (base * (linearConvolution[i] % 10));
      nextCarry = linearConvolution[i] / 10;
      base *= 10;
    নম্বরগুলোর প্রোডাক্ট প্রিন্ট করুন।
শেষ

উদাহরণ কোড

#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