optimal order for long product

[Torbjorn Granlund]

<keith.briggs at bt.com> writes:

  Paul: thanks very much for this reference.  Bernstein is mainly considering a non-commutative product of matrices.   I see that he mentions the integer case on p24, and gives O(n*lg^2(n)*lglg(n)), where n is the total number of input bits.  I don't think he's implying that this is optimal.  On p25 he mentions that Strassen proposes for commuting matrices (which includes the integer case) to always pick the two matrices of smallest degree.
  Also, the product-tree algorithm is recursive and might therefore have a space complexity which is prohibitive in some cases.

The recursive depth is O(log(n)).  

-- 
Torbjörn