### Coin efficiency and the wisdom of quarters

I came across this post today on Freakonomics (via David Malki !), about the efficiency of various coin combinations. Go give it a read, or this post won't make much sense. Go on, I'll wait.

So in case you didn't read it, apparently if you want the least amount of coins in the average change from a purchase, the best combination (assuming four coins, starting at one cent) is one cent, three cents, 11 cents and 37 (or 38) cents. Of course, for the sake of simplicity this ignores the fact that some amounts of change are more likely than others (among other problems -- more on that later), but it's an interesting idea nonetheless.

Since I've been learning Perl at uni this semester I decided to try to write my own script to calculate this, as a coding exercise. That didn't take too long to code, but it sure took a long time to run -- not surprising really, as it has to find 152,096 coin combinations, calculate the efficiency for each one, and then sort the results. I did it on my laptop, and when I ran it it took about 4 and a half minutes to finish. On my desktop it was more like a minute.

The problem with the calculations in the article (and the program I wrote) is that they are limited in scope -- they're only for 4-coin systems which go down to the penny (i.e. America). Over here we have 4 (sub-dollar) coins too, but the smallest is 5 cents. I decided to modify the program to work for any number of coins, and any resolution (i.e. the smallest denomination). That led to a few hours of coding, during which the rest of the world faded out of existence like it always does during coding, only to snap back into place when I finish the program and I realise it's 8 o'clock and I want dinner.

This new version accepts command line arguments to set the number of coins and the smallest denomination. The downside is that is is much slower, taking nearly 4 minutes for a 4-coin, one-cent system (UPDATE: On my laptop it was more than 15 minutes). Having done that, I can say that the theoretical average number of coins of change for our system (5,10,20,50) is... 2.2. The most efficient system is (5,10,25,60) or (5,10,25,65), tying for first place at 2.05. Unlike the unweildy (1,3,11,37) combo, a (5,10,25,60) seems pretty good to me. I guess Americans aren't as silly as I thought they were for using quarters instead of 20-cent coins.

I alluded earlier to some problems with this whole idea. The algorithm I wrote to generate these results (and presumably also the one the other guy wrote, since we got the same results) sometimes overestimates the amount of coins. For example, if your system is (1,24,40) and you're getting 48 cents in change, the program will assume you're getting a 40-cent coin and eight one-cent coins for a total of nine coins. But really you could just get two 24-cent coins.

I'm going to try to fix the program to find the true minimum number of coins. Until then, here's the program.

Coin Efficiency Calculate-O-Mat v0.1

So in case you didn't read it, apparently if you want the least amount of coins in the average change from a purchase, the best combination (assuming four coins, starting at one cent) is one cent, three cents, 11 cents and 37 (or 38) cents. Of course, for the sake of simplicity this ignores the fact that some amounts of change are more likely than others (among other problems -- more on that later), but it's an interesting idea nonetheless.

Since I've been learning Perl at uni this semester I decided to try to write my own script to calculate this, as a coding exercise. That didn't take too long to code, but it sure took a long time to run -- not surprising really, as it has to find 152,096 coin combinations, calculate the efficiency for each one, and then sort the results. I did it on my laptop, and when I ran it it took about 4 and a half minutes to finish. On my desktop it was more like a minute.

The problem with the calculations in the article (and the program I wrote) is that they are limited in scope -- they're only for 4-coin systems which go down to the penny (i.e. America). Over here we have 4 (sub-dollar) coins too, but the smallest is 5 cents. I decided to modify the program to work for any number of coins, and any resolution (i.e. the smallest denomination). That led to a few hours of coding, during which the rest of the world faded out of existence like it always does during coding, only to snap back into place when I finish the program and I realise it's 8 o'clock and I want dinner.

This new version accepts command line arguments to set the number of coins and the smallest denomination. The downside is that is is much slower, taking nearly 4 minutes for a 4-coin, one-cent system (UPDATE: On my laptop it was more than 15 minutes). Having done that, I can say that the theoretical average number of coins of change for our system (5,10,20,50) is... 2.2. The most efficient system is (5,10,25,60) or (5,10,25,65), tying for first place at 2.05. Unlike the unweildy (1,3,11,37) combo, a (5,10,25,60) seems pretty good to me. I guess Americans aren't as silly as I thought they were for using quarters instead of 20-cent coins.

I alluded earlier to some problems with this whole idea. The algorithm I wrote to generate these results (and presumably also the one the other guy wrote, since we got the same results) sometimes overestimates the amount of coins. For example, if your system is (1,24,40) and you're getting 48 cents in change, the program will assume you're getting a 40-cent coin and eight one-cent coins for a total of nine coins. But really you could just get two 24-cent coins.

I'm going to try to fix the program to find the true minimum number of coins. Until then, here's the program.

Coin Efficiency Calculate-O-Mat v0.1