超大空间碰撞概率所需的物品数量

Question

（这不是一个家庭作业问题，如果有班级提供这个问题作为家庭作业，请告诉我，因为我愿意接受它。）

这与birthday problem有关。

我正在寻找一种实用的算法来计算超过大空间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，等等）。

我正在寻找一种算法，可以在合理的时间内以合理的精度计算出合理的时间。维基百科页面提供了数学近似值，但我承认数学有点生疏，我不想花很多时间研究一个近似值，只是发现我不能将它推广并快速实现。

Answer 1

解广义生日问题或概率p = 0.5：

正如Wikipedia指出没有证明式即快速计算，但有一个公式是推测要准确。该公式涉及计算平方根，自然对数，以及基本的算术：

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饲料和找出推测确切的答案。

这里有一个快速的尝试，在实现它，限于蟒蛇花车的准确性：

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) 

您将需要修复它得到一个准确的精度整数结果。 The decimal library可能是解决这个问题所需要的。