XP is just a number PerlMonks

### Re^3: [OT] The statistics of hashing.(SOLVED)

by BrowserUk (Pope)
 on Apr 02, 2012 at 23:59 UTC ( #963153=note: print w/replies, xml ) Need Help??

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

Thank you roboticus.

I ran your algorithm against the results of my 60-hour run, and the correlation is simply stunning!

```#! perl -slw
use strict;

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;
}

my \$exp10_0 = ex_10( 2**32, 0 );

open I, '<', 'L25B32V10I32S1.posns' or die \$!;

while( <I> ) {
my( \$inserts, \$collisions ) = split;
my \$exp3 = ex_10( 2**32, \$inserts ) - \$exp10_0;
printf "Insert  %10d: Predicted  %6d Actual: %6d Delta: %+.3f%%\n"
+,
\$inserts, \$exp3, \$collisions, ( \$collisions - \$exp3 ) / \$exp3
+* 100;
}

__END__
C:\test>rbtcs-form-verify
Insert   779967210: Predicted       1 Actual:      1 Delta: -18.051%
Insert   782382025: Predicted       1 Actual:      2 Delta: +58.813%
Insert   830840395: Predicted       2 Actual:      3 Delta: +29.292%
Insert   882115420: Predicted       4 Actual:      4 Delta: -5.961%
Insert   883031614: Predicted       4 Actual:      5 Delta: +16.325%
Insert   897571477: Predicted       5 Actual:      6 Delta: +18.390%
Insert   923155269: Predicted       6 Actual:      7 Delta: +4.086%
Insert   948108745: Predicted       8 Actual:      8 Delta: -8.996%
Insert   954455113: Predicted       9 Actual:      9 Delta: -4.244%
Insert   967783959: Predicted      10 Actual:     10 Delta: -7.404%
Insert   988381482: Predicted      13 Actual:     11 Delta: -17.487%
Insert   992691311: Predicted      13 Actual:     12 Delta: -13.814%
Insert   995935158: Predicted      14 Actual:     13 Delta: -9.624%
Insert  1011301141: Predicted      16 Actual:     14 Delta: -16.457%
Insert  1013742872: Predicted      17 Actual:     15 Delta: -12.616%
Insert  1022258193: Predicted      18 Actual:     16 Delta: -14.242%
Insert  1031874023: Predicted      20 Actual:     17 Delta: -16.989%
Insert  1034026887: Predicted      20 Actual:     18 Delta: -13.909%
Insert  1036254774: Predicted      21 Actual:     19 Delta: -11.051%
Insert  1037064360: Predicted      21 Actual:     20 Delta: -7.093%
Insert  1037193945: Predicted      21 Actual:     21 Delta: -2.569%
Insert  1037309710: Predicted      21 Actual:     22 Delta: +1.957%
...( ~ 52000 ellided }
Insert  2375752842: Predicted   52209 Actual:  52277 Delta: +0.130%
Insert  2375755671: Predicted   52209 Actual:  52278 Delta: +0.131%
Insert  2375756509: Predicted   52209 Actual:  52279 Delta: +0.133%
Insert  2375760656: Predicted   52210 Actual:  52280 Delta: +0.133%
Insert  2375763928: Predicted   52211 Actual:  52281 Delta: +0.134%
Insert  2375785238: Predicted   52215 Actual:  52282 Delta: +0.128%
Insert  2375788721: Predicted   52215 Actual:  52283 Delta: +0.128%
Insert  2375789878: Predicted   52216 Actual:  52284 Delta: +0.130%
Insert  2375790896: Predicted   52216 Actual:  52285 Delta: +0.131%
Insert  2375798283: Predicted   52217 Actual:  52286 Delta: +0.131%

And that still includes the possibility -- though I believe it to be remote -- that there are 1 or more actual dups in there.

My only regret now is that I wish I'd allowed the run to go to the 3/4 point instead of stopping it half way. The number of false positive would still have been easily manageable for the second pass:

```C:\test>rbtcs-bloom-probb 32 10 30e8
N=4294967296, V=10, X=30e8 integral(30e8)=12580199467.653, integral(0)
+=12579822861.8159
Expected collisions: 376605.837186813

That is an order of magnitude less that my own crude attempt was predicting, hence why I stopped the run.

The only way I can repay you is to assure you that I will do my very best to try and understand the formula -- which I do not currently.

And of course, give you credit, when they world comes knocking at my door for my eminently patentable -- at least if you take Apple as your guide -- algorithm :)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?

Replies are listed 'Best First'.
Re^4: [OT] The statistics of hashing. (dissection)
by tye (Sage) on Apr 03, 2012 at 04:47 UTC
I will do my very best to try and understand the formula

Perhaps this will help some.

Below is some fairly simple code that does the precise calculations of the odds for a collision in a single hash (and compares those calculations with the formula roboticus proposed). I came up with a simpler implementation than I expected to. I didn't even try to implement this at first (only a little because I expected it to be more cumbersome, but) mostly because I knew it would be impractical for computing odds for such a large number of insertions. It consumes O(\$inserts) for memory and O(\$inserts**2) for CPU.

```\$|= 1;
my( \$b )= ( @ARGV, 2**32 ); # Total number of bits in the hash.
my \$i= 1;                   # Number of insertions done so far.
my @odds = 1;               # \$odds[\$s] == Odds of their being \$s+1 bi
+ts set
while( 1 ) {                # Just hit Ctrl-C when you've seen enough
my \$exp= \$b*( 1 - exp(-\$i/\$b) );
my \$avg = 0;
\$avg += \$_ for map \$odds[\$_]*(\$_+1), 0..\$#odds;
my \$err = sprintf "%.6f%%", 100*(\$exp-\$avg)/\$avg;
print "\$i inserts, \$err: avg=\$avg exp=\$exp bits set\n"
if  \$i =~ /^\d0*\$/;
# Update @odds to in preparation for the next value of \$i:
for my \$s (  reverse 0..\$#odds  ) {
\$odds[\$s+1] += \$odds[\$s]*(\$b-\$s-1)/\$b;
\$odds[\$s] *= (\$s+1)/\$b;
}
\$i++;
}

\$i tracks the number of insertions done so far. \$odds[\$s] represents the odds of there being \$s+1 bits set in the hash (after \$i insertions). \$avg is an average of these values of \$s (1..@odds) weighted by the odds. But, more importantly, it is also the odds of getting a single-hash collision when inserting (after \$i insertions) except multiplied by \$bits (\$b). I multiple it and 1-exp(-\$i/\$b) by \$b to normalize to the expected number of set bits instead of the odds of a collision because humans have a much easier time identifying a number that is "close to 14" than a number that is "close to 14/2**32".

\$odds[-1] turns out to exactly match (successively) the values from birthday problem. For low numbers of \$inserts, this swamps the calculation of \$avg (the other terms just don't add up to a significant addition), which is part of why I was computing it for some values in my first reply. (Since you asked about that privately.)

I have yet to refresh my memory of the exact power series expansion of exp(\$x), so what follows is actually half guesses, but I'm pretty confident of them based on vague memory and observed behavior.

For large \$bits, 1-exp(-\$inserts/\$bits) ends up being close to 1/\$bits because 1-exp(-\$inserts/\$bits) expands (well, "can be expanded") to a power series where 1/\$bits is the first term and the next term depends on 1/\$bits**2 which is so much smaller that it doesn't matter much (and nor do any of the subsequent terms, even when added together).

On the other hand, for large values of \$inserts, 1-exp(-\$inserts/\$bits) is close to \$avg because the formula for \$avg matches the first \$inserts terms of the power series expansion.

I hope the simple code makes it easy for you to see how these calculations match the odds I described above. But don't hesitate to ask questions if the correspondence doesn't seem clear to you. Running the code shows how my calculations match roboticus' formula. Looking up (one of) the power series expansions for computing exp(\$x) should match the values being computed for @odds, though there might be some manipulation required to make the match apparent (based on previous times I've done such work decades ago).

- tye

Perhaps this will help some.

I seriously hope this will not offend you, but suspect it will.

Simply put, your post does not help me at all.

I am a programmer, not a mathematician, but given a formula, in a form I can understand(*), I am perfectly capable of implementing that formula in code. And perfectly capable of coding a few loops and print statements in order to investigate its properties.

What I have a problem with -- as evidently you do too -- is deriving those formula.

Like you (according to your own words above; there is nothing accusatory here), my knowledge of calculus is confined to the coursework I did at college some {mumble mumble} decades ago. Whilst I retain an understanding of the principles of integeration; and recall some of its uses, the details are shrouded in a cloud of disuse.

Use it or lose it, is a very current, and very applicable aphorism.

The direction my career has taken me means that I've had no more than a couple of occasions when calculus would have been useful. And on both those occasions, I succeeded in finding "a man that can", who could provide me with an understandable formula, and thus, I achieved my goal without having to relive the history of mathematics.

(*) A big part of the problem is that mathematicians not only have a nomenclature -- which is necessary -- the also have 'historical conventions' -- which are not; and the latter are the absolute bane of the lay-person's life in trying to understand the mathematician's output.

There you are, happily following along when reach a text that goes something like this:

We may think intuatively of the Riemann sum: Ʃba f(x) dx

as the infinite sum: f(x0)dx + f(x1)dx + ... + f(xH - 1)dx + f(xH)(b - xH)

Where did H come from? Where did a disappear to? Is H (by convention) == to b - a?

For the answer to this and other questions, tune in next week ..... to the last 400 (or sometimes 4000) years of the history of math

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?

What I have a problem with -- as evidently you do too -- is deriving those formula.

Well, I'm sorry you didn't understand because I wasn't trying to help you convert between programs and formulae (hence why I left that step to you). I was explaining how to derive the most interesting part of the formula at hand (well, verify the derivation in order to understand it, since the formula was already provided).

I was not trying to teach you how to do integration nor how integration correlates to this sampling problem. I have no interest in trying to teach beginning calculus via a web forum.

But it seems your expressed desire "to understand" does not extend to trying to understand 1-exp(1-\$inserts/\$slots). Perhaps my explanation will assist others on that point.

But my explanation also serves as response to more than one private request you made to me, despite your apparent lack of interest now.

I seriously hope this will not offend you, but suspect it will.

I'm not sure why.

- tye

A reply falls below the community's threshold of quality. You may see it by logging in.

Create A New User
Node Status?
node history
Node Type: note [id://963153]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
As of 2020-12-03 06:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How often do you use taint mode?

Results (51 votes). Check out past polls.

Notices?