Good catch! As originally coded, the error rate across all M/N combinations (< 2**32), seems to come out at ~ 1 in 15 (6.66%).
#! perl -slw
use strict;
use List::Util qw[ min ];
use Math::Random::MT qw[ rand ];
$|++;
sub check {
my( $m, $n ) = @_;
my $step = ( $m +1 ) / $n;
my $f = int( $n * $step ) -1;
return if $f != $m;
return 1;
}
my $trials = 0;
my $fails = 0;
for ( 1 .. 1e6 ) {
my $m = int( rand 2**32 );
for ( 1 .. min( $m, 1000 ) ) {
++$trials;
my $n = 1+int( rand $m );
check( $m, $n ) or ++$fails;
}
printf "\r$_ : %f%%", $fails *100 / $trials;
}
__END__
C:\test>ranges
76977645 : 6.620262%
However, a simple fudge floating point rounding correction factor of 0.000001 seems to sort things out nicely:
#! perl -slw
use strict;
use List::Util qw[ min ];
use Math::Random::MT qw[ rand ];
$|++;
sub check {
my( $m, $n ) = @_;
my $step = ( $m +1.000001 ) / $n;
my $f = int( $n * $step ) -1;
# warn( "m:$m n:$n f:$f\n" )
return if $f != $m;
return 1;
}
my $trials = 0;
my $fails = 0;
for ( 1 .. 1e6 ) {
my $m = int( rand 2**32 );
for ( 1 .. min( $m, 1000 ) ) {
++$trials;
my $n = 1+int( rand $m );
check( $m, $n ) or ++$fails;
}
printf "\r$_ : %f%%", $fails *100 / $trials;
}
__END__
C:\test>ranges
6783635 : 0.000000%
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.
-
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.