几乎平均拆分浮点数,没有损失



假设浮点数(例如:货币(的十进制视觉表示后有 2 位数字,以最小的总误差拆分金额的最佳方法是什么?

例如,要将 100.00 平均分配给 3 个银行账户,我会做这样的事情:

double amount = 100.0;
double acc1 = amount / 3.0;
double acc2 = amount / 3.0;
double acc3 = amount / 3.0;

但是,当打印每个小数点后 2 位的帐户余额时,我得到:

printf("%.2fn", acc1);
printf("%.2fn", acc2);
printf("%.2fn", acc3);
33.33
33.33
33.33
很明显,将

账户的所有金额相加得到 99.99,由于四舍五入而损失了 0.01。

理想情况下,我想要一些可以几乎平均分布和视觉打印的功能/算法

33.34
33.33
33.33

三个帐户中的哪一个获得额外的 0.01 并不重要。

我该怎么做?是否有任何舍入算法名称?

您在这里犯了多个错误。 double是一个双精度二进制浮点数。 100.0 / 3.0等于33.33333333333333570180911920033395290374755859375;给每个人100.0/3.0的问题不在于你给每个人的蛋糕略少于全部,而是你试图给每个人比你拥有的更多的蛋糕。 然后,将其四舍五入到小数点后两位,这是您无法合理期望保留总和的操作。

我建议在您的应用程序中使用整数美分而不是浮点数美元。

话虽如此,要将大小C的蛋糕分成浮点部分以分配给n人,您可以给n-1人一块大小C/n,给最后一个人一块大小fma(-C/n, n-1, C)。 融合的乘法加法在这里是必要的,因为(C/n)*(n-1)乘法可能会产生舍入误差。 也可以使用 fmodremainder .

使用浮点数来表示货币只是自找麻烦;整数更适合此目的。

对于此问题,您需要首先使用下限除法(向下舍入到最接近的美分(将原始总和x分配给n人:

int q = x / n;

(在这里,我假设整数算术与美分。 在 x = 10000n = 3 的情况下,您计算商q = 10000 / 3 = 3333并将其提供给每个人:

33.33
33.33
33.33

然后,计算余数:

int r = x % n;

并将剩余的r美分分配给r人(每人给他们一个(。 由于r总是少于人数,因此您需要决定谁将成为幸运的赢家。

在示例中,r = 10000 % 3 = 1 ,所以我们有一分钱只能给一个人:

33.34 = 33.33 + 0.01
33.33
33.33

您也可以使用显式公式直接计算此值。 第 i 个人收到的美分数由下式给出:

y[i] = q + (i < r);

哪里0 ≤ i < n.

由于加法在浮点运算中甚至不是关联的,因此您的问题没有很好地定义......
(好吧,它可能定义得很好,请参阅更新 2,但一些天真的期望可能会让人感到惊讶(

如果你有 (x+y( + z == 总和,则没有太多保证 x + (y+z( == 总和

例如,假设您要将 0.31 拆分为 3 个 IEEE 754 双精度、0.10、0.10 和 0.11
这是计算回来的总和(最短的小数部分,将四舍五入到与总和相同的浮点数(

0.10+0.10+0.11 == 0.31
0.11+0.10+0.10 == 0.31000000000000005

这两个数字非常接近,但不相同,没有人真正等于 31/100 但好吧......
在第二种形式中,您可以进行轻微更正:

0.10999999999999999 + 0.10 + 0.10 == 0.31

这意味着根据您用于求和的顺序,结果会有所不同......
那么你对浮点有什么期望呢?

当然,如果你确定舍入误差永远不会危险地累积,你可以忽略这些微小的差异,继续使用浮点数来做必要的商/余数运算;可以使用浮点数,但你应该质疑每一个天真的期望,这可能会变得棘手。我的建议是简单地使用其他人建议的整数算术。

更新

在阅读链接四舍五入浮点数以便它们从 PascalCuoq 精确地加起来为 1 后,我意识到 0.10999999999999999 在任何情况下都是比 0.11 更好的解决方案,因为它是 0.31-(0.31-0.11(,并且因为 0.31-(0.31-0.1(==0.1。谢谢帕斯卡库克!

更新 2

非结合性是必不可少的,因为它意味着两种不同的朴素实现将导致不同的结果。

然而,正如tmyklebu所强调的,确切的总和是有明确定义的,尽管在C/C++中不容易获得。

在上面的例子中,最接近的双精度数的精确和为 10/100、10/100、11/

100 略高于最接近的双精度数到 31/100,因此我们必须将其中一个操作数向下调整一个 ulp。这就是浮点用法比关联性的单一属性更有争议的原因。

如果我们尝试将双精度 amount=0.30 公平地分布在 3 个双精度中,则可以说明这一点:因为最接近 30/100 的双精度正好是 5404319552844595/18014398509481984,并且由于分子不能被 3 整除(余数为 1(,因此它不能分成 3 个相等的双精度。5404319552844595/3 的商除以 18014398509481984 将得到 0.1 的前身,我们必须通过增加 ulp 来调整一个操作数。以下朴素总和与确切总和匹配:

0.09999999999999999+0.09999999999999999+0.1 == 0.3 

这是众所周知的(至少在 SO 上(的另一种形式 0.1+0.1+0.1 != 0.3

最新更新