This is the java implementation of classic Coppersmith-Freivalds’ algorithm to check whether the multiplication of matrix A and B equals the given matrix C. It does it by checking A*(B*r)-(C*r) where r is any random column vector consisting only 0/1 as its elements. If this value is zero algorithm prints Yes, No otherwise.
Here is the source code of the Java Program to Implement Coppersmith Freivald’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a sample program to check whether the matrix c is equal to the multiplication of a and b //implementation of Coppersmith Freivalds Algorithm import java.util.Random; import java.util.Scanner; public class Coppersmith_Freivalds_Algorithm { public static void main(String args[]) { System.out.println("Enter the dimesion of the matrices: "); Scanner input = new Scanner(System.in); int n = input.nextInt(); System.out.println("Enter the 1st matrix: "); double a[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { a[i][j] = input.nextDouble(); } } System.out.println("Enter the 2st matrix: "); double b[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { b[i][j] = input.nextDouble(); } } System.out.println("Enter the result matrix: "); double c[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { c[i][j] = input.nextDouble(); } } //random generation of the r vector containing only 0/1 as its elements double [][]r = new double[n][1]; Random random = new Random(); for(int i=0; i<n; i++) { r[i][0] = random.nextInt(2); } //test A * (b*r) - (C*) = 0 double br[][] = new double[n][1]; double cr[][] = new double[n][1]; double abr[][] = new double[n][1]; br = multiplyVector(b, r, n); cr = multiplyVector(c, r, n); abr = multiplyVector(a, br, n); //check for all zeros in abr boolean flag = true; for(int i=0; i<n; i++) { if(abr[i][0] == 0) continue; else flag = false; } if(flag == true) System.out.println("Yes"); else System.out.println("No"); input.close(); } public static double[][] multiplyVector(double[][] a, double[][] b, int n) { double result[][] = new double[n][1]; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { for (int k = 0; k < n; k++) { result[i][j] = result[i][j] + a[i][k] * b[k][j]; } } } return result; } }
Output:
$ javac Coppersmith_Freivalds_Algorithm.java $ java Coppersmith_Freivalds_Algorithm Enter the dimesion of the matrices: 2 Enter the 1st matrix: 2 3 3 4 Enter the 2st matrix: 1 0 1 2 Enter the result matrix: 6 5 8 7 Yes
Related posts:
Interface trong Java 8 – Default method và Static method
Extract links from an HTML page
Introduction to Apache Commons Text
Guide to Spring Cloud Kubernetes
Java Program to Compute Cross Product of Two Vectors
Jackson Annotation Examples
Spring Data JPA @Query
Java Program to Implement Sorted List
Java Program to Implement Self organizing List
Java Program to Implement ArrayDeque API
Java Program to Implement Stack using Two Queues
Consumer trong Java 8
Java – Random Long, Float, Integer and Double
Java Program to Implement Efficient O(log n) Fibonacci generator
Jackson – Bidirectional Relationships
Creating a Web Application with Spring 5
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Spring RestTemplate Error Handling
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Command-Line Arguments in Java
Reactive WebSockets with Spring 5
Hướng dẫn Java Design Pattern – Iterator
Guide to the Volatile Keyword in Java
Java List UnsupportedOperationException
Introduction to Spring Cloud Rest Client with Netflix Ribbon
Java Program to Implement Gaussian Elimination Algorithm
Java Program to Implement LinkedBlockingQueue API
Java – String to Reader
Tính đóng gói (Encapsulation) trong java
Giới thiệu luồng vào ra (I/O) trong Java
Spring Boot - Runners