超过给定碰撞概率的大空间所需的项目数

Question

（这不是作业问题。如果有一个提供此问题作为家庭作业的课程，请告诉我我很想接受它。）

这与生日问题有关。

我正在寻找一种实用算法，以计算超过大空间P碰撞概率所需的项目数量。我需要它来评估哈希算法存储大量项目的适用性。

例如，f(365, .5)应返回23，任何人共享同一生日所需的人数超过0.5的概率。

我使用精确的碰撞概率计算创建了一个简单的实现：

def _items_for_p(buckets, p):
    """Return the number of items for chance of collision to exceed p."""
    logger.debug('_items_for_p($r, $r)', buckets, p)
    up = buckets
    down = 1
    while up > (down + 1):
        n = (up + down) // 2
        logger.debug('up=%r, down=%r, n=%r', up, down, n)
        if _collision_p(buckets, n) > p:
            logger.debug('Lowering up to %r', n)
            up = n
        else:
            logger.debug('Raising down to %r', n)
            down = n
    return up

def _collision_p(buckets, items):
    """Return the probability of a collision."""
    return 1 - _no_collision_p(buckets, items)

def _no_collision_p(buckets, items):
    """Return the probability of no collision."""
    logger.debug('_no_collision_p(%r, %r)', buckets, items)
    fac = math.factorial
    return fac(buckets) / ((buckets ** items) * fac(buckets - items))

不必说，这对我想使用的大空间不起作用（2^256，2^512等）。

我正在寻找一种算法，该算法可以以合理的精度在合理的时间内计算出来。Wikipedia页面提供了数学近似值，但诚然，我的数学有点生锈，我不想花很多时间来研究一个近似值，只是发现我既不能概括它又快速地实现它。

Answer 1

解决通用生日问题或概率p = 0.5：

的解决方案

如Wikipedia所指出的那样，没有公式可以快速计算的公式，但是有一个公式是 subindured 的准确性。该公式涉及计算方形根，自然对数和基本算术：

Sqrt(2*d*ln 2) + (3 - 2 * ln 2)/6 + (9 - 4(ln 2)^2)/(72 + Sqrt(2*d*ln 2) ) - 2 ln(2)^2/(135* d)

因此，您可以在D = 2^256中进食，并找出确切的答案。

这是一个快速的尝试，仅限于Python Floats的准确性：

def solve_birthday_problem( d ):
    ln2 = math.log(2)
    term1 = (2*d*ln2)**0.5
    term2 = (3 - 2 * ln2)/6.0
    term3 = (9 - 4*(ln2)**2)/(72 + (2*d*ln2)**0.5 )
    term4 = 2*ln2**2/(135.0 * d)
    return math.ceil(term1 + term2 + term3 - term4)

您需要修复它以获得准确的精度整数结果。十进制库可能是修复此问题所需的。