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:
- The only testing I did is limited to the cases above. Be sure to run a few more before relying on it.
- I entered the ex_1 and ex_2 routines, but didn't test 'em.
- 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.
-
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.