[Q]:Generate Unique ID's

achrist at easystreet.com achrist at easystreet.com
Sat May 24 17:19:07 EDT 2003


andrew cooke wrote:
> 
> My calculations don't agree (have I made a mistake?)
> 
> As far I can see you'll get "birthday" collisions at around sqrt(n)
> number of ids, where n is the maximum ID value (maybe I'm wrong
> here?).  

I cheated: If you partition the keys into 'small' subsets of a trillion
or so, and only worry about the chance of collisions within a subset,
the probability of a key collision just about vanishes.

Sqrt(2^128) = 2^64.  

A trillion is only about 2 ^ 40.  Because of the sqrt, you only get
about one collision in 2^(2*(64 - 40)) databases.  The age of the
universe in seconds is within a few orders of magnitude of 2^48.
You could get it to come out even by fudging the trillion up or
down just a little.  I was off a little, I guess, and that makes it a
much more interesting question:  Is one key collision every 100 
million years "close enough" to "never" for "practical purposes"?

If it isn't, I'll just have to order some more bits.

Al




More information about the Python-list mailing list