Anzahl der Elemente, die notwendig sind, um eine gegebene Kollisionswahrscheinlichkeit für große Räume zu überschreiten

Question

(Dies ist kein Hausaufgabenproblem. Wenn es eine Klasse gibt, die diese Frage als Hausaufgabe anbietet, bitte sagen Sie mir, wie ich es gerne nehmen würde.)

Dies steht im Zusammenhang mit der birthday problem.

Ich bin auf der Suche nach einem praktischen Algorithmus, um die Anzahl der Elemente zu berechnen, die notwendig ist, um eine Kollisionswahrscheinlichkeit von p für große Räume zu überschreiten. Ich brauche das für die Bewertung der Eignung von Hashing-Algorithmen für die Speicherung einer großen Anzahl von Elementen.

Zum Beispiel f(365, .5) sollte 23 zurückkehren, die Anzahl der Menschen benötigt, um 0,5 Wahrscheinlichkeit zu überschreiten, dass jemand den gleichen Geburtstag teilen.

Ich habe eine einfache Implementierung erstellt eine genaue Kollisionswahrscheinlichkeit berechnet:

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

Unnötig zu sagen, ist dies für die großen Räume nicht funktioniert, mit dem ich arbeiten möchte (2^256, 2^512, etc).

Ich bin auf der Suche nach einem Algorithmus, der dies in einer angemessenen Zeit mit angemessener Genauigkeit berechnen kann. Die Wikipedia-Seite bietet mathematische Näherungen, aber zugegebenermaßen ist meine Mathematik ein wenig eingerostet, und ich möchte nicht viel Zeit mit der Untersuchung einer Näherung verbringen, nur um festzustellen, dass ich sie nicht verallgemeinern und schnell implementieren kann.

Answer 1

Lösung zu verallgemeinerten Geburtstag Problem oder Wahrscheinlichkeit p = 0,5:

Da es von Wikipedia bemerkt ist keine Formel erwiesen, die schnell zu berechnen ist, aber es gibt eine Formel, die genau zu sein gemutmaßt ist. Die Formel beinhaltet die Berechnung von Quadratwurzeln, natürliche Logarithmen und Grundrechen:

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) 

so können Sie in Ihrem d füttern = 2^256 und die Antwort herauszufinden, die um genau zu sein gemutmaßt wird.

Hier ist ein kurzer Versuch ihrer Umsetzung, auf die Genauigkeit des Python Schwimmern begrenzt:

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) 

Sie müssen es in Ordnung zu bringen, ein genaues Präzision integer Ergebnis zu erhalten. The decimal library kann sein, was benötigt wird, um dies zu beheben.