(32S, 32SII) Birthday paradox, hash collision probability
|
04-28-2020, 03:23 PM
(This post was last modified: 05-04-2020 12:29 AM by Albert Chan.)
Post: #7
|
|||
|
|||
RE: (32S, 32SII) Birthday paradox, hash collision probability
(04-27-2020 07:54 PM)Albert Chan Wrote: ln_P(n,s) := -s/(12*n*(n-s)) - (s + (n-s+0.5)*ln(1-s/n)) (04-27-2020 10:43 PM)Albert Chan Wrote: ln(P(n,s)) ≈ -s/(12*n*(n-s)) + 2*(n-s+0.5)(y^3/3 + y^5/5 + ...) - (s-1)y This version use the 2nd form, to avoid numerical cancellation problem of original formula. It assumed IEEE double, ln(2^-52) ≈ -36.0, and sum y^n terms in reverse order With all this work, we might as well add more corrections. XCas> series(1/(e^D-1),D) → 1/D -1/2 +D/12 -D^3/720 +D^5/30240 +D^6*order_size(D) Let u=n-x, f(x) = ln(n-x) = ln(u) → df = ln(n-x) dx = -ln(u) du With x limit from 0 to s, we have u = n-x = from n to n-s XCas> diff(-ln(u),u,3) / -720 → 1/(u^3*360) XCas> diff(-ln(u),u,5) / 30240 → -1/(u^5*1260) Code: function ln_nr(n,s) -- log(probability of no repetition) lua> m = require'mathx' lua> function fac(n) return m.tgamma(n+1) end lua> fac(69.95)/fac(69) 56.58432038352886 lua> function perm(n,s) return exp(ln_nr(n,s)) * n^s end lua> perm(69.95, 0.95) 56.58432038352816 lua> 70*perm(69.95,-0.05) -- 69.95!/69! = 70*(69.95!/70!) 56.58432038352817 lua> 70/perm(70,0.05) -- 69.95!/69! = 70/(70!/69.95!) 56.58432038352817 lua> ((69.95+70)/2)^0.95 -- inspired from Approximating Gamma Ratios 56.58427578530249 |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)