http://qs321.pair.com?node_id=892956


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.