FYI, there are occasional one-off rounding error issues with this algorithm (possibly platform dependent), 2.5% of the time partitioning ranges of 1..100 or less. Depending on your goals that may or may not matter, but here are some examples :
$M,$N final array element (should be $M)
(14,11) ==> final=13
(14,13) ==> final=13
(29,11) ==> final=28
(29,13) ==> final=28
(29,22) ==> final=28
(29,26) ==> final=28
(59,11) ==> final=58
(59,13) ==> final=58
(59,22) ==> final=58
(59,26) ==> final=58
(59,44) ==> final=58
(59,52) ==> final=58
(59,55) ==> final=58
(100,49) ==> final=99
(100,98) ==> final=99
(100,99) ==> final=99
Test script
use strict;
use warnings;
#========================================
# Algorithms
#========================================
sub ranges_javafan {
my ($M, $N) = @_;
return [ map {[int($_*($M+1)/$N)
, int(($_+1)*(($M+1)/$N))-1]
} 0..$N - 1];
}
#----------------------------------------
sub ranges_javafan_buk {
my ($M, $N) = @_;
my $STEP = ( $M + 1 ) / $N;
return [ map [int( $_ * $STEP ), int( ( $_+1 ) * $STEP ) -1]
, 0 .. $N - 1];
}
#----------------------------------------
sub ranges_elisheva_ikegami {
my ($M, $N) = @_;
my $r = ($M+1)%$N;
my $q = ($M+1-$r)/$N;
my $iEnd=0;
return [ map { my $iStart=$iEnd; [$iStart, ($iEnd+=$_) - 1]
} (($q+1) x $r, ($q) x ($N-$r)) ];
}
#========================================
# Check of final element of range
#========================================
sub roundCheck {
my ($cr, $M) = @_;
my $iTotal=0;
my $iErrors=0;
for my $m (1..$M) {
for my $n (1..$m) {
$iTotal++;
my $aRanges = $cr->($m, $n);
my $iFinal = $aRanges->[-1][1];
if ($iFinal != $m) {
$iErrors++;
# Uncomment here to see individual errors
# ---------------------------------------
# print "($m,$n) ==> final=$iFinal\n";
}
}
}
printf "Error rate: %s\n", ($iErrors*100/$iTotal);
}
#-------------------------------------------------------
print "Javafan:\n";
roundCheck(\&ranges_javafan, 100);
print "Javafan_buk:\n";
roundCheck(\&ranges_javafan_buk, 100);
print "elisheva_ikegami\n";
roundCheck(\&ranges_elisheva_ikegami, 100);
#outputs (Debian Linux - Lenny, perl 5.10.0, 32-bit)
Javafan:
Error rate: 2.47524752475248
Javafan_buk:
Error rate: 2.47524752475248
elisheva_ikegami
Error rate: 0
Update added test script and added parenthetical remark about platform dependency.
-
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.