检查分数之和是否大于或等于1,而不计算总和。

huangapple go评论161阅读模式
英文:

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

问题

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

使用 boost::multiprecision::cpp_rational 表示分数。

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).

在某个时刻,我需要确定可能大量分数的总和是否达到了1。我不关心总和的确切值,甚至不关心它是否恰好是1或更大。这些单独的分数都在0和1之间(都是不包括的)。

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.

有一些领域特定的考虑:

  • 获得具有相同分母的大量分数是常见情况,而不是罕见事件。
  • 总和恰好为1的情况是常见情况。
  • 总和大幅超过1(超过2)的情况可能如此罕见以至于基本上不会发生。

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.

作为第一步,我已经在一个std::map中计算了部分总和,该std::map按分母“排序”并首先添加相同分母的分数。

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).

但在那之后,我只是将它们相加,并在每次相加后检查结果是否已经大于或等于1,如果是的话就提前退出(因为这些分数都是正数)。

英文:

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).

答案1

得分: 1

Sure, here's the translated text:

我的想法是通过计算上限和下限S_U和S_L来测试分数之和S是否超过1。您选择一个大的分母D,然后对于每个分数n_i/d_i,找到s_i,使得

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

并计算

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

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

如果S_L和S_U都小于1,则S < 1。
如果S_L和S_U都大于1,则S > 1。
否则,测试结果不确定,您必须以传统方式进行计算,将所有分数相加,然后可以尝试使用更大的D,或者使用“概率和为1测试”(见下文)来“证明”它确实等于1。

通过这种测试,您必须遍历所有分数,但不会产生大量中间结果,所以希望它会更快,前提是结果是确定的。浮点数运算应被视为近似,因此要么不使用,要么在对舍入条件特别注意的情况下使用。

您可以使用模算术构建一个“概率和为1测试”。随机选择一个素数P,使得P不是任何d_i的因数。然后可以计算S mod P,对分数进行模P求和。如果选择的P足够随机,那么可以假设S != 1且S = 1 mod P的概率为1/P。此外,如果P_1和P_2是这样的素数,那么S != 1但S = 1 mod P_1和S = 1 mod P_2的概率为1/(P_1P_2)。这样,可以轻松获得S != 1的概率非常小,当所有j个素数P_j都满足S = 1 mod P_j时。

英文:

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 &lt;= n_i/d_i &lt;= (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.

huangapple
  • 本文由 发表于 2023年8月11日 02:19:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/76878375.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定