Strassen and large number multiplication implementation - 15/10/2017 22:13 EDT

1) Implement Strassen’s matrix multiplication algorithm. Your program should take an input variable n (=2k where k is a positive integer, 1≤n≤ 1,024) in the Linux command line and generate two n*n random integer matrices, A and B. To avoid the integer overflow, please generate the maximum random integer as root(maximum integer/n) for each input variable n. Compute A*B using Strassen’s algorithm and compare the result to the result produced by the standard matrix multiplication algorithm with O(n3) time complexity. Print the results, if correct. (If incorrect results are produced, no credit will be given. Your program should work for any matrices. If it works for specific matrices but doesn’t work for other matrices, no credit will be given.) 2. Implement Large Integer Multiplication algorithm (image attached). Modify your algorithm so that it divides each n-digit integer into three smaller integers of n/3 digits. Your programs should take a input variable n(=6k where k is a positive integer) in the Linux command line and generate two n-digit random integers (the most significant digit is between 1 and 9, not 0), A and B. Compute A*B using original algorithm and the algorithm you modified. Please make sure that you get the same results for the two algorithms. Print the results, if correct. No credit will be given if the algorithm is incorrectly implemented, the time complexity of your program is higher than O(n2 ), or your program only works for specific k values. The code should be written in relatively simple constructs(using arrays) and easy to understand so can be explained and understood.