Ciao, Il 2019-10-04 14:31 ni...@lysator.liu.se ha scritto:
Depends on the details... Say we start with r in canonical
Additive redc: r' = (r^2 + q m) / B < m^2 / B + m
Subtractive redc: r' = (r^2 - qm) / B, -m < r' < m^2 / B This can obviously underflow, and if we check for that and add back m, we get canonical representation, 0 <= r' < m. A subtle advantage of subtractive redc is that in the double-limb subtraction r^2 - qm, the low limb always cancel, with no borrow, so we only need to subtract the high libms.
Thanks for the details! I tried the subrtactive redc for MPN_REDC_0 in mpn/generic/powm.c, and the resulting code seems cleaner and a little bit faster.
We are arguing again about the time spent in Miller-Rabin for nextprime... and we just released... so now we can experiment brand new code... That's why I pushed an implementation to specialise mpn_powm for the case base==2.
https://gmplib.org/repo/gmp/rev/63e53ddfd210 Comments are welcome. Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
