Delphi Division with equal splitting of the rest (MOD)

Question

I have a math question which I try to solve with a Delphi function. I am trying to split up an integer into (nearly) equal pieces. Example:

You have 10 testcases and you want to execute them in 3 parts. So the best way to balance the workload would be to execute 3, 3, and 4 rather than 1, 1 and 8.

procedure calc_stream_numbers;
var div_res,rest:double;
    total,streams:integer;
begin
total := 10; 
streams := 3;
 div_res := total DIV streams;
 rest := total MOD streams;
 showmessage('Items: '  +IntToStr(total)+#13#10+
              'Streams: '+IntToStr(streams)+#13#10+
              'Result: '+FloatToStr(div_res)+
              'Rest: '+FloatToStr(rest));
end;

This gives me the division result of 10 / 3 = 3 (Rest 1) So I could execute 3 x 3 Testcases which makes 9 in total. To execute all 10 of them, I have to add the remaining one to any of the 3 streams. But If you have a more complicated example..

I am sure there is a mathematical expression for this but I must admit, I have noe clue. Maybe you are able to enlighten me how such a division is called and if there is any built-in delphi function.

Answer 1

You can code it like this:

function BalancedWorkload(Total, Count: Integer): TArray<Integer>;
var
  i: Integer;
begin
  SetLength(Result, Count);
  for i := 0 to Count-1 do
  begin
    Result[i] := Total div Count;
    dec(Total, Result[i]);
    dec(Count);
  end;
end;

You have Total units to split up into Count parts. We start with Total div Count for the first item. Then we have Total - (Total div Count) units left which need to be split into Count - 1 parts. Continue in this way until there's nothing left to do.

This algorithm could easily be written in a recursive way, but the iterative approach above somehow seems simpler to me.

---

Your entire approach assumes that you can predict ahead of time how long each task will take. But what if, for whatever reason, some tasks take longer than others? Then your approach will not be efficient. A better approach is to have a threadsafe queue of tasks. Let each consumer pull tasks off the queue and process them until there are no tasks left.

Answer 2

This function will calculate an array of integer containing the balanced workloads for each testcase.

function SplitInteger(Value: Integer; divisor: Integer): TArray<Integer>;
var
  d,i : Integer;
begin
  SetLength(Result,divisor);
  if (divisor = 0) then
    Exit;
  d := Value div divisor;
  for i := 0 to divisor - 1 do
    Result[i] := d;
  // Fill up with the remains
  for i := 0 to (value mod divisor) - 1 do
    Inc(Result[i]); 
end;

Answer 3

Here it is: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

One dimension is the amount of workloads, another one is amount of workers

---

Well, 2D Graphics is targeted at being eye-candy, so at fairly distributing "long" segments throughout "short" ones. In your case we can bias all the "long" ones to one end.

function SplitIntoEqualParts(Total, Count: Integer): TArray<Integer>;
var
  i: Integer;
  delta, delta1, extra: Word;
begin
  Assert( Count < High(Word) ); // RTL DivMod limitation
  SetLength(Result, Count);

  DivMod(Total, Count, delta, extra); 
  // one division operation is 2 times faster than two separate operations :-D
  delta1 := Succ(delta);      

  for i := 0 to extra-1 do 
    Result[i] := delta1;    
  for i := extra to Count-1 do 
    Result[i] := delta;    
end;

• http://delphi.about.com/library/rtl/blrtlDivMod.htm
• Is there a DivMod that is *not* Limited to Words (<=65535)?
• How do I implement an efficient 32 bit DivMod in 64 bit code