optimal order for long product

[Paul Zimmermann]

> 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