3

我有一个我正在尝试执行的转换：

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损失一些不可接受的准确性。

我想重写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尽可能多的情况并仍然产生正确的结果？

4

2 回答 2

3

一点老派数学，你可以用它%来计算余数：

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 //
于 2013-08-30T16:17:30.033 回答
1

分解你的部门：

r = 1000*(n/factor) + ((n%factor)*1000)/Factor

如果余数溢出（因子很大）但如果因子小于你就可以了，你仍然可能会遇到问题MAX_UINT64/1000。

于 2013-08-30T16:16:29.310 回答