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
_______________________________________________
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
