Monday, November 08, 2021

Money is Hard in Programming

Last week I wrote about the making change for a dollar project. It got me thinking about how hard dealing with money in programming really is. The problem with money is that 1/10 is an infinitely repeating fraction in Binary.If one adds 1/10

Take the following C$ code.

double penny = 1.0 / 10.0;
double dime = 0.0;
Console.WriteLine(penny);  
for (int I = 0; I < 100; I++)
{
     dime += penny;
}
if (dime == 10.0) Console.WriteLine("Dime");
Console.WriteLine(dime);

One might expect that the word “dime” would be printed but it’s not. What this code actually prints is the following.

0.1
9.99999999999998

The 0.1 is expected but as you can see, adding the 0.1 100 times doesn’t give exactly 10.0. The problem often doesn’t show up right away. This sort of thing often confuses beginners because the programming language “helpfully” hides the issue. When I had the program display the value of “dime” after every addition the discrepancy don’t show up until around 6.0.

5.8
5.9
5.99999999999999

It’s not only beginners who struggle with this issue. It’s a pretty common issue and some languages support a currency data type for that reason. The currency data type adds some overhead to operations and not everyone is a fan of using it. A different alternative is to use integers and insert a decimal point on display.

One of the first programming languages I used for business related software, called DIBOL, didn’t support floating point numbers at all. It supported 18 digits of integer accuracy. It was an interesting language. Using it did make it easier for me to think about using integers for money later in my career though. Most beginners don’t have that sort of a helpful start. They are used to thinking in digital rather than binary. To my way of thinking this reinforces my thinking that learning binary is an important part of computer science education.

Thursday, November 04, 2021

How Many Ways to Make a Dollar

I ran into a reminder of an interesting programming problem the other day. One I meant to use with students but never did. Other teachers I know do use it. Simply pot, how many possible combinations of coins are there that add up to a dollar. It’s easily solved with a set of nested loops like the ones below.

int count = 0;

for (int halves = 0; halves <= 2; halves++)
{
     for (int quarter = 0; quarter <= 4; quarter++)
     {
         for (int dimes = 0; dimes <= 10; dimes++)
         {
             for (int nickels = 0; nickels <= 20; nickels++)
             {
                 for (int penny = 0; penny <= 100; penny++)
                 {
                     int value = halves * 50 + quarter * 25 + dimes * 10 + nickels * 5 + penny;
                     if (value == 100)
                     {
                         count++;
                     }
                 }
             }
         }
     }
}
Console.WriteLine(count);

It’s pretty straight forward. The key thing is understanding what coins there are and what their value it. The code above doesn’t include a dollar coin. Should it? Probably but it depends on the way the problem is specified. Also these are the coins currently being minted. Over the history of the country there have been a number of other coins in circulation

US TREASURY: What denominations of coins are no longer being produced?

There are quite a few denominations of coins that the United States Mint does not produce any longer for general circulation. They are the half-cent coin, the two-cent coin, the three-cent coin, the half-dime coin (although it was replaced by the five-cent coin), a twenty-cent coins, and the various denominations of gold coins. Although the Mint does produce a series of gold bullion coins, these are not intended for circulation.

The problem would be more interesting if some of these were allowed. I keep thinking that there must be another way to solve the problem though. I just can’t think of what it might be.

[Edit] Jeremiah Simmons shared information about solving this problem using Dynamic Programming. It's more complicated but scales better. Take a look. Understanding The Coin Change Problem With Dynamic Programming

It is so sawesome when educators share ideas with each other.