in reply to Re^2: Split range 0 to M into N non-overlapping (roughly equal) ranges.
in thread Split range 0 to M into N non-overlapping (roughly equal) ranges.
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.
In Section
Seekers of Perl Wisdom