c++ - 64 位溢出数学转换

Question

我有一个要执行的转换:

uint64_t factor = 2345345345; // Actually calculated at runtime, but roughly this magnitude

uint64_t Convert(uint64_t num)
{
    return num * 1000ULL / factor;
}

对于最大的 num 值，乘法在除以 factor 之前换行。将顺序更改为 num/factor * 1000UL 会失去一些 Not Acceptable 准确性。

我想重写 Convert() 来处理所有可能的 num 值:

uint64_t Convert(uint64_t num)
{
    if(num > MAX_UINT64/1000ULL)       // pseudo code
    {
        // Not sure what to put here
    }
    else
    {
        return num * 1000ULL / factor;
    }
}

我们考虑过使用 128 位数学运算，但希望尽可能避免使用它。

实现 Convert() 的最有效方法是什么，以便它可以理想地处理最大的 num 可能并仍然产生正确的结果？

Answer 1

有点老派的数学，你可以使用%来计算剩余:

uint64_t Convert(uint64_t num)
{
    uint64_t m = 1000;
    uint64_t a = num / factor;
    uint64_t t = num % factor;
    uint64_t h = m * t / factor;

    return a * m + h;
}

例子:

uint64_t Convert2(uint64_t num)
{
    return num * 1000ULL / factor;
}

uint64_t Convert3(uint64_t num)
{
    return num / factor * 1000ULL;
}


int main()
{
    cout << Convert(std::numeric_limits<uint64_t>::max()) << endl;
    cout << Convert2(std::numeric_limits<uint64_t>::max()) << endl;
    cout << Convert3(std::numeric_limits<uint64_t>::max()) << endl;
}

输出:

7865257077400  <--- // The correct one //
7865257077     <--- // Value wrapped before multiplication // 
7865257077000  <--- // Low accuracy, loses remaining //