# Implement Strassen's algorithm [closed]

Strassen's algorithm was the first method of matrix multiplication in subcubic time complexity, namely O(n**log2(7)) for a pair of n*n matrices (assuming the numbers therein are large enough that their O(n*log2(n)) exact multiplication has become the constraint on your performance, and any nested structures and function calls are negligible in comparison).

For a 2*2 matrix, it is defined as

lambda a,b: (lambda a,b,c,d,e,f,g: (a+d-e+g,c+e,b+d,a-b+c+f))((a+a)*(b+b),(a+a)*b,a*(b-b),a*(b-b),(a+a)*b,(a-a)*(b+b),(a-a)*(b+b))


And for larger square ones, as splitting them into quarters and then calling this but with numbers' addition, negation and multiplication methods substituted for matrices' (notably using itself for the latter, its seven self-calls per doubling of the width and height being the reason for the exponent).

For simplicity (so you won't need to deal with implementing standard matrix multiplication and subdividing into Strassen-able ones), your inputs will be two 2**n*2**n matrices of integers, represented as length-2**(2*n) tuples (or lists or your language's equivalent), encoded with elements in reading order, and you will return another such tuple. For instance, when inputted with these two

(5,2,0,0,
4,0,5,2,
3,4,5,0,
3,1,4,2)

(7,4,5,3,
4,0,2,7,
1,4,1,1,
0,5,3,5)


, it should return

(43,20,29,29,
33,46,31,27,
42,32,28,42,
29,38,27,30)

• Welcome to Code Golf! I've closed this question as it is missing an objective scoring criteria. For future reference, we recommend using the Sandbox to get feedback on challenge ideas before posting them to main Dec 21, 2022 at 1:06
• The requirement that answers implement this specific algorithm is unobservable - also see this Dec 21, 2022 at 3:52
– Simd
Dec 21, 2022 at 4:14
• I’m voting to close this question because it has an unobservable requirement, as mentioned by Mousetail. Jan 2 at 20:05

from functools import reduce