Greedy Program Running Forever

Question

I recently developed a simple program designed to take a certain amount of money (in dollars) and determine the least number of coins necessary to fulfill that requirement.

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    // prompts for change and assigns variable owed_change that value
    float owed_change = -1;
    while (owed_change < 0 )
    {
        printf("How much change is owed?\n");
        owed_change = GetFloat();
    }
    // sets the varialble n_coins to 0
    int n_coins = 0;
    // repeats until no more change is owed
    while (owed_change != 0)
    {
        /* checks for the biggest coin that can be used and increases 
        the number of coins by 1 */
        if (owed_change >= .25)
        {
            owed_change -= .25;
            n_coins++;
        }
        else if (owed_change >= .10)
        {
            owed_change -= .10;
            n_coins++;
        }
        else if (owed_change >= .05)
        {
            owed_change -= .05;
            n_coins++;
        }
        else
        {
            owed_change -= .01;
            n_coins++;
        }
    }
    printf("%d\n", n_coins);
}

The program works for multiples of .25 but runs forever for any other number. From testing, I have found out that it has something to do with the variable owed_change being subtracted from and coming to the result of -0, which satisfies owed_change != 0. However, from research, I have found out that -0 as a floating point should act as +0. If so, what else have I done wrong?

TL;DR: Floats are not exact. For technical details why, [see here](http://stackoverflow.com/questions/21895756/why-are-floating-point-numbers-inaccurate). When dealing with money, one option is to calculate everything in cents (using `int`s) or using an exact decimal type (not sure what that would be for C) or to use a delta (so instead of `!= 0` you'd have to check if owed_change is some value around 0, not sure what an appropriate value is) — Michael Stum, Mar 14 '17 at 23:55
equality comparisons of floats are iffy... so, `while (owed_change != 0)` will usually never be true. so use `while (owed_change < 0.009)` or something similar — bruceg, Mar 14 '17 at 23:55
0.25 is exactly representable as a `float` (usually), but many of the other denominations are not. What's likely happening is that `owed_change` ends up *almost* zero, but not exactly, so the loop continues. Generally you shouldn't use `float`s for this sort of thing -- try working with an integer number of cents instead of a floating point number of dollars. — Dmitri, Mar 14 '17 at 23:55
Because of [Floating point comparison](http://stackoverflow.com/q/7008649/2172854). — abhishek_naik, Mar 14 '17 at 23:55

score 3 · Accepted Answer · answered Mar 15 '17 at 00:04

3

It would be better, in your case, to work with money as cents and multiply all your values by 100. The reason for this is that floats are not exact values; that would be the reason why your code works for floating point values like 0.25, but not for smaller floating point numbers like 0.1, 0.05, and 0.01. For your purpose, you would be better off using an int value.

Instead of:

0.25$, use 25 cents
0.10$, use 10 cents
0.05$, use 5 cents
0.01$, use 1 cent

Change the data type of owed_change to int from float after making the above changes. That should resolve your problem.

answered Mar 15 '17 at 00:04

BusyProgrammer

2,783
5
18
31

A better idea is to use double but keep the amount in cents. That way you have more precision, and a graceful deterioration should very large or very small amounts of money be entered. – Malcolm McLean Mar 15 '17 at 00:09
Changing it to an `int` variable works just fine too. If you need more precision, you can use `long int` as well. – BusyProgrammer Mar 15 '17 at 00:11
2

@MalcolmMcLean Using cents in a `double` can still cause problems if the number entered is extremely large (unrealistically so, admittedly) or if a fraction is entered (unless explicitly rounded to an integer after). If the value is large enough, subtracting small numbers might not change it. – Dmitri Mar 15 '17 at 00:17

Greedy Program Running Forever

1 Answers1