[PPL-devel] mpz_addmul_ui with ui = 1

Roberto Bagnara bagnara at cs.unipr.it
Mon Feb 2 22:30:03 CET 2009

Paul Zimmermann wrote:
>> From: Roberto Bagnara <bagnara at cs.unipr.it>
>> In the Parma Polyhedra Library, we found out that,
>> for mpz_mul(), checking the source arguments against 0
>> gives rise to significant speedups in some algorithms.
> this surprises me, since 0 has a special representation in mpz, and thus
> is early detected in mpz_add and mpz_mul. Please can you give an example?

Hi Paul,

sorry for the delay: I was busy and I wanted to check my facts again before
replying.  The example is in


There you will find the two following fragments:

	// FIXME(0.10.1): the test seems to speed up the GMP computation.
	if (tableau_ij != 0) {
	  scalar_value = tableau_ij * norm_factor[i];
	  add_mul_assign(challenger_den, scalar_value, scalar_value);


#if 1 // CHECKME: the test seems to speed up the GMP computation.
       const Coefficient& y_i = y[i];
       if (y_i != 0)
	sub_mul_assign(x_i, y_i, normalized_x_k);
       sub_mul_assign(x_i, y[i], normalized_x_k);
#endif // 1

This happens in our implementation of the simplex with unbounded arithmetics.
As an example, if we leave the code as it is, solving the problem boeing1.mps
the CPU time is 7.95 seconds;  if we remove the tests against zero, the CPU
time increases to 11.88 seconds.  Timings have been taken on a machine
equipped with an Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz, running
Fedora 10, gmp-4.2.2-8.fc10.x86_64, GCC 4.3.2.  The code for add_mul_assign()
and sub_mul_assign() is below, where GMP_Integer is an alias for mpz_class:

inline void
add_mul_assign(GMP_Integer& x, const GMP_Integer& y, const GMP_Integer& z) {
   mpz_addmul(x.get_mpz_t(), y.get_mpz_t(), z.get_mpz_t());

inline void
sub_mul_assign(GMP_Integer& x, const GMP_Integer& y, const GMP_Integer& z) {
   mpz_submul(x.get_mpz_t(), y.get_mpz_t(), z.get_mpz_t());

If it can help, I am willing to perform the same test on different platforms,
possibly with different versions of GMP and/or GCC.
All the best,


Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
mailto:bagnara at cs.unipr.it

More information about the gmp-discuss mailing list