How fast can we multiply?

[Tim Peters]

[Les Schaffer]
> i dont see the connection between floating point matrix multiplies and
> the integer arithmetic tim sketched out in the previous post.

Knuth Volume 2 is a good reference, for this and all other vital questions
in life <wink>.

Turns out it's possible to multiply two 2x2 matrices using 7 multiplies.
Since matmult can be "blocked", a larger matrix can be treated as a 2x2
array of smaller submatrices, and the same trick recursively applied.  In
the end you get a method with runtime O(n**log2(7)) ~= O(n**2.81) instead of
O(n**3).

The intmult trick is less work to code, and yields a bigger payoff earlier.

much-like-python-itself-ly y'rs  - tim