Re: Split range 0 to M into N non-overlapping (roughly equal) ranges.

My immediate solution was quite similar to your approach. To look for something different, I thought about how it would work if we were counting down from $M to zero. My current approach puts all the leftovers from repeatedly subtracting $step from $M into the last range:

($N,$M)=@ARGV;
($step,$s)=(int$M/$N,0);
puhs @ranges, [$M-$step,$M],$M-=$step
    while($M and ($M > 2*$step or $M%$step==0));
print 'Last step oversized by ',$M-$step
[download]

This approach seems somewhat shorter, but it certainly is not clearer. Especially the test when to continue is ugly and wrong - if $M is 2*$step -1, you will only get one highly oversized range instead of one undersized and one ideal range. I'm not sure how to fix this.

But this approach reminds me of Bresenham's line algorithm, which more or less has the same problem, to segment a line into roughly equal-sized segments, except that it distributes these segments in a 2-dimensional way. This algorithm likely has no nicer formulation than what you already have though, but it will distribute the oversized ranges much nicer, and the size difference between two ranges will never be larger than 1.

Comment on Re: Split range 0 to M into N non-overlapping (roughly equal) ranges. Select or Download Code

Replies are listed 'Best First'.
Re^2: Split range 0 to M into N non-overlapping (roughly equal) ranges. by chrestomanci (Priest) on Mar 12, 2011 at 21:54 UTC
++ insightful Searching CPAN for "Bresenham's line algorithm" returns Algorithm::Line::Bresenham, and an XS version. It looks like it would be feasible to re-purpose the algorithm to split a range a the OP wants.	[reply]
Re^3: Split range 0 to M into N non-overlapping (roughly equal) ranges. by BrowserUk (Patriarch) on Mar 12, 2011 at 22:24 UTC
The problem with Bresenham is that it requires you to iterate the entire range (segment) one at a time. For 360 degrees (or just 45 if you use the 1/8th mirroring optimisation), that isn't a problem, but for ranges above 100,000 or so (and many of mine are in the 10s or 100s of millions), it would be horribly slow. 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.	[reply]
Re^4: Split range 0 to M into N non-overlapping (roughly equal) ranges. by Corion (Patriarch) on Mar 12, 2011 at 23:21 UTC
I knew that all those days looking at assembly language line drawing algorithms would some day pay off. I'm almost certain there is an "improved" Bresenham algorithm that does not require you to paint the line pixel-by-pixel - but unfortunately, I can't find it. Most likely, it is discussed in the "Mode X" articles published around 1990. The "Mode X" was a graphics mode where you could write up to four bytes of (8 bit) graphics memory, by writing one byte to the graphics bus. This greatly improved (non-OpenGL) rasterizers, as long as they could tell when the next error overflow was bound to happen. And yay, Google Gives! Michael Abrash's book, "Graphics Programming", is online, and it has the discussion of how to turn Bresenham's Algorithm 90 degrees sideways, so you get to know how long a run (=range) is without iterating it. I'm not convinced that this solution is any better than your original approach, as the algorithm plus setup is best stuffed away in a subroutine, and it certainly is not really self-explaining to the casual onlooker. But at least this made me revisit ideas of the olden times and find an application for a somewhat unrelated topic.	[reply]
Re^5: Split range 0 to M into N non-overlapping (roughly equal) ranges. by BrowserUk (Patriarch) on Mar 13, 2011 at 00:22 UTC


go ahead... be a heretic
	PerlMonks