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 に答える