Subject: Re: RelCache (aka ELF prebinding) news
To: Thor Lancelot Simon <tls@rek.tjls.com>
From: Dave Huang <khym@azeotrope.org>
List: tech-userlevel
Date: 12/03/2002 02:55:34
On Tue, Dec 03, 2002 at 02:27:02AM -0500, Thor Lancelot Simon wrote:
> I'm curious how you decided that the likelihood of a random collision was
> too great with a 32-bit sum. I started to make some rather simplistic
> mathematical arguments here but after investigating the literature on
> CRC error rates for about an hour, all I'm really sure of is that my
> calculations were wrong.
FWIW, assuming I did the math right, according to the birthday paradox,
there's a 50% probability of a collision in a pool of about 77162
random 32-bit numbers. I.e., if you assigned a random 32-bit number to
77162 files, there'd be a 50% chance that two files have the same
number. For a 64-bit random number, the 50% chance of a collision
occurs at around 5,056,937,540 numbers.
CRCs aren't uniformly distributed though, so this might not mean much :)
--
Name: Dave Huang | Mammal, mammal / their names are called /
INet: khym@azeotrope.org | they raise a paw / the bat, the cat /
FurryMUCK: Dahan | dolphin and dog / koala bear and hog -- TMBG
Dahan: Hani G Y+C 27 Y++ L+++ W- C++ T++ A+ E+ S++ V++ F- Q+++ P+ B+ PA+ PL++