speed of mpq_cmp vs mpq_sub

Torbjörn Granlund tg at gmplib.org
Mon May 23 07:55:11 UTC 2016

Marc Glisse <marc.glisse at inria.fr> writes:

  Just checking: I don't think this will help when comparing p/q with
  (2p+1)/2q. Anything that doesn't somehow involve the gcd of the
  denominators will still require the full multiplications and be much
  slower than a subtraction for that case. But that's probably
  inevitable, since computing the gcd would likely be slower in many
Indeed; I no longer think we can make cmp faster than sub for all inputs.

  (I think in the program I posted the denominators are all powers of 2,
  which helps for the gcd computation...)
  Now your proposition may still help in other cases. The initial
  cross-product / interval arithmetic thing sounds like it would handle
  quite a few more cases than the current bitlength tests. In
  particular, the *101 / *103 should become fast :-)

I think a sloppy initial cross product makes a lot of sense regardless
of the present reports.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list