在 float 和 double 之间选择

Question

背景：

我一直在研究以下问题，"The Trip" 来自 S. Skiena 的 "Programming Challenges: The Programming Contest Training Manual"：

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 ,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.

（粗体是我的，书here, site here）

我用下面的代码解决了这个问题：

/*
 * 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;
}

我原来的实现有 float 而不是 double。它正在处理描述中提供的小问题实例，我花了很多时间试图找出问题所在。

最后我发现我必须使用 double 精度，显然编程挑战测试中的一些大输入使我的 float 算法失败。

问题：

鉴于输入可以有 1000 个学生，每个学生最多可以花费 10,000 美元，我的 total 变量必须存储最大大小为 10,000,000.

我应该如何决定需要哪种精度？有没有什么东西可以提示我 float 不足以完成这项任务？

我后来意识到，在这种情况下，我完全可以避免浮点数，因为我的数字适合整数类型，但我仍然有兴趣了解是否有办法预见 float在这种情况下足够精确。

Answer 1

10,000,000>2^23 所以您至少需要 24 位尾数，这是单精度提供的。由于中间舍入，最后一位可能会出错。

1个数字~3.321928位。

Answer 2

正如您所说：永远不要使用浮点变量来表示金钱。使用整数表示 - 可以是美分形式的一个大数字，也可以是当地货币的小数部分，或者是两个数字[这使得数学有点尴尬，但更容易 see/read/write 值作为两个单位]。

不使用浮点数的动机是 "often not accurate"。就像 1/3 不能用十进制表示为精确值一样，无论你写多少个三，实际答案都会有更多的三，二进制浮点值不能精确描述一些小数值，你得到 "Your value of 0.20 does not match 0.20 that the customer owes" - 这没有意义，但那是因为根据计算机，“0.200000000001”和“0.19999999999”并不完全相同。最终，这些小的舍入误差会以某种方式导致一些大问题——无论它是 float、double 还是 extra_super_long_double.

但是，如果你有这样的问题：如果我要表示一个1000万的值，精度为单位的1/100，我需要多大的浮点变量，你的计算就变成了:

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

因此，在这种情况下，我们得到的位为 29.897，因此您需要 30 位（换句话说，float 不够好。

当然，如果您不需要几分之一美元（或其他任何东西），您可以少花几位数。即 log2(10000000) = 23.2 - 所以 24 位尾数 -> 对于 float.

来说还是太大了

Answer 3

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

事实上 0.10 根本不能用二进制浮点数表示（如果您使用普通计算机，float 和 double 都是）应该是提示。二进制浮点数非常适合一开始就不准确的物理量，或者无论具有可判定相等性的合理数值系统如何都会不准确的计算。货币金额的精确计算不是二进制浮点数的良好应用。

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

使用整数类型表示美分数。根据您自己的推理，您不必处理超过 1,000,000,000 美分的金额，因此 long 应该足够了，但只需使用 long long 并避免遇到极端情况的麻烦。

在 float 和 double 之间选择

Choosing between float and double

c++

algorithm

floating-point

precision