Re^2: [OT] The statistics of hashing.

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

Hm. Attempting calculate 1 - 1/2**128 using my calculator just returns 1.

So then I tried Math::BigFloat, and still got just 1. What Am I doing wrong?

use Math::BigFloat;

$moritzFactor = Math::BigFloat->new( 1 )->bsub(
    Math::BigFloat->new( 1 )->bdiv(
        Math::BigFloat->new( 2 )->bpow( 128 )
    )
);

print $moritzFactor;
;;
1

[0] Perl> print $moritzFactor->bstr;;
1

[0] Perl> print $moritzFactor->bsstr;;
1e+0
[download]

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?

Comment on Re^2: [OT] The statistics of hashing. Select or Download Code

Replies are listed 'Best First'.
Re^3: [OT] The statistics of hashing. by moritz (Cardinal) on Apr 01, 2012 at 15:31 UTC
You'd need a floating-point number with a mantissa of about 128 bits to hold the value of (1-1/2128) Luckily there are other ways to evaluate the expression. If we set `x = 1/2128`, we can do a taylor series to evaluate `(1-x)*n` around x = 0 (and since x is very small, it's a good approximation: `(1 - x)^n = 1 - n x + 1 / 2 * n * (n - 1) * x ** 2 + ...` [download] Where higher orders can be neglected. If you chose an `n` that is high enough, you can get non-1 values as the result. Though I'm not sure if that's really helpful. What you'd really need is the expectation value of the number of collisions (the lambda symbol in Poisson Distribution, then you could easily calculate everything you wanted. Perl 6 - second systems done right	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: [OT] The statistics of hashing.
by moritz (Cardinal) on Apr 01, 2012 at 15:31 UTC

You'd need a floating-point number with a mantissa of about 128 bits to hold the value of (1-1/2**128)

Luckily there are other ways to evaluate the expression. If we set x = 1/2**128, we can do a taylor series to evaluate (1-x)**n around x = 0 (and since x is very small, it's a good approximation:

(1 - x)^n = 1 - n * x + 1 / 2 * n * (n - 1) * x ** 2 + ...
[download]

Where higher orders can be neglected. If you chose an n that is high enough, you can get non-1 values as the result.

Though I'm not sure if that's really helpful. What you'd really need is the expectation value of the number of collisions (the lambda symbol in Poisson Distribution, then you could easily calculate everything you wanted.

Perl 6 - second systems done right

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom