efficiency bug in mpz_powm_ui?

[paul zimmermann]

       Dear Marco,

> > 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 
> asymptotically.
> 
> >   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:
> https://gmplib.org/repo/gmp/rev/63e53ddfd210

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).

Best regards,
Paul

PS: while trying the above change, I noticed the daily snapshots are broken
since January 18...