Как стать автором
Обновить

Переполнение при умножении

Время на прочтение 3 мин
Количество просмотров 14K
Перед выполнением умножения C++ приводит множители к одному типу не короче int, а разрядность результата совпадает с разрядностью приведенных множителей. Для того, чтобы не потерять точность, иногда требуется для умножения выполнять дополнительные операции.
Рассмотрим задачу. Система определяет время с момента запуска программы в тиках микропроцессора вызовом функции:
unsigned long long getTickCount();

Длина unsigned long long — 64 бита. Для преобразования в физические единицы времени в системе существует константа:
const unsigned long long TICKS_PER_SECOND = 1999000001ULL;

Требуется определить функцию перевода тиков в наносекунды getNsec(unsigned long long ticks) с семантикой:
unsigned long long getNsecNaive(unsigned long long ticks) {
    static const unsigned long long NSEC_PER_SECOND = 1000000000ULL;
    unsigned long long nsec =  NSEC_PER_SECOND * ticks / TICKS_PER_SECOND;
    return nsec;
}

Для функции getNsec() необходимо обеспечить максимально возможную точность. Параметр ticks может быть как большим, так и маленьким. Для маленьких ticks (скажем, до 2^34) нужно вычисления выполнять в следующем порядке:
(NSEC_PER_SECOND * ticks) / TICKS_PER_SECOND

То есть сначала умножать, потом делить. Поскольку NSEC_PER_SECOND < 2^30, при умножении не возникнет переполнения, так как его результат будет меньше 2^64.
Для больших ticks, поскольку умножение может вызвать переполнение, лучше выполнять операции в следующем порядке:
NSEC_PER_SECOND * (ticks / TICKS_PER_SECOND)

Проблема в данном случае состоит в том, что второй множитель — всегда целый, результат в десятичной системе счисления всегда будет оканчиваться девятью нулями, то есть фактически обеспечивается секундная точность и функцию getNsec() следует переименовать в getSec(). С другой стороны, исходные данные позволяют обеспечить большую точность.
С учетом неассоциативности машинных операций умножения и деления всего возможны 4 порядка вычислений, то есть еще 2 помимо двух рассмотренных:
(NSEC_PER_SECOND / TICKS_PER_SECOND) * ticks

и
ticks / (TICKS_PER_SECOND / NSEC_PER_SECOND)

Первый всегда дает ноль, а второй — ticks, то есть почти 50% ошибку (которую в данном случае можно свести до 0,1%, но эта погрешность все равно не наименьшая возможная).
Итак, в лучшем случае получаем секундную точность. Решить проблему увеличения точности можно следующими способами (в порядке увеличения предпочтения):
  1. Производить вычисления с вещественными (double) типами
  2. Приводить аргументы к 128-разрядным целым
  3. Использовать функцию MultDiv()
Данные подходы могут быть не применимы по причинам ограничений платформы (процессора), среды программирования и библиотек, требований проекта.
Воспользуемся следующим подходом. Пусть в результате деления ticks на TICKS_PER_SECOND получаем неполное частное seconds и остаток r:
unsigned long long seconds = ticks / TICKS_PER_SECOND; 
unsigned long long r = ticks % TICKS_PER_SECOND;

Тогда ticks = seconds*TICKS_PER_SECOND + r. Подставляем в формулу для nsec:
nsec = NSEC_PER_SECOND * (seconds*TICKS_PER_SECOND + r) / TICKS_PER_SECOND = NSEC_PER_SECOND*seconds + (NSEC_PER_SECOND*r) / TICKS_PER_SECOND. Поскольку r < TICKS_PER_SECOND, (NSEC_PER_SECOND*r) никогда не даст переполнения. Итоговая функция:
unsigned long long getNsec(unsigned long long ticks) {
    static const unsigned long long NSEC_PER_SECOND = 1000000000ULL;
    return NSEC_PER_SECOND * (ticks / TICKS_PER_SECOND)
        + ((NSEC_PER_SECOND)*(ticks % TICKS_PER_SECOND))/TICKS_PER_SECOND;
}

Результат получается ровно таким, как если бы мы посчитали NSEC_PER_SECOND*ticks как 128-битное значение, а потом разделили на TICKS_PER_SECOND, то есть обеспечивается максимальную точность для данных исходных значений и данной разрядности представления результата. Формула в операторе return никак не упрощается: ни NSEC_PER_SECOND, ни /TICKS_PER_SECOND за скобки не выносится.
Фактически решение задачи сведено к реализации функции MultDiv(a, b, c), вычисляющей a*b/c, где b и c — большие константы, а дробь b/c не сократима.
Теги:
Хабы:
+25
Комментарии 23
Комментарии Комментарии 23

Публикации

Истории

Работа

QT разработчик
13 вакансий
Программист C++
121 вакансия

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн