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

Question

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

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

这是一种最坏的情况：在每个操作（乘法或除法）上，显式地将结果乘以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 2

作为commented by Eric Postpischil，这是“interval arithmetic和相关概念”

谷歌搜索python interval arithmetic发现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])

让我们将其与integer calculation的边界进行比较：

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

因此interval解的精度较低（它是一个较大的区间，只有下界和上界的前十位匹配），但它是正确的（实际值确实在区间内）。从这个意义上说，我想它永远是正确的，尽管我没有研究它是如何工作的

Answer 3

获得范围的一种方法是使用整数，通过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（the float）实际上超出了实际范围，有点太小了。但它的前12位数字是正确的，所以看起来很不错

通过比较lower和upper，我们还得到了更多匹配的数字，从而得到了正确的数字：2.739014747614072227115028053996911215831436E-51。有了更大的比例因子，我们可以得到更多