โปรแกรม C++ ใช้งานอัลกอริทึม Coppersmith-Freivald

อัลกอริทึม Freivalds ใช้ตรวจสอบว่าการคูณเมทริกซ์ถูกต้องหรือไม่ โดยมีโอกาสผิดพลาดน้อยกว่า 2^-k ในเวลา O(kn^2)

อัลกอริทึม

Begin
  รับ matrix1(n*n), matrix2(n*n), matrix3(n*n)
  // ตามอัลกอริทึม ต้องตรวจสอบ: matrix1 × matrix2 = matrix3
  1) เลือกเวกเตอร์ a[n][1] แบบสุ่มและสม่ำเสมอ ซึ่งองค์ประกอบจะเป็น 0 หรือ 1
  2) คำนวณ matrix2 * a, matrix3 * a แล้ว matrix1 * (matrix2 * a) เพื่อประเมินนิพจน์ matrix1 * (matrix2 * a) - matrix3 * a
  3) ตรวจสอบว่า matrix1 * (matrix2 * a) - matrix3 * a = 0 หรือไม่
  4) ถ้าเป็นศูนย์ การคูณเมทริกซ์ถูกต้อง ไม่ใช่ถ้าผิด
End

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

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main(int argc, char **argv) {
  cout << "Enter the dimension of the matrices: ";
  int n;
  cin >> n;
  cout << "Enter the 1st matrix: ";
  double matrix1[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> matrix1[i][j];
    }
  }
  cout << "Enter the 2nd matrix: ";
  double matrix2[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> matrix2[i][j];
    }
  }
  cout << "Enter the result matrix: ";
  double matrix3[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> matrix3[i][j];
    }
  }
  double a[n][1];
  for (int i = 0; i < n; i++) {
    a[i][0] = rand() % 2;
  }
  double matrix2a[n][1];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1; j++) {
      for (int k = 0; k < n; k++) {
        matrix2a[i][j] += matrix2[i][k] * a[k][j];
      }
    }
  }
  double matrix3a[n][1];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1; j++) {
      for (int k = 0; k < n; k++) {
        matrix3a[i][j] += matrix3[i][k] * a[k][j];
      }
    }
  }
  double matrix12a[n][1];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1; j++) {
      for (int k = 0; k < n; k++) {
        matrix12a[i][j] += matrix1[i][k] * matrix2a[k][j];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    matrix12a[i][0] -= matrix3a[i][0];
  }
  bool flag = true;
  for (int i = 0; i < n; i++) {
    if (matrix12a[i][0] == 0) continue;
    else flag = false;
  }
  if (flag == true)
    cout << "This is the resultant matrix";
  else
    cout << "This is not the resultant matrix";
}

ผลลัพธ์ที่ 1

Enter the dimension of the matrices: 2
Enter the 1st matrix: 1 2 3 4
Enter the 2nd matrix: 2 0 1 2
Enter the result matrix: 4 4 10 8
This is the resultant matrix

ผลลัพธ์ที่ 2

Enter the dimension of the matrices: 2
Enter the 1st matrix: 1 2 3 4
Enter the 2nd matrix: 2 0 1 2
Enter the result matrix: 4 5 5 5
This is not the resultant matrix