正确确定比例因子

Question

一个函数根据给定的 x（整数）和 s（浮点数）确定 y（整数），如下所示：

floor(x * s)

如果知道x和y如何计算s，那么保证floor(x * s)正好等于y.

如果我简单地执行 s = y / x 是否有可能 floor(x * s) 不等于 y 由于 浮点数 操作？

Answer 1

如果我们重新表述您的问题，您想知道等式 y = floor( x * y/x ) 是否适用于 x 和 y 整数，其中 y/x 转换为 python转化为64位浮点数，后续乘法也生成64b浮点数。

Python 的 64b 浮点数遵循 IEEE-754 规范，这给了它们 15-17 bits of decimal precision。为了执行除法和乘法，x 和 y 都被转换为浮点数，这些操作可能会将最小精度降低最多 1 位（真正最坏的情况），但它们肯定不会增加精度。因此，在此操作中您最多只能期望 15-17 位的精度。这意味着 y 值高于 10^15 might/will 存在舍入误差.

更实际的例子可以是（您可以将此代码重复用于其他示例）：

import numpy as np
print("{:f}".format(np.floor(1.3 * (1.1e24 / 1.3))))
#> 1100000000000000008388608.000000

Answer 2

If I simply perform s = y / x is there any chance that floor(x * s) won't be equal to y due to floating point operations?

是的，有可能不相等。提供一个简单的反例：y = 1 和 x = 49。

(为了讨论，让我们限定x,y > 0。)

要找到通常有效的给定 x,y 的比例因子 s，我们需要在数学上反转 y = floor(x * s)。我们需要考虑乘法误差（参见 ULP）和底截断。

 # Pseudo code

 e = ULP(x*s)
 y <  (x*s + 0.5*e) + 1
 y >= (x*s - 0.5*e)

 # Estimate e
 est = ULP((float)y)
 s_lower = ((float)y - 1 - 0.5*est)/(float)x
 s_upper = ((float)y     + 0.5*est)/(float)x

候选人 s 会说谎 s_lower < s <= s_upper。

使用更高精度的例程执行上述操作。那么我建议使用最接近s_lower, s_upper.

中点的float

或者，在 s 的初始尝试可以使用：

s_first_attempt = ((float)y - 0.5)/(float)x

正确确定比例因子

Correctly determining scaling factor

python

floating-point