Checking if a sum of fractions is greater or equal to 1 without calculating the sum

Question

We use boost::multiprecision::cpp_rational to represent fractions.

At some point, I have to determine if a sum of a potentially huge number of fractions reaches 1 or not. I don’t care about the exact value of the sum; not even if it’s exactly 1 or above. The individual fractions are all between 0 and 1 (both exclusive).

Is there some clever math trick that I’m not aware of that spares me from actually having to calculate the sum?

---

There are some domain-specific considerations:

• Getting a lot of fractions with the same denominators is a common case and not a rare happenstance.
• The case where the sum is exactly 1 is a common case.
• The sum exceeding 1 by a large amount (exceeding 2) is probably so rare it essentially never happens.

---

My optimization attempts so far:

As a first step, I already calculate partial sums in a std::map that “sorts” the fractions by denominator and adds same-denominator fractions first.

The partial sums are then sorted by size, largest first.

But after that, I just add them and after each addition, check if the result is already greater or equal than 1 and quit early if they are (that’s because the fractions are all positive).

Answer 1

My idea is to test to see if the sum of the fractions S exceeds 1 by calculating upper and lower bounds, S_U and S_L respectively. You choose a large denominator D, then for each fraction n_i/d_i you find s_i such that

s_i/D <= n_i/d_i <= (s_i + 1)/D

and calculate

S_L = sum{i=1 to n} s_i/D

and

S_U = sum{i=1 to n} (s_i + 1)/D

If both S_L and S_U are less than 1, then S < 1. If both S_L and S_U are greater than 1, then S > 1. Otherwise, the test is inconclusive and you have to do it the long way, adding up all the fractions, try again with a larger D, or use a 'Probabilistic Sum To Unity Test' (see below) to 'prove' that it sums to exactly 1.

With this test, you have to go through all the fractions, but you don't have massive intermediate results, so hopefully it will be faster, assuming it is conclusive. Floating point arithmetic should be assumed to be approximate so should either not be used or used paying great attention to the rounding criteria.

You could construct a 'Probabilistic Sum To Unity Test' using modular arithmetic. Take a prime number P at random such that P does not divide any of the d_i. Then you can calculate S mod P, summing the fractions mod P. If the choice of P is random enough, then you can assume that the probability that S != 1 and S = 1 mod P is 1/P. Moreover, if P_1 and P_2 are such primes, then the probability that S != 1 but S = 1 mod P_1 and S = 1 mod P_2 is 1/(P_1P_2). This way, it should be easy to obtain a vanishingly small probability that S != 1 when S = 1 mod P_j for all j primes.