optimal order for long product

[keith.briggs at bt.com]

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


-----Original Message-----
From: Paul Zimmermann on behalf of Paul Zimmermann
Sent: Fri 3/6/2009 1:38 PM
To: Briggs,KM,Keith,CXR2 R
Cc: gmp-discuss at gmplib.org
Subject: Re: optimal order for long product
 
> Date: Fri, 6 Mar 2009 13:27:25 -0000
> From: <keith.briggs at bt.com>
> 
> For the problem of finding the mpz_t product of many (perhaps >10^6) unsigned long ints (using mpz_mul_ui),
> is it known what is the optimal order in which to multiply?  Smallest first, largest first, or some other order?
> 
> Keith

the optimal is a balanced product tree, to benefit from fast multiplication.
See http://cr.yp.to/lineartime/multapps-20041007.pdf, Section 12.

Paul Zimmermann