optimal order for long product

[Décio Luiz Gazzoni Filho]

On Mar 9, 2009, at 8:14 AM, Torbjorn Granlund wrote:

> <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)).

Besides, you can do it mostly in-place -- results from the previous  
level of the tree can be discarded as they're used.

Décio