XP is just a number PerlMonks

### Comment on

 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":

• 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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (11)
As of 2018-06-25 16:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (127 votes). Check out past polls.

Notices?