Obtaining a reliable integer percentage ratio from two (64-bit) integers

Question

On my platform, unsigned long long is 64 bits (8 bytes). Suppose I have two such variables:

unsigned long long partialSize;
unsigned long long totalSize;
//somehow determine partialSize and totalSize

How can I reliably determine how many percentages (rounded to a nearby integer) partialSize is of totalSize? (If possible, it would be nice if I wouldn’t have to assume that the former is less than the latter, but if I really have to make this assumption, it’s fine. But we can, of course, assume that both are non-negative.)

For example, is the following code completely bulletproof? My fear is that it contains some kind of rounding, casting, or conversion errors that could cause the ratio to go out of whack under some conditions.

unsigned long long ratioPercentage
    = (unsigned long long)( ((double)partialSize)/((double)totalSize) * 100.0 );

Answer 1

It's not completely bullet-proof. double mantissae are only 53 bits (52 + 1 implicit), so if your numbers are larger than 2^53, the conversion to double will in general introduce rounding errors. However, the rounding errors are very small in relation to the numbers itself, so a percentage calculation resulting in an integer value will introduce more inaccuracy than the conversion.

A possibly more serious concern is that this will always round downwards, e.g. for totalSize = 1000 and partialSize = 99, it will return 9 rather than the closer value 10. You can get better rounding by adding 0.5 before casting to unsigned long long.

You can get exact results using only integer arithmetic (if the final result doesn't overflow), it's fairly easy if partialSize is not too large:

if (partialSize <= ULLONG_MAX / 100) {
    unsigned long long a = partialSize * 100ULL;
    unsigned long long q = a / totalSize, r = a % totalSize;
    if (r == 0) return q;
    unsigned long long b = totalSize / r;
    switch(b) {
        case 1: return q+1;
        case 2: return totalSize % r ? q : q+1; // round half up
        default: return q;
    }
}

Easy modifications if you want floor, ceiling or round-half-to-even.

It's okay if totalSize >= 100 and ULLONG_MAX / 100 >= partialSize % totalSize,

unsigned long long q0 = partialSize / totalSize;
unsigned long long r = partialSize % totalSize;
return 100*q0 + theAbove(r);

It gets more fiddly in the other cases, I'm not keen on doing it, but I could be persuaded if you need it.

Answer 2

Note that your formula isn't correct as it omits the +0.5 needed to get round-to-nearest.

So I'll proceed assuming this corrected formula:

(unsigned long long)( ((double)partialSize)/((double)totalSize) * 100.0 + 0.5);

As I've mentioned in the comments, the straight-forward method, although simple, is not guaranteed to correctly rounded results. So your intuition is right in that it is not bullet-proof.

In the vast majority of cases, it will still be correct, but there will be a small set of borderline cases where it won't be correctly rounded. Whether or not those matter is up to you. But the straight-forward method is usually sufficient for most purposes.

Why it may fail:

There are 4 levels of rounding. (corrected from the 2 that I mentioned in the comments)

1. The casts 64-bits -> 53-bits
2. The division
3. The multiply by 100.
4. The final cast.

Whenever you have multiple sources of rounding, you suffer from the usual sources of floating-point error.

Counter Examples:

Although rare, I'll list a few examples where the straight-forward formula will give an incorrectly rounded result:

 850536266682995018 /  3335436339933313800  //  Correct: 25%  Formula: 26%
3552239702028979196 / 10006309019799941400  //  Correct: 35%  Formula: 36%
1680850982666015624 /  2384185791015625000  //  Correct: 70%  Formula: 71%

Solution:

I can't think of a clean 100% bullet-proof solution to this other than to use arbitrary precision arithmetic.

But in the end, do you really need it to always be perfectly rounded?

---

EDIT :

For smaller numbers, here's a very simple solution that rounds up on 0.5:

return (x * 100 + y/2) / y;

This will work as long as x * 100 + y/2 doesn't overflow.

@Daniel Fischer answer has a more comprehensive solution for the other rounding behaviors. Though it shouldn't be too hard to modify this one to get round-to-even.