efficiency bug in mpz_powm_ui?
Paul.Zimmermann at inria.fr
Mon Mar 2 11:01:26 UTC 2020
> > it seems that mpz_powm_ui is highly inefficient when BASE^EXP has about
> > the
> > same size as MOD, in which case it could first compute BASE^EXP
> > exactly, then
> > perform only one reduction:
> You are right, mpz_powm_ui does not implement an algorithm that is
> optimal for every possible use-case. But I'd not consider this a bug :-)
> > mpz_ui_pow_ui (x, 2, e);
> > mpz_mod (r1, x, y);
> I'm not sure that mpz_ui_pow_ui (x, 2, e) is the more efficient way to
> obtain a value x with only the bit e set to 1 :-)
> But of course, in this context, the following _mod dominates
> > mpz_set_ui (x, 2);
> > mpz_powm_ui (r2, x, e, y);
> Thanks to a recent change, this function should be faster now, when base
> is 2:
thank you, this solves the issue I reported.
> Even if there is not jet any special code for the special case "BASE^EXP
> has about the same size as MOD".
indeed, the same issue can happen for other small values of BASE (not only 2).
PS: while trying the above change, I noticed the daily snapshots are broken
since January 18...
More information about the gmp-bugs