optimal order for long product

Paul Zimmermann Paul.Zimmermann at loria.fr
Fri Mar 6 14:38:34 CET 2009

> 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

More information about the gmp-discuss mailing list