See all articles

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.

By Katelyn Lesse

Senior Director of Engineering, Betterment |

Published Jul. 26, 2017

Chart going up and down next to a bullseye arrow

A Functional Approach to Penny-Precise Allocation Jul 26, 2017 12:00:00 AM How we solved the problem allocating a sum of money proportionally across multiple buckets by leaning on functional programming. 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 Emergency fund: $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. 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 Find the number of pennies that will be left over to allocate by taking the inflow minus the total of the integer quotients 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]. 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 12345631000/100000, 12345635000/100000, 12345620000 /100000 and 12345614000/100000. The integer quotients with their respective remainders are [38271, 36000], [43209, 60000], [24691, 20000], [17283, 84000]. 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. 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 emergency fund 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.

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
Emergency fund: $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.

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
Find the number of pennies that will be left over to allocate by taking the inflow minus the total of the integer quotients
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].

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 12345631000/100000, 12345635000/100000, 12345620000 /100000 and 12345614000/100000. The integer quotients with their respective remainders are [38271, 36000], [43209, 60000], [24691, 20000], [17283, 84000].

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.
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 emergency fund 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.