C++ প্রোগ্রাম: কপারস্মিথ-ফ্রাইভাল্ডস অ্যালগরিদম ইমপ্লিমেন্টেশন

এলগরিদম

ফ্রাইভাল্ডস অ্যালগরিদম একটি প্রোবাবিলিস্টিক অ্যালগরিদম যা ম্যাট্রিক্স গুণনের সঠিকতা যাচাই করে O(kn²) সময়ে। এটি তিনটি ম্যাট্রিক্স A, B, C এর জন্য যাচাই করে যে A × B = C কিনা।

ধাপসমূহ:

র‍্যান্ডম বাইনারি ভেক্টর r (০ বা ১) জেনারেট করুন।
Br, Cr, এবং A(Br) কম্পিউট করুন।
যদি A(Br) - Cr = 0 হয়, তবে গুণন সঠিক হওয়ার সম্ভাবনা বেশি।
এই প্রক্রিয়া k বার রিপিট করুন। ফেলার প্রোবাবিলিটি 2^-k।

উদাহরণ কোড

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

vector<double> matVecMul(vector<vector<double>>& M, vector<double>& v) {
    int n = M.size();
    vector<double> res(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res[i] += M[i][j] * v[j];
    return res;
}

bool freivalds(vector<vector<double>>& A, vector<vector<double>>& B,
               vector<vector<double>>& C, int k = 10) {
    int n = A.size();
    srand(time(0));

    for (int iter = 0; iter < k; iter++) {
        vector<double> r(n);
        for (int i = 0; i < n; i++) r[i] = rand() % 2;

        vector<double> Br = matVecMul(B, r);
        vector<double> Cr = matVecMul(C, r);
        vector<double> ABr = matVecMul(A, Br);

        for (int i = 0; i < n; i++)
            if (abs(ABr[i] - Cr[i]) > 1e-9)
                return false; // Definitely wrong
    }
    return true; // Probably correct
}

int main() {
    cout << "ম্যাট্রিক্সের ডাইমেনশন (n): ";
    int n; cin >> n;

    vector<vector<double>> A(n, vector<double>(n));
    vector<vector<double>> B(n, vector<double>(n));
    vector<vector<double>> C(n, vector<double>(n));

    auto readMatrix = [&](vector<vector<double>>& M, string name) {
        cout << name << " ম্যাট্রিক্স লিখুন:\n";
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> M[i][j];
    };

    readMatrix(A, "A");
    readMatrix(B, "B");
    readMatrix(C, "C");

    if (freivalds(A, B, C, 10))
        cout << "গুণন সঠিক (উচ্চ সম্ভাবনায়)।\n";
    else
        cout << "গুণন ভুল।\n";
    return 0;
}

আউটপুট উদাহরণ

ইনপুট ১:
n = 2
A = [[1,2],[3,4]]
B = [[2,0],[1,2]]
C = [[4,4],[10,8]]
আউটপুট: গুণন সঠিক (উচ্চ সম্ভাবনায়)।

ইনপুট ২:
n = 2
A = [[1,2],[3,4]]
B = [[2,0],[1,2]]
C = [[4,5],[5,5]]
আউটপুট: গুণন ভুল।

ব্যাখ্যা

ফ্রাইভাল্ডস অ্যালগরিদম বড় ম্যাট্রিক্স গুণনের ভেরিফিকেশনের জন্য দ্রুত এবং মেমরি-এফিশিয়েন্ট। ডিটারমিনিস্টিক ভেরিফিকেশনের O(n³)时间的複雜তার তুলনায় এটি অনেক দ্রুত। k বাড়ালে নির্ভুলতা বাড়ে।