greedy algorithm (with coins) in C

Question

In my code I usede the greedy algorithm in order to use the minimum amaount of coins. For example: I must return $0.41, the minimum amount of coins I can use is 4:

1 - 0,25;
1 - 0.10;
1 - 0.05;
1 - 0.01;

There are 4 types of coins: 0.25,0.10,0.05,0.01.

Here is my code:

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

int main(void)
{
    printf("Enter the sum, that you want to return you:");
    float sum = GetFloat();
    float quaters = 0.25;
    float dime = 0.10;
    float nickel = 0.05;
    float penny = 0.01;
    int count_q = 0,count_d = 0,count_n = 0,count_p = 0;


    while(sum<0){
        printf("Incorrect, enter the positive float number");
        sum = GetFloat();
    }

    while(sum > 0){
        if(sum - quaters >=0){
            sum -=quaters;
            count_q +=1;
        }
        else if((sum -quaters <0) && (sum -dime>=0)){
            sum -= dime;
            count_d +=1;
        }
        else if((sum - dime <0) &&(sum - nickel>=0) ){
            sum -= nickel;
            count_n +=1;
        }
        else if(sum - nickel <0){
            sum -= penny;
            count_p +=1;
        }
    }
    printf("The number of quaters: %i\n",count_q);
    printf("The number of dimes: %i\n",count_d);
    printf("The number of nickels: %i\n",count_n);
    printf("The number of pennies: %i\n",count_p);
}

This code calculates how many coins of each type of was used to return the sum. In most cases it works fine.

But sometimes, for example, when i enter the number 1.12 it gives me wrong result:

Enter the sum, that you want to return you:1.12
The number of quaters: 4
The number of dimes: 1
The number of nickels: 0
The number of pennies: 3

I think, that the problem is in last else if statement. But i don't know how can I correct it.

Answer 1

To my understanding, there is no bug in your code in the strictest sense, as the reasoning on which the implementation is based (a greedy algorithm) is correct. You are most likely experiencing rounding errors due to repeated subtraction, as you use float, the single-precision floating type to represent your values. Perhaps, if you change float to double in your code, the output will be as expected for your example input.

However, this only pushes the boundaries of the limitation. Perhaps it would be better to internally represent the amount of money in pennies as int.

Note that, when first confronted with the fact that floating point representations are inaccurate, I believed that the impossibility to represent some values and accumulation of rounding errors would be an issue only when you absolutely do some rocket science calculations, but would never be relevant for what I considered to be layman's calculations. However, this is not the case.