Efficiently detect that rational numbers are equal

Question

I have a collection of many rational numbers, with the numerator and denominator of each stored as a large (hundreds or thousands of bits) unsigned integer. I'd like to be able to efficiently test whether any given rational number a/b in the set is equal to any other rational number c/d in the set.

The most straightforward method would be to test whether a*d == b*c, of course, but I'd like something more efficient than computing the full products.

Some notes on my particular use-case:

• The pairs I'll be testing have a high likelihood of actually being equal (because I'm already precomputing and comparing them by their floating point approximations first), so early-outing if they're unequal won't save me much time.
• I'm fine with precomputing extra data for each of the numbers, but each number will only be used in a handful of comparisons, so expensive precomputation (such as prime factorization) probably wouldn't be worthwhile.
• Occasional false negatives would be fine, but false positives are not.

I think this may be theoretically impossible, but throwing it out to the hive mind just in case.

Answer 1

You can filter out many not equal pairs of fractions by comparing the bit-lengths. Let l(a) = floor(log2(a)) + 1 the bit-length of a. If a/b = c/d than l(a) + l(d) = l(c) + l(b).

You can use this for a speedup when you are first comparing the lengths and comparing the products, only if the sum of the lengths are equal.