Revisiting gcd and gcdext for small operands

paul zimmermann Paul.Zimmermann at inria.fr
Fri Dec 1 15:07:20 UTC 2017


> > Without detail knowledge of the current implementation, these numbers
> > suggest to me that we could speed small operand gcd and gcdext.  But I
> > might be wrong.

not clear to me. For one word basically you can perform a multiply in a few
cycles, whereas for a gcd you may need up to mp_bits_per_limb operations.

If you find an algorithm that computes a gcd of two words in a few cycles,
it would be a major improvement!

Paul


More information about the gmp-devel mailing list