Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Solving Foemmel's Conundrum: Fending off an Accounting Crisis

DZone's Guide to

Solving Foemmel's Conundrum: Fending off an Accounting Crisis

·
Free Resource

Patterns of Enterprise Architecture has long been the staple book in the world of enterprise system development, akin to the Gang of Four Patterns book for object-oriented design, and while many of the core patterns are often used, there is a great deal that can be learned from the Base Patterns described in this work. In particular, the Money Pattern describes a very practical problem, Foemmel's Conundrum, which is often the cause of many painstaking and intractable complications (for both the developer and end users).

Not only is this problem important for systems dealing with money, but it can also be applicable to systems dealing with similar constructs, such as time. This article describes the Conundrum and explores some of the possible extensions to the Money Pattern, described in Fowler's seminal work, that can be used to solve the Conundrum.

Defining the Problem

In most cases, handling money in a system is a simple task. Even in enterprise systems, a simple double may appear to be sufficient, but the shortfalls of this approach quickly become evident in more complex scenarios. One of those cases is called Foemmel's Conundrum1:

Allocate a whole amount of 5 cents into two accounts, where the first account contains 30% of the original amount and the second account contains 70% of the original amount.

Let's suppose the first account belongs to Alice and second account belongs to Bob. The simplest solution to this problem is to multiply the original amount by the respective percentages for each account. For Alice's account, this means multiplying 5 cents by 30%, which results in 1.5 cents; for Bob's account, this means multiplying 5 cents by 70%, which results in 3.5 cents. While this is a theoretical solution, it lacks pragmatic use: Few accountants would be placated with a balance sheet holding fractional cents.

If, instead, we round the values to the nearest cent, we end up with another problem. In Alice's case, the rounded value would be 2 cents, and in Bob's case, the rounded value would be 4 cents, totaling 6 cents. The same result would occur if we took the ceiling of both values. Conversely, if we take the floor of both values, we would obtain a total of 4 cents, with Alice holding 1 cent and Bob holding 3 cents. We are caught in a pickle: No accounting office would ever allow us to throw an extra penny in the mix to make the math work, nor would the same accounting office be okay with having a penny mysteriously leave the books.

Recapping, we have tried the following, but to no avail:

  1. Unrounded multiplication: results in fractional cents, which is not pragmatic for a real application or system
  2. Rounded multiplication: results in a greater total amount than we were originally dividing (i.e., the total amounts to 6 cents, even though we are trying to divide 5 cents)
  3. Ceilinged multiplication: results in the same problem as rounded multiplication, where we end up with a greater total than we started with (note that in the case of Alice and Bob's accounts, rounded multiplication devolves into ceilinged multiplication, where the amount possessed by both Alice and Bob are rounded up)
  4. Floored multiplication: results in a lesser total amount than we were originally dividing (i.e., the total amounts to 4 cents, even though we are trying to divide 5 cents)

The astute reader will notice, though, that we have only exhausted two of four rounding possibilities: (1) round both up; (2) round both down; (3) round Alice up and Bob down; and (4) round Alice down and Bob up. In the latter two options, we essentially pick a winner and loser: Either Alice or Bob will be rounded up, and the other will be rounded down. Picking Alice as the winner, we would round her 1.5 cents to 2 cents and round Bob's 3.5 cents down to 3 cents, totaling our original 5 cents. In the opposite case, Alice would end up with 1 cent and Bob would end up with 4 cents.

Although we have now solved this particular case of Foemmel's Conundrum, we have not solved the general case. In order to frame the general case, we need to move outside the realm of Alice and Bob and into a real-world application, where things become even trickier.

Generalizing the Problem

Suppose we are creating an accounting and payment application for a company with thousands of employees. In an effort to increase worker satisfaction, the company has requested that their employees be allowed to divide their paychecks into one or more accounts, so long as the total percentage equals 100%. For example, an employee can specify that his paycheck be divided in the following manner: 20% to his savings account, 70% to his checking account, 5% to his vacation club account, and 5% to a long-term savings account for a house he is looking to buy in the future.

In this case, we cannot hand-pick which portions to round up or round down to end up with the starting amount. Instead, we must devise an algorithmic way of completing this task. One general solution to this problem, proposed by Martin Folwer1, is the following:

Assuming the percentages total to exactly 100%, multiply each account percentage by the total amount and floor to the cent; distribute the remaining cents among the accounts until the original total is reached

For example, suppose a paycheck of $1,027.59 must be divided using the percentages described above. For the first step, we simply multiply each account percentage by the total amount and take the floor.

Account Percent Calculation Result
Savings 20 floor(1027.59 * 0.20) = floor(205.518) 205.51
Checking 70 floor(1027.59 * 0.70) = floor(719.313) 719.31
Vacation Club 5 floor(1027.59 * 0.05) = floor(51.3795) 51.37
Long-term Savings 5 floor(1027.59 * 0.05) = floor(51.3795) 51.37
Total 1,027.56

This totals $1,027.56, which is 3 cents short of our original total. We then distribute the remaining cents among the accounts until all remaining cents have been exhausted. The method of distribution can be made to be complex or simple. For example,

  1. Sequential distribution: distribute the cents starting with the first account and continuing sequentially until there are no cents remaining
  2. Minimization of truncation: give a cent to the account who had the greatest amount truncated during the floor operation, followed by the next highest truncated amount, continuing until all remaining cents are exhausted (for example, vacation club and long-term savings accounts had 0.95 cents truncated, so they would receive 1 cent of the remaining amount, respectively; the remaining cent would be given to the savings account, since it had o.80 cents truncated, which is more than the 0.30 truncated from the checking account)
  3. Minimization of degree of change: give a cent to the the account with the greatest percent, followed by the next greatest percent, continuing until all remaining cents are exhausted (for example, give the first cent to the checking account, which has 70% of the distribution, followed by the savings, at 20%, and then either, not both, the vacation club or long-term savings, which each have 5%; by giving the remaining cents to the account that has the highest percentage, the percent that the account increases is minimized; i.e., giving a cent to the checking account only adds 0.0014%, but adding a cent to the vacation club changes the vacation club amount by 0.019%)
  4. Random distribution: Pseudo-randomly distribute the cents among the remaining accounts; the disadvantage of this approach is the appearance to the user (what if, for example, all the remaining cents are randomly added to a single account?)

For the sake of simplicity and user understanding, sequential distribution is acceptable. This results in the following values:

Account Percent Calculation Result
Savings 20 1027.59 * 0.20 = 205.518 + 1 205.52
Checking 70 1027.59 * 0.70 = 719.313 + 1 719.32
Vacation Club 5 1027.59 * 0.05 = 51.3795 + 1 51.38
Long-term Savings 5 1027.59 * 0.05 = 51.3795 51.37
Total 1,027.59

The total amount now reaches $1,027.59. With the conceptual solution understood, we can now move on to creating a codified solution.

Codifying the Solution

As seen above, the solution to Foemmel's Conundrum is not trivial, and therefore, sprinkling its logic throughout a system is a poor design decision. Instead, we should encapsulate this logic into its own class. This encapsulation manifests itself in the form of Martin Fowler's Money Pattern. In following this this pattern, we will create a Money class that stores the number of cents as a long integer value and provides a method for allocating the number of cents contained in the Money object using the provided ratio (i.e., 20%, 70%, 5%, and 5% in the above example).

In an effort to make this solution more general, we will allow a user to provide any set of ratios. For example, if the ratios 1 and 2 are supplied, we will allocate 1 cent to the first account for every 2 cents allocated to the second account: Given a total of 6 cents, the first account will have 2 cents and the second will have 4 cents.

Although the Money Pattern includes methods for other manipulations of money (such as multiplication), for the sake of brevity, our Money class will not include these methods. This results in the following class structure:2

public class Money {

    private long cents;

    public Money (long cents) {
        this.cents = cents;
    }

    public long getCents () {
        return this.cents;
    }

    public Money add (long cents) {
        this.cents += cents;
        return this;
    }

    public List<Money> allocate (List<Integer> ratios) {
        // Obtain the divisor for the ratios (sum of individual ratio values)
        int ratioTotal = ratios.stream().mapToInt(Integer::intValue).sum();

        // Set the remainder to the original total
        long remainder = this.cents;

        // Allocate the list of money values to be returned
        List<Money> results = new ArrayList<>();

        for (int i = 0; i < ratios.size(); i++) {
            // Compute the value (total * percent)
            // I.e. ratio = {1,2}, then (1 / 3) and (2 / 3) respectively
            long value = (long) (this.cents * ratios.get(i) / (double) ratioTotal);

            // Store the result
            results.add(new Money(value));

            // Subtract the result amount from the remainder
            remainder -= results.get(i).getCents();
        }

        for (int i = 0; i < remainder; i++) {
            // Iterate through each cent of the remainder
            results.get(i).add(1);
        }

        return results;
    }

    @Override
    public String toString () {
        return String.format("$%.2f", this.cents / 100.0);
    }
}

Using the following main method, we obtain a solution to Foemmel's Conundrum:

public static void main (String[] args) {
    // Create a money object with 5 cents
    Money money = new Money(5);

    // Allocate the 5 cents 30/70
    System.out.println(money.allocate(Arrays.asList(30, 70)));
}

This results in the output [$0.02, $0.03], which is the solution we previously devised. Using the following main method, we can obtain our previously devised solution to the accounting problem:

public static void main (String[] args) {
    // Create a money object with 5 cents
    Money money = new Money(102759);

    // Allocate the 5 cents 30/70
    System.out.println(money.allocate(Arrays.asList(20, 70, 5, 5)));
}

This results in the output [$205.52, $719.32, $51.38, $51.37], which matches our devised solution. While our Money class does provide the correct values for both of our scenarios, it can be made more flexible. As previously described, there are many ways in which the remaining cents can be distributed among the values. In order to let clients decide on the best technique for the distribution of the remaining cents, we can use the Strategy Pattern.

The constructor of our Money class will now accept a strategy for the remainder distribution algorithm. This strategy can be provided explicitly when a Money object is created, or injected using a Dependency Injection (DI) framework. The interface for the distribution algorithm is

public interface RemainderDistributor {
    public void distribute (List<Money> values, long remainder);
}

A strategy implementation for our sequential distribution algorithm would resemble

public class SequentialDistributor implements RemainderDistributor {

    @Override
    public void distribute(List<Money> values, long remainder) {

        for (int i = 0; i < remainder; i++) {
            // Iterate through each cent of the remainder
            values.get(i).add(1);
        }
    }
}

Our Money class would now resemble the following:

public class Money {

    private long cents;
    private RemainderDistributor distributor;

    public Money (long cents, RemainderDistributor distributor) {
        this.cents = cents;
        this.distributor = distributor;
    }

    public long getCents () {
        return this.cents;
    }

    public Money add (long cents) {
        this.cents += cents;
        return this;
    }

    public List<Money> allocate (List<Integer> ratios) {

        // Obtain the divisor for the ratios (sum of individual ratio values)
        int ratioTotal = ratios.stream().mapToInt(Integer::intValue).sum();

        // Set the remainder to the original total
        long remainder = this.cents;

        // Allocate the list of money values to be returned
        List<Money> results = new ArrayList<>();

        for (int i = 0; i < ratios.size(); i++) {
            // Compute the value (total * percent)
            // I.e. ratio = {1,2}, then (1 / 3) and (2 / 3) respectively
            long value = (long) (this.cents * ratios.get(i) / (double) ratioTotal);

            // Store the result
            results.add(new Money(value, this.distributor));

            // Subtract the result amount from the remainder
            remainder -= results.get(i).getCents();
        }

        // Delegate to the distributor
        this.distributor.distribute(results, remainder);

        return results;
    }

    @Override
    public String toString () {
        return String.format("$%.2f", this.cents / 100.0);
    }
}

This new Money class can be rechecked using the following main method:

public static void main (String[] args) {
    // Create a money object with 5 cents
    Money money = new Money(5, new SequentialDistributor());

    // Allocate the 5 cents 30/70
    System.out.println(money.allocate(Arrays.asList(30, 70)));

    // Create a money object with $1,027.59
    Money accountMoney = new Money(102759, new SequentialDistributor());

    // Allocate the money to each account
    System.out.println(accountMoney.allocate(Arrays.asList(20, 70, 5, 5)));
}

Note that we are explicitly creating the Money objects, and therefore, we are explicitly supplying a distribution strategy. When the new Money objects are created in the allocate method, these objects are supplied with the same distributor object as the Money object that created them. If a DI framework were used, the creation of the new Money objects would be delegated to the framework. 

With this, clients now have a means to use other distribution techniques for the remaining cents. While our Money class is functioning as expected, there are a few edge cases that should be considered.

Accounting for Edge Cases

Just as with every system, there are always edge cases that must be considered. In the case of the allocate method of our Money class, there are few main problems we must look for (there are many others, but in an effort to describe the nature of the Conundrum, the following have been selected):

  1. Providing more non-zero ratios than cents
  2. Providing zero as a ratio value
  3. Providing an empty list of ratios
  4. Dividing a total of 0 cents by any ratios

Providing More Non-Zero Ratios than Cents

In the first case, we may try to divide N cents by N + 1 non-zero ratios. For example, what happens if we try to divide 5 cents evenly into 6 buckets? In this case, there is no way to avoid one of the buckets being the loser, where it contains 0 cents, while all other buckets contain 1 cent. Using a sequential distributor, the first five buckets should contain 1 cent, while the sixth bucket should contain 0 cents. 

When the allocate method is execute with these parameters, the results are initially filled with 0 cents, because a ratio of 1/6 is multiplied by 5 cents (the total), which results in fractional cents (5/6 cents, which in turn results in 0 cents). The distributor is then left with a remainder of 5 cents, which it sequentially distributes to the results. This leaves us with the first five buckets containing 1 cent and the sixth bucket containing 0 cents. This edge case can be tested using the following:

// Create a money object with 5 cents
Money money = new Money(5, new SequentialDistributor());

// Allocate the 5 cents evenly 6 ways
System.out.println(money.allocate(Arrays.asList(1, 1, 1, 1, 1, 1)));

resulting in [$0.01, $0.01, $0.01, $0.01, $0.01, $0.00], as expected. What if the ratios are not event distributed? For example, suppose that the ratios 2 and 4 are provided. In this case, the first ratio will result in 1 cent being added to the first bucket (5 * (2/6), or 10/6, floored to 1) and 3 cents being added to the second bucket (5 * (4/6), or 20/6, floored to 3). The remaining cent will be distributed to the first account, resulting in the first bucket containing 2 cents and the second containing 3 cents. If the order of the ratios were flipped, the result would be 4 and 1 cents, respectively. Both ratio orderings can be tested using the following main method:

public static void main (String[] args) {
    // Create a money object with 5 cents
    Money money = new Money(5, new SequentialDistributor());

    // Allocate the 5 cents 2/4 and 4/2
    System.out.println(money.allocate(Arrays.asList(2,4)));
    System.out.println(money.allocate(Arrays.asList(4,2)));
}

Executing this method results in the outputs [$0.02, $0.03] and [$0.04, $0.01], respectively. 

Providing Zero as a Ratio Value

The second edge case is also already handled, except in one particular case. If a ratio of zero is provided (assuming at least one other non-zero ratio is also provided), then its respective bucket will not contain any cents. For example, 

// Create a money object with 5 cents
Money money = new Money(5, new SequentialDistributor());

// Allocate the 5 cents 30/0/70
System.out.println(money.allocate(Arrays.asList(3, 0, 7)));

will result in [$0.02, $0.00, $0.03]. The case that must be explicitly handled occurs when zero is the only ratio supplied (or, one or more zero ratios are provided without including any other non-zero ratios). For example, we try to split 5 cents with a ratio of 0. As our Money class stands now, an exception will be thrown, because our sequential distributor will be left with 5 cents to distribute, but only 1 bucket to iterate over.

In the normal case, there will never be more remaining cents than buckets, so we do not have to account for a case where, for example, the remainder is 5, but the number of buckets is 1. Instead of placing all of the remaining cents in the single bucket (because a ratio of zero should result in 0 cents in the bucket), we will add a conditional to check for this event at the top of our allocate method:

public List<Money> allocate (List<Integer> ratios) {

    // Obtain the divisor for the ratios (sum of individual ratio values)
    int ratioTotal = ratios.stream().mapToInt(Integer::intValue).sum();

    if (ratioTotal == 0) {
        // The ratio totals 0
        List<Money> result = new ArrayList<>();

        // Add as many 0 values are there are zero ratios
        ratios.forEach(ratio -> result.add(new Money(0, this.distributor)));

        return result;
    }

    /* The rest of the method remains unchanged */
}

Now, if we supply a list that contains only 0 ratios (one or more), the returned list will contain the same number of elements as the supplied ratio list, each with a value of 0. For example, supplying [0] as the ratio list results in [$0.00], and supplying [0, 0] as the ratio list results in [$0.00, $0.00].

Providing an Empty List of Ratios

The case where an empty list is provided can be handled by simply returning an empty list (thus, if an empty list of ratios is provided, an empty list of Money objects is returned):

public List<Money> allocate (List<Integer> ratios) {

    if (ratios.size() == 0) {
        // No ratios were provided
        return new ArrayList<>();
    }

    // Obtain the divisor for the ratios (sum of individual ratio values)
    int ratioTotal = ratios.stream().mapToInt(Integer::intValue).sum();

    /* The rest of the method remains unchanged */
}

Therefore, if we provide [] to the allocate method, we will get [] in return.

Dividing a Total of 0 Cents by Any Ratios

The final edge case to consider is what happens when 0 cents are divided using any ratio. In this case, there should be as many buckets as ratios, all with the value 0. Currently, this case is handled: The total value is multiplied by the ratio, thus resulting in a list containing all zeros and of length N, where N is the number of supplied ratios. Although this case is implicitly handled, the handler for all 0 ratio inputs can be amended to to immediately return the desired 0-filled list when this last edge case is encountered:

public List<Money> allocate (List<Integer> ratios) {

    /* Previous parts of method remain unchanged */

    if (ratioTotal == 0 || this.cents == 0) {
        // The ratio totals 0
        List<Money> result = new ArrayList<>();

        // Add as many 0 values are there are zero ratios
        ratios.forEach(ratio -> result.add(new Money(0, this.distributor)));

        return result;
    }

    /* The rest of the method remains unchanged */
}

This case can be tested using the following snippet

// Create a money object with 0 cents
Money money = new Money(0, new SequentialDistributor());

// Allocate the 0 cents 1/2/3
System.out.println(money.allocate(Arrays.asList(1,2,3)));

which results in the output [$0.00, $0.00, $0.00].

Conclusion

In daily life, as well as in enterprise system development, there are numerous problems that stand the test of time, and Foemmel's Conundrum is one of them. While this issue may properly be ignored in small systems or personal applications, this is not acceptable for most enterprise level systems. Instead, this problem must be dealt with head on.

One of the simplest solutions is described in Martin Fowler's Patterns of Enterprise Application Architecture in form of the Money pattern. While this pattern solves this recurring problem for money-based components, it is also applicable for many other realms, such as time (how can 5 seconds be divided 30/70 without gaining or losing a second?). Since this problem has existed since the dawn of currency, it is here to stay, therefore, we must account for this age old problem: Foemmel's Conundrum.

Source Code

The Gradle-based source code, along with automated unit tests, for this article can be found on Github.

Footnotes

  1. Fowler, Martin. Patterns of Enterprise Application Architecture. Boston: Addison-Wesley, 2003. Print. <http://www.martinfowler.com/books/eaa.html>
  2. Although the type of the remainder is a long, an int type is used for iteration when distributing the remaining cents. This conversion occurs because the list of Money objects can only be accessed using an int type, not a long. This conversion, while unsafe, is sufficient for the demonstrations provided in this article, as the int type does not store the original total (a long value), but only the remaining cents during distribution, which is likely to be only a fraction of the original total (i.e., can at worst be equal to the number of ratios provided). For greater safety, a more encapsulated number type can be used, such as BigDecimal.
Topics:
java ,money ,patterns ,enterprise architecture ,enterpise integration ,accounting

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}