efficiency bug in mpz_powm_ui?

[Marco Bodrato]

Ciao,

Il 2020-02-29 11:54 paul zimmermann ha scritto:
> 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
Even if there is not jet any special code for the special case "BASE^EXP 
has about the same size as MOD".

Ĝis,
m