Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

comment on

( [id://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:

$ ./ana_2.pl 16 4 65536 N=65536, V=4, X=65536 integral(65536)=139415.765849051, integral(0)=13 +6533.333333333 Expected collisions: 2882.43251571807 $ ./ana_2.pl 16 4 16384 N=65536, V=4, X=16384 integral(16384)=136541.854969116, integral(0)=13 +6533.333333333 Expected collisions: 8.52163578287582 $ ./ana_2.pl 14 3 16384 N=16384, V=3, X=16384 integral(16384)=31411.9141476821, integral(0)=30 +037.3333333333 Expected collisions: 1374.58081434877 $ ./ana_2.pl 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 ana_2.pl #!/usr/bin/perl # # ana_2.pl 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; }

Notes:

  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.

...roboticus

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

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



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2024-03-28 19:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found