Free for 90 days: Sign up now and get 90 days managed free after your first deposit. See offer details

<title>Dismiss</title>
Engineering at Betterment

A Functional Approach to Penny-Precise Allocation

How we solved the problem allocating a sum of money proportionally across multiple buckets by leaning on functional programming.

Articles by Katelyn Lesse

By Katelyn Lesse
  |  Published: July 26, 2017

An easy trap to fall into as an object-oriented developer is to get too caught up in the idea that everything has to be an object. I work in Ruby, for example, where the first thing you learn is that everything is an object. Some problems, however, are better solved by taking a functional approach.
For instance, at Betterment, we faced the challenge of allocating a sum of money proportionally across multiple buckets. In this post, I’ll share how we solved the problem by leaning on functional programming to allocate money precisely across proportional buckets.

The Problem

Proportional allocation comes up often throughout our codebase, but it’s easiest to explain using a fictional example:

Suppose your paychecks are $1000 each, and you always allocate them to your different savings accounts as follows:

  • College savings fund: $310
  • Buy a car fund: $350
  • Buy a house fund: $200
  • Safety net: $140

Now suppose you’re an awesome employee and received a bonus of $1234.56. You want to allocate your bonus proportionally in the same way you allocate your regular paychecks. How much money do you put in each account?

You may be thinking, isn’t this a simple math problem? Let’s say it is. To get each amount, take the ratio of the contribution from your normal paycheck to the total of your normal paycheck, and multiply that by your bonus. So, your college savings fund would get:

(310/1000)*1234.56 = 382.7136

We can do the same for your other three accounts, but you may have noticed a problem. We can’t split a penny into fractions, so we can’t give your college savings fund the exact proportional amount.

More generally, how do we take an inflow of money and allocate it to weighted buckets in a fair, penny-precise way?

The Mathematical Solution: Integer Allocation

We chose to tackle the problem by working with integers instead of decimal numbers in order to avoid rounding. This is easy to do with money — we can just work in cents instead of dollars. Next, we settled on an algorithm which pays out buckets fairly, and guarantees that the total payments exactly sum to the desired payout. This algorithm is called the Largest Remainder Method.

1. Multiply the inflow (or the payout in the example above) by each weight (where the weights are the integer amounts of the buckets, so the contributions to the ticket in our example above), and divide each of these products by the sum of the buckets, finding the integer quotient and integer remainder

2. Find the number of pennies that will be left over to allocate by taking the inflow minus the total of the integer quotients

3. Sort the remainders in descending order and allocate any leftover pennies to the buckets in this order

The idea here is that the quotients represent the amounts we should give each bucket aside from the leftover pennies. Then we figure out which bucket deserves the leftover pennies.

Let’s walk through this process for our example:

Remember that we’re working in cents, so our inflow is 123456 and we need to allocate it across bucket weights of [31000, 35000, 20000, 14000].

1. We find each integer quotient and remainder by multiplying the inflow by the weight and dividing by the total weight. We took advantage of the divmod method in Ruby to grab the integer quotient and remainder in one shot, like so:

buckets.map do |bucket|
 (inflow * bucket).divmod(total_bucket_weight)
end

This gives us 123456*31000/100000, 123456*35000/100000, 123456*20000 /100000 and 123456*14000/100000. The integer quotients with their respective remainders are [38271, 36000], [43209, 60000], [24691, 20000], [17283, 84000].

2. Next, we find the leftover pennies by taking the inflow minus the total of the integer quotients, which is 123456 — (38271 + 43209 + 24691 + 17283) = 2.

3. Finally, we sort our buckets in descending remainder order (because the buckets with the highest remainders are most deserving of extra pennies) and allocate the leftover pennies we have in this order. It’s worth noting that in our case, we’re using Ruby’s sort_by method, which gives us a nondeterministic order in the case where remainders are equal. In this case, our fourth bucket and second bucket, respectively, are most deserving. Our final allocations are therefore [38271, 43210, 24691, 17284]. This means that your college savings fund gets $382.71, your car fund gets $432.10, your house fund gets $246.91, and your safety net gets $172.84.

The Code Solution: Make It Functional

Given we have to manage penny allocations between a person’s goals often throughout our codebase, the last thing we’d want is to have to bake penny-pushing logic throughout our domain logic. Therefore, we decided to extract our allocation code into a module function.

Then, we took it even further. Our allocation code doesn’t need to care that we’re looking to allocate money, just that we’re looking to allocate integers. What we ended up with was a black box ‘Allocator’ module, with a public module function to which you could pass 2 arguments: an inflow, and an array of weightings.

Our Ruby code looks like this.

The takeaway

The biggest lesson to learn from this experience is that, as an engineer, you should not be afraid to take a functional approach when it makes sense. In this case, we were able to extract a solution to a complicated problem and keep our OO domain-specific logic clean.

Recommended Content

View All Resources
WebValve – The Magic You Need for HTTP Integration

WebValve – The Magic You Need for HTTP Integration

Struggling with HTTP integrations locally? Use WebValve to define HTTP service fakes and toggle between real and fake services in non-production environments.

Displaying Performance to Shape Better Investor Behavior

Displaying Performance to Shape Better Investor Behavior

Understanding your accounts’ performance can feel complicated. We’re advancing how we display performance to help answer your questions and make stronger investment decisions.

Cash Analysis Methodology

Cash Analysis Methodology

Betterment's cash analysis aims to provide smart feedback when we think you have extra cash that could be earning you more value if it were in a higher yield account.

Explore your first goal

Safety Net

This is a great place to start—an emergency fund for life's unplanned hiccups. A safety net is a conservative portfolio.

Retirement

Whether it's a long way off or just around the corner, we'll help you save for the retirement you deserve.

General Investing

If you want to invest and build wealth over time, then this is the goal for you. This is an excellent goal type for unknown future needs or money you plan to pass to future generations.

<title>Close</title>

Search our site

For more information and disclosures about the Betterment Resource Center, click here. | See our contributors.