带有准确信息的数字类型？

Question

最近有人想要一个无冲突哈希函数来将一百万个值哈希成一个 32 位哈希值。如果您知道 birthday paradox，您就知道这不太可能是无碰撞的。但是想知道概率，我是这样计算的（从概率 1 开始，然后对于百万个值中的每一个，乘以它是前一个 none 的概率）：

>>> p = 1
>>> for i in range(10**6):
        p *= (2**32 - i) / 2**32

>>> p
2.7390147476139603e-51

但是我在那里乘以一百万个浮点数，所以我担心会失去越来越多的准确性。

是否有一种数字类型与简单的浮点数不同，它不仅能给我一个不准确的数字，还能告诉我它有多不准确？像 [2.73e-51, 2.74e-51] 这样的范围或像 2.7390147476139603e-51 +/- 1e-54?

这样的错误

或者有其他方法可以检查结果的准确性吗？

Answer 1

获得范围的一种方法是使用整数，将概率按比方说 10¹⁰⁰ 缩放。对于下限总是向下舍入，对于上限总是向上舍入：

>>> lower = 10**100
>>> for i in range(10**6):
        lower = lower * (2**32 - i) // 2**32

>>> lower
27390147476140722271150280539996691121583143636646

>>> upper = 10**100
>>> for i in range(10**6):
        upper = -(-upper * (2**32 - i) // 2**32)

>>> upper
27390147476140722271150280539996691121583143640960

对齐它们：

upper  27390147476140722271150280539996691121583143640960
p     2.7390147476139603e-51
lower  27390147476140722271150280539996691121583143636646

我们可以看到p（float）其实是在真实范围之外的，有点太小了。但是它的前十二位数字是正确的，所以看起来不错。

通过比较lower和upper，我们也得到了更多的匹配，因此正确的数字：2.73901474761407222711502805399966911215831436e-51。有了更大的比例因子，我们可以获得更多。

Answer 2

这是最坏的情况：在每个操作（乘法或除法）中，明确地将结果乘以 1+2^-52 或 1-2^-52 并检查（使用 assert）它实际上有所作为。这应该估计不确定性的上限，而且它仍然非常小——它在没有任何断言失败的情况下到达终点，差异是 10^9 的一部分。

import sys

m_upper = (1 + 2**(1 - sys.float_info.mant_dig))
m_lower = (1 - 2**(1 - sys.float_info.mant_dig))

p_upper = p_lower = 1

for i in range(10**6):

    factor = (2**32 - i) / 2**32
    f_upper = factor * m_upper
    f_lower = factor * m_lower

    assert(f_upper > factor)
    assert(f_lower < factor)

    p_upper *= f_upper

    p_upper1 = p_upper * m_upper
    assert(p_upper1 > p_upper)
    p_upper = p_upper1
    
    p_lower *= f_lower

    p_lower1 = p_lower * m_lower
    assert(p_lower1 < p_lower)
    p_lower = p_lower1

print(p_upper, p_lower, p_upper - p_lower)

给予

2.739014748809663e-51 2.7390147464186476e-51 2.3910154124504752e-60

请注意，如果 (1 - sys.float_info.mant_dig) 被 -sys.float_info.mant_dig 替换（即使用 2^-53 而不是 2^-52），则断言开始失败。

Answer 3

As , that's "interval arithmetic 和相关概念。

谷歌搜索python interval arithmetic finds PyInterval。让我们试试看：

from interval import interval

p = interval[1]
for i in range(10**6):
    p *= (2**32 - i) / 2**32
print(p)

输出（运行 on repl.it）：

interval([2.7390147473969355e-51, 2.739014747831127e-51])

让我们将其与的界限进行比较：

interval upper 2.739014747831127e-51
integer upper   27390147476140722271150280539996691121583143640960
integer lower   27390147476140722271150280539996691121583143636646
interval lower 2.7390147473969355e-51

所以interval的解不是很精确（是一个更大的区间，只有上下界的前十位匹配），但它是正确的（真正的值确实在区间内）。我想从这个意义上说它总是正确的，尽管我没有研究它是如何工作的。

Answer 4

（基于）

因子 (2**32 - i) / 2**32 是准确的，也就是说，它们准确地表示为 float。此外，浮点标准保证乘法得到最准确的 float 值。它可能低于或高于实际产品，但它是可能的最接近 float 的值。因此，如果我们故意总是偏离下一个更大的 float 值，那将永远不会小于实际值，即它给了我们一个上限。我们通过偏离下一个 更小的 float 值得到一个 lower 的边界。

Python 3.9引入了math.nextafter，让我们使用它：

>>> import math
>>> lower = upper = 1
>>> for i in range(10**6):
        factor = (2**32 - i) / 2**32
        lower = math.nextafter(lower * factor, -math.inf)
        upper = math.nextafter(upper * factor, math.inf)

>>> lower, upper
(2.739014747179961e-51, 2.739014748048138e-51)
>>> upper - lower
8.681767916298978e-61

带有准确信息的数字类型？

Number type with accuracy information?

python

floating-accuracy