#hw4.txt, 9Feb, Andrew Lohr
#Problem 1:

#x:=0
#for i from 1 to 10 do
#x:=x+i
#od:
#x;

#Problem 2:
#I read C4.txt

#Problem 3:
MatMultRG := proc(A,B) local PadA,PadB,i:
PadA := PadZeros(A):
PadB := PadZeros(B):
return [seq([op(1..nops(A),MatMultR(PadA,PadB)[i])],i=1..nops(A))]:
end:

#Problem 4:
MatScale:= proc(A,c) local i,j:
[seq([seq(c*A[i][j],j=1 .. nops(A[i]))],i=1..nops(A))]:
end:

Strassen := proc(A,B) local PadA,PadB,i:
PadA := PadZeros(A):
PadB := PadZeros(B):
return [seq([op(1..nops(A),StrassenR(PadA,PadB)[i])],i=1..nops(A))]:
end:

StrassenR := proc(A,B)  local n,i,A11,A12,A21,A22,B11,B12,B21,B22, 
M1,M2,M3,M4,M5,M6,M7,M8,C11,C12,C21,C22:
n:=nops(A):

if nops(B)<>n then
 RETURN(FAIL):
fi:

if not type(log[2](n),integer) then
     RETURN(FAIL):
fi:

if n=1 then
 RETURN([[A[1][1]*B[1][1]]]):
fi:

A11:=[seq([op(1..n/2,A[i])],i=1..n/2)]:
A12:=[seq([op(n/2+1..n,A[i])],i=1..n/2)]:
A21:=[seq([op(1..n/2,A[i])],i=n/2+1..n)]:
A22:=[seq([op(n/2+1..n,A[i])],i=n/2+1..n)]:



B11:=[seq([op(1..n/2,B[i])],i=1..n/2)]:
B12:=[seq([op(n/2+1..n,B[i])],i=1..n/2)]:
B21:=[seq([op(1..n/2,B[i])],i=n/2+1..n)]:
B22:=[seq([op(n/2+1..n,B[i])],i=n/2+1..n)]:



M1:=StrassenR(MatAdd(A11,A22),MatAdd(B11,B22)):
M2:=StrassenR(MatAdd(A21,A22),B11):
M3:=StrassenR(A11,MatAdd(B12,MatScale(B22,-1))):
M4:=StrassenR(A22,MatAdd(B21,MatScale(B11,-1))):
M5:=StrassenR(MatAdd(A11,A12),B22):
M6:=StrassenR(MatAdd(A21,MatScale(A11,-1)),MatAdd(B11,B12)):
M7:=StrassenR(MatAdd(A12,MatScale(A22,-1)),MatAdd(B21,B22)):
 
C11:=MatAdd(MatAdd(M1,M4),MatAdd(MatScale(M5,-1),M7)):
C12:=MatAdd(M3,M5):
C21:=MatAdd(M2,M4):
C22:=MatAdd(MatAdd(M1,MatScale(M2,-1)),MatAdd(M3,M6)):

[seq([op(C11[i]),op(C12[i])],i=1..nops(C11)),
seq([op(C21[i]),op(C22[i])],i=1..nops(C21))]:

end:

#Problem 5:
RandMat:=proc(n,R) local ra,i,j:
ra:=rand(-R..R):
[seq([seq(ra(),j=1..n)],i=1..n)]:
end:

#Problem 6:

#MatMultR 64x64 time = 314.137
#Strassen 64x64 time = 323.038
#for 128x128, runtimes were too long