C ++中长整数除法的上限

Question

我试图解决一些涉及大数除法的问题。我偶然发现某些情况下我使用以下方法得到了错误的结果：

LL result = (LL)ceil((double)(a-b)/c)，其中a,b,c为long long integers(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.
那么是什么导致了这个错误？

我在 C++14 模式下使用 GCC 5.1（在 ideone.com 上）。

Answer 1

虽然它可以存储更大量级的数字，但double的典型实现只能保持大约 15-16 位精度。

浮点数减法也可能是个问题，尤其是当两个数字的大小几乎相同时。如果两个输入都是（比如）50 位，但前 40 位相同，则它们将抵消，结果将只有大约 10 位。

因此，首先，如果这是您想要的结果类型，您可能希望使用 long long 进行所有数学运算。其次，您可能至少要考虑将 (a-b)/c 重新排列为 a/c-b/c 以尽可能延迟减法。

Answer 2

如果你知道两个值都是正数，你可以用纯整数（或 long long）计算 ceil：

    (x + y-1)/y

所以，在你的情况下：

    (a - b + c-1)/c

处理负数留作 reader 的练习（决定你想要它做什么可能有点繁琐，而且你通常不需要它）。

C ++中长整数除法的上限

Ceiling of Long Integer division in c++

c++

integer

ceil

long-integer