t...@gmplib.org (Torbjörn Granlund) writes: > Now what?
1. Update mpn_gcd.c and other callers of gcd_11 to call the new functions (like in the patch I posted few days ago). Watch out for performance regressions. 2. Consider alternative entry points. Allowing one even operand would simplify mpn_gcd, at least. Entrypoints with initial reduction (like current mpn_gcd_1, but with a more carefully tuned threshold). 3. Fix the doc(?) bug in mpn_gcd, regarding even inputs. > Should we have gcd_33, gcd_44, and gcd_55 also? I think it would be more beneficial to optimize hgcd2. I think one could have a loop use table lookup on the most significant bits, to get an approximate quotient. Not sure if it's reasonable to do a count_leading_zeros per iteration, or if one should have some other book-keeping if (approximate) leading bits, or maintain normalization within the loop. E.g., 3-limb gcd should typically boil down to one hgcd2, a couple of 3:1 mul_1/addmul_1, and one call to gcd_22. It's not obvious that a gcd_33 using the binary algorithm will be faster. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel