将整数乘以适当分数的快速方法，没有浮点数或溢出

Question

我的程序经常需要执行以下计算：

鉴于：

N 是一个 32 位整数
D 是一个 32 位整数
绝对值（N）<=绝对值（D）
D != 0
X 是任意值的 32 位整数

查找：

X * N / D 作为 X 缩放为 N/D 的四舍五入整数（即 10 * 2 / 3 = 7）

显然我可以直接使用 r=x*n/d，但我经常会从 x*n 中溢出。如果我改为 r=x*(n/d) 那么我只会得到 0 或 x 由于整数除法会丢弃小数部分。然后是 r=x*(float(n)/d) 但在这种情况下我不能使用浮点数。

准确性会很好，但不如速度那么重要，并且是一个确定性函数（在给定相同输入的情况下总是返回相同的值）。

N 和 D 目前已签名，但如果有帮助，我可以解决它们始终未签名的问题。

适用于 X 的任何值（以及 N 和 D，只要 N <= D）的通用函数是理想的，因为此操作以各种不同的方式使用，但我也有一个特定的情况，其中值X 是已知的 2 的常数次方（准确地说是 2048），只是加快特定调用的速度将是一个很大的帮助。

目前我正在使用 64 位乘法和除法来避免溢出（本质上是 int multByProperFraction(int x, int n, int d) { return (__int64)x * n / d; } 但有一些断言和额外的位摆弄以进行舍入而不是截断）。

不幸的是，我的分析器报告 64 位除法函数占用了太多空间 CPU（这是一个 32 位应用程序）。我试图减少我需要执行此计算的频率，但运行无法解决它，所以我试图找出一种更快的方法，如果可能的话。在 X 是常量 2048 的特定情况下，我使用位移位而不是乘法，但这并没有多大帮助。

Answer 1

基本的正确方法就是(uint64_t)x*n/d。假设 d 是可变且不可预测的，这是最佳的。但是，如果 d 是常量或不经常更改，您可以预先生成常量，以便 exact 除以 d 可以作为乘法和位移位执行。该算法的一个很好的描述，大致是 GCC 在内部使用的将常量除法转换为乘法的算法，在这里：

http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

我不确定让它适用于“64/32”除法（即除以 (uint64_t)x*n 的结果）有多容易，但你应该能够将它分解成高低部分如果没有别的。

请注意，这些算法也可用作 libdivide。

Answer 2

容忍不精确，使用n,d,x

的16位MSBit

Algorithm
while (|n| > 0xffff) n/2, sh++
while (|x| > 0xffff) x/2, sh++
while (|d| > 0xffff) d/2, sh--
r = n*x/d  // A 16x16 to 32 multiply followed by a 32/16-bit divide.
shift r by sh.

当 64 bit 除法很昂贵时，这里的 pre/post 处理可能值得进行 32 位除法 - 这肯定是 CPU 的大块。

如果无法诱导编译器执行 32-bit/16-bit 除法，则跳过 while (|d| > 0xffff) d/2, sh-- 步骤并执行 32/32 除法。

尽可能使用无符号数学。

Answer 3

我现在已经对几种可能的解决方案进行了基准测试，包括 weird/clever 来自其他来源的解决方案，例如组合 32 位 div & mod & 添加或使用农民数学，这里是我的结论：

首先，如果您只针对 Windows 并使用 VSC++，只需使用 MulDiv()。它非常快（比在我的测试中直接使用 64 位变量更快），同时仍然准确并为您四舍五入结果。我找不到任何更好的方法来使用 VSC++ 在 Windows 上做这种事情，即使考虑到像 unsigned-only 和 N <= D.

这样的限制

但是，在我的例子中，即使跨平台也具有确定性结果的函数比速度更重要。在我用作测试的另一个平台上，64 位 divide 在使用 32 位库时比 32 位慢得多，而且没有 MulDiv()使用。这个平台上的 64 位 divide 需要大约 26 倍于 32 位 divide 的时间（然而 64 位乘法与32 位版本...)。

所以如果你有像我这样的案例，我会分享我得到的最好的结果，结果证明只是对 chux 答案的优化。

我将在下面分享的两种方法都使用了以下函数（尽管特定于编译器的内在函数实际上仅在 Windows 中帮助提高了 MSVC 的速度）：

inline u32 bitsRequired(u32 val)
{
    #ifdef _MSC_VER
        DWORD r = 0;
        _BitScanReverse(&r, val | 1);
        return r+1;
    #elif defined(__GNUC__) || defined(__clang__)
        return 32 - __builtin_clz(val | 1);
    #else
        int r = 1;
        while (val >>= 1) ++r;
        return r;
    #endif
}

现在，如果 x 是一个大小为 16 位或更小的常量，并且您可以预先计算所需的位数，我发现此函数在速度和准确性方面的最佳结果：

u32 multConstByPropFrac(u32 x, u32 nMaxBits, u32 n, u32 d)
{
    //assert(nMaxBits == 32 - bitsRequired(x));
    //assert(n <= d);
    const int bitShift = bitsRequired(n) - nMaxBits;
    if( bitShift > 0 )
    {
        n >>= bitShift;
        d >>= bitShift;
    }

    // Remove the + d/2 part if don't need rounding
    return (x * n + d/2) / d;
}

在较慢的 64 位 divide 平台上，上述函数运行 ~16.75 倍是 return ((u64)x * n + d/2) / d; 的速度，平均为 99.999981%准确性（比较 return 值与 x 的运行ge 的差异，即当 x 为 2048 时与预期的 returning +/-1 将是 100 - (1/2048 * 100 ) = 99.95% 准确) 当用大约一百万个运行domized 输入进行测试时，其中大约一半通常是溢出。最坏情况下的准确率为 99.951172%。

对于一般用例，我从以下方面找到了最佳结果（并且无需限制 N <= D 即可启动！）：

u32 scaleToFraction(u32 x, u32 n, u32 d)
{
    u32 bits = bitsRequired(x);
    int bitShift = bits - 16;
    if( bitShift < 0 ) bitShift = 0;
    int sh = bitShift;
    x >>= bitShift;

    bits = bitsRequired(n);
    bitShift = bits - 16;
    if( bitShift < 0 ) bitShift = 0;
    sh += bitShift;
    n >>= bitShift;

    bits = bitsRequired(d);
    bitShift = bits - 16;
    if( bitShift < 0 ) bitShift = 0;
    sh -= bitShift;
    d >>= bitShift;

    // Remove the + d/2 part if don't need rounding
    u32 r = (x * n + d/2) / d;
    if( sh < 0 )
        r >>= (-sh);
    else //if( sh > 0 )
        r <<= sh;

    return r;
}

在具有较慢 64 位 divide 的平台上，上述函数运行 ~18.5 倍与使用 64 位变量一样快，并且具有 99.999426% 的平均值和99.947479% 的最坏情况准确度。

我能够通过改变移位来获得更快的速度或更高的准确性，例如如果不是绝对必要的话，我尽量不一直向下移位到 16 位，但速度的任何提高都是在准确性成本高，反之亦然。

None 我测试的其他方法甚至接近相同的速度或精度，大多数比仅使用 64 位方法慢或精度损失巨大，因此不值得研究。

显然，不保证运行其他人会在其他平台上获得类似的结果！

编辑： 用纯代码替换了一些乱七八糟的 hack，实际上让编译器完成它的工作运行更快。

将整数乘以适当分数的快速方法，没有浮点数或溢出

Fast method to multiply integer by proper fraction without floats or overflow

c++

math

bit-manipulation

integer-overflow

integer-division