[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
http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/~checkout~/ppl/src/MIP_Problem.cc?rev=1.80;content-type=text%2Fplain;cvsroot=PPL
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);
}
and
#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);
#else
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
(http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/demos/ppl_lpsol/examples/boeing1.mps?cvsroot=PPL)
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,
Roberto
--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it
More information about the gmp-discuss
mailing list