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