Получение надежного целочисленного процентного отношения из двух (64-битных) целых

Question

На моей платформе unsigned long long составляет 64 бита (8 байт). Предположим, у меня есть две такие переменные:

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

Как я могу надежно определить, сколько процентов (округленное до ближайшего целого числа) partialSize составляет totalSize? (Если возможно, было бы неплохо, если бы мне не приходилось предполагать, что первое меньше второго, но если мне действительно нужно сделать это предположение, это нормально. Но мы, конечно, можем предположить, что оба не -отрицательное.)

Например, является ли следующий код полностью пуленепробиваемым? Я боюсь, что он содержит какие-то ошибки округления, приведения или преобразования, которые могут привести к тому, что соотношение выйдет из строя в некоторых условиях.

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

Answer 1

Это не полностью пуленепробиваемый. double mantissae - это всего 53 бита (52 + 1 неявно), поэтому, если ваши числа больше 2^53, преобразование в double, как правило, приводит к ошибкам округления. Однако ошибки округления очень малы по отношению к самим числам, поэтому вычисление в процентах, приводящее к целочисленному значению, приведет к большей погрешности, чем преобразование.

Возможно, более серьезной проблемой является то, что она всегда будет округляться вниз, например для totalSize = 1000 и partialSize = 99 он вернет 9, а не более близкое значение 10. Вы можете улучшить округление, добавив 0.5 перед тем, как привести к unsigned long long.

Точные результаты можно получить, используя только целочисленную арифметику (если конечный результат не переполняется), это довольно просто, если partialSize не слишком велико:

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

Легкие модификации, если вы хотите, чтобы пол, потолок или округлились до половины.

Ничего страшного, если totalSize >= 100 и ULLONG_MAX / 100 >= partialSize % totalSize,

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

В других случаях это становится более беспокойным, я не заинтересован в этом, но я могу быть убежден, если вам это нужно.

Answer 2

Обратите внимание, что ваша формула неверна, так как в ней пропущено +0.5, необходимое для округления до ближайшего.

Итак, я продолжу предполагать, что эта исправленная формула:

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

Как я уже упоминал в комментариях, простой метод, хотя и простой, не гарантирует правильного округления результатов. Так что ваша интуиция права в том, что она не пуленепробиваема.

В подавляющем большинстве случаев оно все равно будет правильным, но будет небольшой набор пограничных случаев, где оно не будет правильно округлено. Независимо от того, зависит ли это от вас. Но простого метода обычно достаточно для большинства целей.

Почему может произойти сбой:

Есть 4 уровня округления. (исправлено из 2, которые я упоминал в комментариях)

1. 64-битные разряды -> 53-битные
2. Дивизион
3. Умножить на 100.
4. Окончательный состав.

Всякий раз, когда у вас есть несколько источников округления, вы страдаете от обычных источников ошибок с плавающей запятой.

Примеры счетчиков:

Хотя это редко, я приведу несколько примеров, когда прямая формула даст неверно округленный результат:

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

Решение:

Я не могу придумать чистого 100% пуленепробиваемого решения, кроме как использовать произвольную точность арифметики .

Но, в конце концов, вам действительно нужно, чтобы оно всегда было идеально округленным?

---

РЕДАКТИРОВАТЬ:

Для небольших чисел, вот очень простое решение, которое округляется до 0.5:

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

Это будет работать до тех пор, пока x * 100 + y/2 не переполнится.

@ Ответ Даниэля Фишера предлагает более полное решение для других способов округления. Хотя это не должно быть слишком сложно, чтобы изменить это, чтобы округлить до.

Answer 3

Одна формула всегда будет переполняться, вызывать сбой или давать большие ошибки для некоторых значений.
Эта комбинация работает почти всегда:

if (totalSize > 1000000) {
    pct = partialSize / (totalSize / 100);
} else {
    pct = (partialSize*100) / totalSize;
}

Сбой только в том случае, еслиpartalSize больше, чем MAX_U_LONG_LONG / 100и totalSize ниже 1000000. В этом случае правильный процент намного больше, чем 100%, поэтому это не очень интересно.