# Python3 code
#
# Matrix multiplication in linear time with total matrix size,
# true only when entries are natural numbers or zero.
#
# ---------------------------------------------------
#
# To convert tabs to spaces use the expand command.
# See https://www.rhyscitlema.com/about/codingstyle.html
#
# Provided by Rhyscitlema
# https://www.rhyscitlema.com/algorithms/matrix-multiplication
#
# USE AT YOUR OWN RISK!
#
# note: disable line 170 if dealing with large input
def naive_time_algorithm (n, v, m, D, M, naive_time_R):
for i in range(n):
for j in range(m):
naive_time_R[i][j]=0
for k in range(v):
naive_time_R[i][j] += D[i][k] * M[k][j]
def linear_time_algorithm (n, v, m, D, M, linear_time_R):
# please refer to the quoted website above for detail explanation of this algorithm.
# beware of how floor() is used here, floor(7/5) = 7//5.
# first, 2v(n+m) operations are performed so to get the largest entry, L, of the two input matrices D and M.
L=0
for i in range(n):
for j in range(v):
if (D[i][j]>L): L = D[i][j]
for i in range(v):
for j in range(m):
if (M[i][j]>L): L = M[i][j]
# L is now modified to the 'base L number' (see details of the algorithm).
# consider 4 operations performed.
L = L*L*v + 1
# second, 2m-1 operations are performed so to store the x, y, z, ... coefficients,
# note that some of them are very large numbers.
coef = [0]*m
coef[0]=1
for i in range(1, m):
coef[i] = coef[i-1]*L
# third, 2vm operations are performed so to store the array S.
S = [0]*v
for i in range(v):
S[i]=0
for j in range(m):
S[i] += M[i][j]*coef[j] # this is where the second matrix M is used
# fourth, 2nv operations are performed so to store the biggest values in this algorithms, the array T.
# T incorporates the basic idea behind the algorithm.
T = [0]*n
for i in range(n):
T[i]=0
for j in range(v):
T[i] += D[i][j]*S[j] # this is where the first matrix D is used
# fifth and last, 3nm-n operations are performed so to get the final output values for the resulting matrix R.
# we need and have: L, coef and T.
for i in range(n):
for j in range(m-1):
linear_time_R[i][j] = ( T[i] % coef[j+1] ) // coef[j]
linear_time_R[i][m-1] = T[i]//coef[m-1] # recall: T[any] < L^m
# total number of operations = 3nm + 4v(n+m) + 2m-n+3 .
# print overall result to screen
def printoutput (n, v, m, D, M, naive_time_R, linear_time_R):
print(" *** Output is as shown below ***")
print("D (", n, "-by-", v, ") :", sep="")
for i in range(n):
for j in range(v):
print("{:4}".format(D[i][j]), end=" ")
print()
print()
print("M (", v, "-by-", m, ") :", sep="")
for i in range(v):
for j in range(m):
print("{:4}".format(M[i][j]), end=" ")
print()
print()
print("Naive_time_R (", n, "-by-", m, ") :", sep="")
for i in range(n):
for j in range(m):
print("{:4}".format(naive_time_R[i][j]), end=" ")
print()
print()
print("Linear_time_R (", n, "-by-", m, ") :", sep="")
for i in range(n):
for j in range(m):
print("{:4}".format(linear_time_R[i][j]), end=" ")
print()
print()
# ******* START *******
print("\tThe program is of the form:")
print("\tInput matrix D = (n-by-v)")
print("\tInput matrix M = (v-by-m)")
print("\tOutput matrix R = (n-by-m)")
print()
# get the sizes of the matrices
n = eval(input("Enter n : "))
v = eval(input("Enter v : "))
m = eval(input("Enter m : "))
# initialise the matrices D, M and R
D=[] # n-by-v
M=[] # v-by-m
naive_time_R=[] # n-by-m
linear_time_R=[] # n-by-m
for i in range(n):
D.append([0]*v)
for i in range(v):
M.append([0]*m)
for i in range(n):
naive_time_R.append([0]*m)
linear_time_R.append([0]*m)
# randomly generate input matrices entries, from 0 to but excluding n
import random
for i in range(n):
for j in range(v):
D[i][j] = random.randrange(n)
for i in range(v):
for j in range(m):
M[i][j] = random.randrange(m)
for i in range(n):
for j in range(m):
naive_time_R[i][j] = -1 # just for sake of initialisation, but can be removed
linear_time_R[i][j] = -1
# calling the two functions
print("\nNaive_time algorithm is running ...")
naive_time_algorithm (n, v, m, D, M, naive_time_R)
print("Done.\n")
print("linear_time algorithm is running ...")
linear_time_algorithm (n, v, m, D, M, linear_time_R)
print("Done.\n")
printoutput (n, v, m, D, M, naive_time_R, linear_time_R) # disable this line if dealing with large input of m
# verify if the two output matrices are equal
k=0
for i in range(n):
for j in range(m):
if naive_time_R[i][j] != linear_time_R[i][j]:
k=1
break
if k: break
if k: print("Different output matrices.")
else: print("Equal output matrices.")
print()