[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230418172936.GA2732@openwall.com>
Date: Tue, 18 Apr 2023 19:29:37 +0200
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox
On Tue, Apr 18, 2023 at 07:12:09PM +0200, magnum wrote:
> $ bc -l <<< '4096*(1-(4095/4096)^1024)'
> 906.12935699914074324992
I was using this same formula for these things.
> Background: I was amazed how an 4-level bitmap that "should" give 1/16
> false positives, could end up as good as 1/43. That was with 512 hashes
> in a 4x1024 bitmap. Using this formula we end up with 1/41, so mystery
> solved.
>
> In another test case, 1024 hashes in a 8x1024 bitmap would be "full" and
> should give 1/1 false positives if we don't factor in the birthday
> paradox. But empirical tests showed an amazing 1/38 - actually good
> enough to make an nvidia perform near its best! This was again
> explained with the birthday paradox (which says 1/39).
Now you need to compare efficiency of these multiple bitmaps against one
Bloom filter of their cumulative size. And then against a Cuckoo filter
of the same size.
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
