note
BrowserUk
<blockquote><i></i></blockquote>
<p>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%).
<code>
#! 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%
</code>
<p>However, a simple <strike>fudge</strike> floating point rounding correction factor of 0.000001 seems to sort things out nicely:<code>
#! 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%
</code>
<div class="pmsig"><div class="pmsig-171588">
<hr />
<font size=1 >
<div>Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.</div>
<div>"Science is about questioning the status quo. Questioning authority". </div>
<div>In the absence of evidence, opinion is indistinguishable from prejudice.</div>
</font>
</div></div>
892828
892900