PSI - Breaking Up is (Not So) Hard to Do

Breaking Up Is (Not So) Hard To Do

Published in the Open Systems Database Association Newsletter, Fall 2002

Have you ever run into one of those situations where the answer to a problem seems obvious, but the obvious answer isn't necessarily the best one? For example, what is 10 divided by 3? The obvious answer, assuming 4-place precision (a standard for Multivalue systems), would be 3.3333. But is that the correct - or even best - answer?

If we define the question a little further and say that the answer must be expressed as an integer, then it would appear that this first obvious answer is obviously wrong. In this case, we might say that the best answer for this question is simply 3. But again, is that truly the best answer?

Defining the question even further, let's say that the answer - whatever it may turn out to be - must be able to be returned to its original form (that is, the original number) easily. To make this happen, we'd need to divide our number in such a way so that adding up the divided portions arrives back at our original value of 10. In this case, the floating-point answer won't work because 3.3333 x 3 = 9.9999, which is not quite the original answer. The integer answer is even farther (a whole number) away from the original value.

While this would appear to be a paradox, it is actually a very common problem faced by developers of scheduling software. Specifically, if we have a ten hour task that must be split into three days of work, with each day's time expressed in whole hours, how much work should be scheduled for each day?

Put into those terms, it's understandable that an equal division of time per day may not be the best answer. Without a calculator, can you quickly tell precisely how many extra minutes and seconds are in 3.3333 hours? Splitting the time equally and either truncating or rounding isn't much of a solution either, because both options result in fewer than 10 hours being scheduled.

Another approach to this is to schedule the time in portions that are unequal, but as equal as possible. For example, we may schedule three hours for each of the first two days, then four hours for the third. This results in our total of 10 hours being scheduled unequally, but as equally as possible (within the requirements). Alternatively, we might schedule the longer day first and the shorter days last, or the longer day in the middle of the shorter days. Regardless of how the days are arranged, this approach results in a total of 10 hours being scheduled in time blocks that are as equal as possible without getting into funky floating-point clock calculations.

Of course, 10 hours divided into three days isn't all that difficult to work out manually. But what if you have 98 hours divided into 17 days? Or 135 hours divided into 11 days? As the numbers get bigger, the calculation can become a bit more mentally challenging.

But then again, that's why we have computers. Using a technique that I call declining division¹ the division of any integer into as equal as possible parts is really quite simple. "Well, if it's so simple", perhaps you're thinking, "why bother writing about it?¨. Bottom line, it has been my experience that there's a lot of heinous code out there trying to achieve this simple objective, and my goal in writing this is merely to illustrate that one possible solution for this problem really doesn't have to be all that difficult.

Now, before the vendors of scheduling software start lighting up the flames, it's important to qualify that this calculation is just one component of the whole scheduling process. And it does present only one way of splitting time - integer hours per day. Nonetheless, the technique can easily be adapted to calculate fragments of time per day without any significant changes to the logic. For example, rather than calculating on whole hours, let's assume our time to be split is in quarter hours. Splitting 98 hours (392 quarter hours) into 17 days results in 1 day with 24 quarter hours, and 16 days with 23 quarter hours. Again, the calculation doesn't change with different time intervals; rather, we only need to change our basic unit of time and scale our time to be divided into that unit.

The principle of declining division is really quite simple. Start with a number to be divided and the number of times you want that number divided. To get the first answer, divide the original value by the original divisor, convert that answer to an integer, and add it to a list of results. In our original example of dividing 10 by 3, the integer portion of 10 divided by 3 is 3 - which is then added to our result list.

Next, the first answer is subtracted from the value, and the divisor is decremented. In our example, 10 - 3 = 7, and our new divisor is 3 - 1 = 2. These become the new values for calculating the second answer. Divide 7 by 2, convert the answer to an integer, and add this answer (3) to our result list. (Continue performing this calculation until the divisor is zero.) In the final iteration of our example, 7 - 3 = 4, and our divisor is now 2 - 1 = 1, giving a final answer is 4 / 1 = 4, which is then added to the result list and our calculation is complete.

Figure 1 contains the MV-BASIC code for calculating declining division. As you can see, it's not long, and all the work is done in the 14 executable lines in the 1000 subroutine. This routine could actually be slightly smaller, but it includes logic to arrange the results in either ascending or descending order. (Knowing that the largest numbers will usually be the result of the later calculations, all we have to do is add each answer to either the top or bottom of the list to arrange the list in a specific order.)

*
* Program Name: DECL.DIVIDE
* Written By:   Kevin King
* Date:         10 Aug 2002
* Description:  This program illustrates the "declining division" technique
*               for splitting a number into as equal as possible components 
*               with no remainder.
*
*****************************************************************************
* Modifications
*****************************************************************************
* Date.....  Changed By.....  Description of Change..........................
*
PROMPT ''
*
TRUE  = (1 EQ 1)
FALSE = NOT(TRUE)
*
PRINT 'What number is to be divided : ' :
INPUT VALUE
*
IF VALUE = '' OR NOT(NUM(VALUE)) THEN STOP
*
PRINT 'How many values do you want to divide ' : VALUE : ' into? ' : 
INPUT DIVISOR
*
IF DIVISOR = '' OR NOT(NUM(DIVISOR)) THEN STOP
*
SMALLEST.FIRST = FALSE
*
GOSUB 1000 ;* Do the work
*
PRINT 'Here are your results...'
PRINT
FOR RESULT.LOOP = 1 TO RESULT.CNT
  PRINT RESULT<1,RESULT.LOOP>
NEXT RESULT.LOOP
*
STOP
*
*****************************************************************************
1000 * Do the work
*****************************************************************************
*
RESULT     = ''
RESULT.CNT = 0
*
LOOP
WHILE (DIVISOR GT 0) DO
  THIS.VALUE = INT(VALUE / DIVISOR)
  *
  RESULT.CNT = RESULT.CNT + 1
  IF (SMALLEST.FIRST) THEN
    RESULT<1,RESULT.CNT> = THIS.VALUE
  END ELSE
    RESULT = INSERT(RESULT,1,1,0,THIS.VALUE)
  END
  *
  VALUE = VALUE - THIS.VALUE
  DIVISOR = DIVISOR - 1
REPEAT
*
RETURN

FIGURE 1 - DECL.DIVIDE - Sample MV-BASIC program illustrating declining division technique

Figure 2 shows the same logic in Java. Note that for the sake of simplicity, this class simply passes the values into the calculation instead of prompting for them, as the BASIC code does. (No need overcomplicating the obvious, right?)

import java.util.Vector;

/**
 * This class illustrates the "declining division" technique for splitting 
 * a number into as equal as possible components with no remainder
 */

public class DecliningDivide
{    
    public static Vector divide(int value, int divisor, boolean smallest_first)
    {
        Vector result = new Vector();
        
        while(divisor > 0)
        {
            Integer this_result = new Integer(value / divisor);
            
            if(smallest_first)
                result.add(this_result);
            else
                result.add(0,this_result);
            
            value = value - this_result.intValue();
            divisor--;
        }
        
        return(result);
    }
    
    public static void main(String[] args)
    {
        System.out.println(divide(10,3,false));
    }
}

FIGURE 2 - DecliningDivide - Sample Java class illustrating declining division technique

Regardless of whether this technique is used for scheduling or some other purpose, hopefully this has shown that it doesn't have to be an overly complex problem to solve. With a few lines of code and tried-and-true methods, even difficult problems can be easily conquered - even when the answers aren't all that obvious.

¹ This term is used in leiu of any more generally accepted mathematical term.

Kevin King is the President and Chief Technologist with Precision Solutions, Inc., a leading technology solutions provider in Longmont, Colorado. He can be reached by email at Kevin@PrecisOnline.com or by voice at 303/651-7050.