Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

OK, I think I'm done with this diversion. I've built a program that will compute the expected number of collisions with no looping. Example output:

$ ./ 16 4 65536 N=65536, V=4, X=65536 integral(65536)=139415.765849051, integral(0)=13 +6533.333333333 Expected collisions: 2882.43251571807 $ ./ 16 4 16384 N=65536, V=4, X=16384 integral(16384)=136541.854969116, integral(0)=13 +6533.333333333 Expected collisions: 8.52163578287582 $ ./ 14 3 16384 N=16384, V=3, X=16384 integral(16384)=31411.9141476821, integral(0)=30 +037.3333333333 Expected collisions: 1374.58081434877 $ ./ 16 10 32768 N=65536, V=10, X=32768 integral(32768)=191953.190301726, integral(0)=1 +91952.863492063 Expected collisions: 0.326809662627056

The code is straightforward:

$ cat #!/usr/bin/perl # # N V X # # N=vector size (bits), V=number of vectors, X=sample number # use strict; use warnings; use feature ':5.10'; my $n=shift; $n = 1<<$n; my $v=shift; my $x=shift; my ($exp1, $exp2, $exp3); given ($v) { when ( 1) { $exp1=ex_1($n, $x), $exp2=ex_1($n, 0) } when ( 2) { $exp1=ex_2($n, $x), $exp2=ex_2($n, 0) } when ( 3) { $exp1=ex_3($n, $x), $exp2=ex_3($n, 0) } when ( 4) { $exp1=ex_4($n, $x), $exp2=ex_4($n, 0) } when (10) { $exp1=ex_10($n, $x), $exp2=ex_10($n, 0) } default { die "Need symbolic integral form for $v vectors!\n"; } } $exp3 = $exp1-$exp2; print "N=$n, V=$v, X=$x integral($x)=$exp1, integral(0)=$exp2\n"; print "Expected collisions: $exp3\n"; sub ex_1 { my ($N, $X) = @_; return $N *exp( -$X/$N) + $X; } sub ex_2 { my ($N, $X) = @_; return -$N/2*exp(-2*$X/$N) + 2*$N *exp( -$X/$N) + $X; } sub ex_3 { my ($N, $X) = @_; return $N/3*exp(-3*$X/$N) - 3*$N/2*exp(-2*$X/$N) + 3*$N *exp( -$X/$N) + $X; } sub ex_4 { my ($N, $X) = @_; return -$N/4*exp(-4*$X/$N) + 4*$N/3*exp(-3*$X/$N) - 3*$N *exp(-2*$X/$N) + 4*$N *exp( -$X/$N) + $X; } sub ex_10 { my ($N, $X) = @_; return -$N/10*exp(-10*$X/$N) + 10*$N/9 *exp( -9*$X/$N) - 45*$N/8 *exp( -8*$X/$N) + 120*$N/7 *exp( -7*$X/$N) - 35*$N *exp( -6*$X/$N) + 252*$N/5 *exp( -5*$X/$N) - 105*$N/2 *exp( -4*$X/$N) + 40*$N *exp( -3*$X/$N) - 45*$N/2 *exp( -2*$X/$N) + 10*$N *exp( -1*$X/$N) + $X; }


  1. The only testing I did is limited to the cases above. Be sure to run a few more before relying on it.
  2. I entered the ex_1 and ex_2 routines, but didn't test 'em.
  3. For the other numbers of vectors, just expand (1 - exp(-X/N))^V, and integrate it. The ex_1..n functions are coded straight from the integration.


When your only tool is a hammer, all problems look like your thumb.

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

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others surveying the Monastery: (3)
    As of 2021-01-24 07:08 GMT
    Find Nodes?
      Voting Booth?