Splitting a floating point number almost-equally with no loss

Question

Assuming 2 digits after decimal visual representation of floating point number (eg: currency), what's the best way to split an amount with minimum total error?

For example, to distribute 100.00 equally to 3 bank accounts, I'd do something like this:

double amount = 100.0;
double acc1 = amount / 3.0;
double acc2 = amount / 3.0;
double acc3 = amount / 3.0;

However when printing each of the account balance with 2 decimal, I get:

printf("%.2f\n", acc1);
printf("%.2f\n", acc2);
printf("%.2f\n", acc3);

33.33
33.33
33.33

It's apparent summing up all of the account's amount gives 99.99, a 0.01 is lost due to rounding.

Ideally I want some function / algorithm that can distribute almost-equally and visually print

33.34
33.33
33.33

It doesn't matter which of the three accounts get the extra 0.01.

How do I do this? Is there any rounding algorithm name for this?

Answer 1

You are making multiple errors here. double is a double-precision binary floating-point number. 100.0 / 3.0 equals 33.33333333333333570180911920033395290374755859375; the problem with giving everybody 100.0/3.0 is not that you are giving everyone slightly less than the full amount of cake, but rather you are trying to give everyone more cake than you have. You then round this to two decimal places, which is an operation you cannot reasonably expect to preserve the sum.

I would suggest trafficking in integer numbers of cents instead of floating-point numbers of dollars in your application.

With that said, to split a cake of size C into floating-point parts for distribution among n people, you can give n-1 people pieces of size C/n and the last person a piece of size fma(-C/n, n-1, C). The fused multiply-add is necessary here since the multiplication in (C/n)*(n-1) may incur roundoff error. One can also accomplish this using fmod or remainder.

Answer 2

Using floating-point numbers to represent currency is just asking for trouble; integers would be much more appropriate for this purpose.

For this problem, you want to first distribute original sum x to n people using floored division (round downwards to the nearest cent):

int q = x / n;

(Here I'm assuming integer arithmetic with cents.) In the case of x = 10000 and n = 3, you calculate the quotient q = 10000 / 3 = 3333 and give that to everyone:

33.33
33.33
33.33

Then, calculate the remainder:

int r = x % n;

and distribute the remaining r cents to r people (give them one each). Since r is always less than the number of people, you will need to decide who gets to be the lucky winners.

In the example, r = 10000 % 3 = 1, so we have one cent that can only be given to one person:

33.34 = 33.33 + 0.01
33.33
33.33

You can also calculate this directly using an explicit formula. The number of cents that the i-th person receives is given by:

y[i] = q + (i < r);

where 0 ≤ i < n.

Answer 3

Since addition is not even associative in floating point arithmetic, your problem is not well defined...
(Well it might be well defined, see update 2, but some naive expectations might be a cause of surprise)

If you have (x+y) + z == sum, there is not much guaranty that x + (y+z) == sum

For example, say you want to split 0.31 in 3 IEEE 754 double precision, 0.10, 0.10 and 0.11
Here is sum computed back (the shortest decimal fraction that would round to the same float as the sum)

0.10+0.10+0.11 == 0.31
0.11+0.10+0.10 == 0.31000000000000005

These two numbers are very close, but not the same, and no one is really equal to 31/100 but well...
In the second form, you could do a slight correction:

0.10999999999999999 + 0.10 + 0.10 == 0.31

That means that depending on the order you use to sum back, results shall differ...
So what do you expect exactly from floating point?

Of course, you could just ignore those tiny differences and continue using floating point to do the necessary quotient/remainder operations if you are sure that rounding errors will never accumulate dangerously; it's possible to use float but you should then question each and every naive expectation and it can get tricky. My advice would be to simply use integer arithmetic as others suggested.

UPDATE

After reading the link Rounding floats so that they sum to precisely 1 from PascalCuoq, I realized that 0.10999999999999999 is in all case a better solution than 0.11 because it's 0.31-(0.31-0.11), and because 0.31-(0.31-0.1)==0.1. Thanks PascalCuoq!

UPDATE 2

The non associativity is essential because it implies that two different naive implementations will lead to different results.

However, as underlined by tmyklebu, the exact sum is well defined, though not easily accessible in C/C++.

In above example, the exact sum of nearest double to 10/100 , 10/100 , 11/100 slightly excess the nearest double to 31/100, so we have to adjust one of the operands down by an ulp. This is what makes floating point usage arguable more than the single property of associativity.

This can be illustrated if we try to fairly distribute the double amount=0.30 in 3 double: because the nearest double to 30/100 is exactly 5404319552844595/18014398509481984, and since the numerator is not divisible by 3 (the remainder is 1), then it cannot be split in 3 equal doubles. The quotient of 5404319552844595/3 divided by 18014398509481984 will lead to the predecessor of 0.1, and we have to adjust one operand by increasing with an ulp. Naive sum hereunder matches exact sum:

0.09999999999999999+0.09999999999999999+0.1 == 0.3 

This is another form of the very well known (at least on SO) 0.1+0.1+0.1 != 0.3