Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^3: [OT] The statistics of hashing.

by moritz (Cardinal)
on Apr 01, 2012 at 15:31 UTC ( [id://962888]=note: print w/replies, xml ) Need Help??


in reply to Re^2: [OT] The statistics of hashing.
in thread [OT] The statistics of hashing.

You'd need a floating-point number with a mantissa of about 128 bits to hold the value of (1-1/2**128)

Luckily there are other ways to evaluate the expression. If we set x = 1/2**128, we can do a taylor series to evaluate (1-x)**n around x = 0 (and since x is very small, it's a good approximation:

(1 - x)^n = 1 - n * x + 1 / 2 * n * (n - 1) * x ** 2 + ...

Where higher orders can be neglected. If you chose an n that is high enough, you can get non-1 values as the result.

Though I'm not sure if that's really helpful. What you'd really need is the expectation value of the number of collisions (the lambda symbol in Poisson Distribution, then you could easily calculate everything you wanted.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://962888]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2024-03-28 09:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found