Choosing between float and double

Question

The background:

I have been working on the following problem, "The Trip" from "Programming Challenges: The Programming Contest Training Manual" by S. Skiena:

A group of students are members of a club that travels annually to different locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.

The group agrees in advance to share expenses equally, but it is not practical to share every expense as it occurs. Thus individuals in the group pay for particular things, such as meals, hotels, taxi rides, and plane tickets. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within one cent) all the students' costs.

Input

Standard input will contain the information for several trips. Each trip consists of a line containing a positive integer n denoting the number of students on the trip. This is followed by n lines of input, each containing the amount spent by a student in dollars and cents. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.

Output

For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.

(Bold is mine, book here, site here)

I solved the problem with the following code:

/*
 * the-trip.cpp
 */

#include <iostream>
#include <iomanip>
#include <cmath>

int main( int argc, char * argv[] )
{
    int students_number, transaction_cents;
    double expenses[1000], total, average, given_change, taken_change, minimum_change;
    while (std::cin >> students_number) {
        if (students_number == 0) {
            return 0;
        }
        total = 0;
        for (int i=0; i<students_number; i++) {
            std::cin >> expenses[i];
            total += expenses[i];
        }
        average = total / students_number;
        given_change = 0;
        taken_change = 0;
        for (int i=0; i<students_number; i++) {
            if (average > expenses[i]) {
                given_change += std::floor((average - expenses[i]) * 100) / 100;
            }
            if (average < expenses[i]) {
                taken_change += std::floor((expenses[i] - average) * 100) / 100;
            }
        }
        minimum_change = given_change > taken_change ? given_change : taken_change;
        std::cout << "$" << std::setprecision(2) << std::fixed << minimum_change << std::endl;
    }
    return 0;
}

My original implementation had float instead of double. It was working with the small problem instances provided with the description and I spent a lot of time trying to figure out what was wrong.

In the end I figured out that I had to use double precision, apparently some big input in the programming challenge tests made my algorithms with float fail.

The question:

Given the input can have 1000 students and each student can spend up to 10,000$, my total variable has to store a number of the maximum size of 10,000,000.

How should I decide which precision is needed? Is there something that should have given me an hint that float wasn't enough for this task?

I later realized that in this case I could have avoided floating point at all since my number fits into integer types, but I'm still interested in understanding if there was a way to foresee that float wasn't precise enough in this case.

Answer 1

As you said: Never use floating point variables to represent money. Using an integer representation - either as one large number in form of cents or whatever the fraction of the local currency is, or as two numbers [which makes the math a bit more awkward, but easier to see/read/write the value as two units].

The motivation for not using floating point is that it's "often not accurate". Just like 1/3 can't be writen as an exact value using decimal representation, no matter how many threes you write, the actual answer would have more threes, binary floating point values can not precisely describe some decimal values, and you get "Your value of 0.20 does not match 0.20 that the customer owes" - which doesn't make sense, but that's because "0.200000000001" and "0.19999999999" aren't exactly the same thing according to the computer. And eventually, those little rounding errors will cause some big problem in one way or another - and this regardless of if it's float, double or extra_super_long_double.

However, if you have a question like this: if I have to represent a value of 10 million, with a precison of 1/100th of the unit, how big a floating point variable do I need, your calculation becomes:

float bigNumber = 10000000;
float smallNumber = 0.01;
float bits = log2(bigNumber/smallNumber);
cout << "Bits in mantissa needed: " << ceil(bits) << endl;

So, in this case, we get bits as 29.897, so you need 30 bits (in other words, float is not good enough.

Of course, if you do not need fractions of a dollar (or whatever), you can get away with a few less digits. Namely log2(10000000) = 23.2 - so 24 bits of mantissa -> still too big for a float.

Answer 2

Is there something that should have given me an hint that float wasn't enough for this task?

The fact that 0.10 is not representable at all in binary floating-point (which both float and double are if you use an ordinary computer) should have been the hint. Binary floating-point is perfect for physical quantities that arrive inaccurate to begin with, or for computations that will be inaccurate anyway whatever the reasonable numerical system with decidable equality. Exact computations of monetary amounts are not a good application of binary floating-point.

How should I decide which precision is needed? … my total variable has to store a number of the maximum size of 10,000,000.

Use an integer type to represent numbers of cents. By your own reasoning, you shouldn't have to deal with amounts of more than 1,000,000,000 cents, so long should be enough, but just use long long and save yourself the risk of trouble with corner cases.

Answer 3

10,000,000>2^23 so you need at least 24 bits of mantissa, which is what single precision provides. Because of intermediate rounding, the last bits can err.

1 digit ~ 3.321928 bits.