mpz_addmul_ui with ui = 1

Marc Glisse marc.glisse at normalesup.org
Thu Jan 29 22:09:41 CET 2009


On Thu, 29 Jan 2009, Paul Zimmermann wrote:

>> 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?

I had the same reaction, but it is not absurd. The difference between a 
check for 0 inline or in a function is already about a factor 4. And then 
you still get an extra factor because mpz_mul does a couple things before 
the actual check for 0. However, I have a very hard time imagining an 
application where you multiply by a mpz_t representing 0 often enough for 
this to be noticable.

> For an unsigned int argument (the 3rd argument 'a' above in mpz_addmul_ui)
> there is no special treatement for 0 (or 1) if I remember correctly, so it is
> indeed the responsibility of the user to check that case.

It does test for 0, unless I misread the code. I don't think it tests for 
1 though. It could make sense to add compile time tests 
(__builtin_constant_p), especially for C++, but they would not help here 
and obviously adding runtime checks makes the code slower in the general 
case, and then you never know where to stop (detect 1? detect powers of 
2?).

(Not directly related)
At some point I was wondering whether the special representation of 0 
(size==0) should be extended to represent instead small numbers that can 
fit in an integer at most as long as _mp_d. Hard to tell.

-- 
Marc Glisse


More information about the gmp-discuss mailing list