Потолок деления длинных целых в переполнении стека
Я пытался решить какую-то проблему, которая включает в себя деление больших чисел. Я наткнулся на определенный сценарий, где я получаю неправильные результаты, используя:
LL result = (LL) ceil ((double) (a-b) / c), где a, b и c — длинные длинные целые числа (LL).
#include <stdio.h> /* printf */
#include <math.h> /* ceil */
#define LL long long
int main ()
{
LL a= 10000000000000000;
LL aa = 10000000000000000-1;
LL aaa = 10000000000000000+1;
int b = 1;
int c = 1;
printf ( "%Ld\n", (LL)ceil((double)(a-b)/c) );
printf ( "%Ld\n", (LL)ceil((double)(aa-b)/c) );
printf ( "%Ld\n", (LL)ceil((double)(aaa-b)/c) );
return 0;
}
Output:
10000000000000000
9999999999999998
10000000000000000
Это начинает происходить с целыми числами, которые больше или равны 10 ^ 16 и делятся на 10.
Верхняя граница long long ~ 10 ^ 18.
Итак, что вызывает эту ошибку?
Я использую GCC 5.1 в режиме C ++ 14 (на ideone.com).
Решение
Хотя он может хранить цифры с гораздо большим величина, типичная реализация double может поддерживать только около 15-16 цифр точности.
Вычитание с плавающей запятой также может быть проблемой, особенно если два числа имеют примерно одинаковую величину. Если оба входа имеют (скажем) 50 битов, но первые 40 битов идентичны, они будут отменены, и результат будет иметь только около 10 битов.
Итак, во-первых, вы, вероятно, хотите сделать всю математику с long long если это тот тип, который вы хотите получить в результате. Во-вторых, вы можете хотя бы подумать о перестановке (a-b)/c в a/c-b/c задержать вычитание как можно дольше.
Другие решения
Если вы знаете, что оба значения положительные, вы можете вычислить ceil в чисто целочисленном (или длинном длинном) с помощью:
(x + y-1)/y
Итак, в вашем случае:
(a - b + c-1)/c
Работа с отрицательными числами оставлена читателю как упражнение (может быть немного сложно решить, что именно вы хотите от него делать, и вам это обычно не нужно).