由运行时常量值重复整数除

Question

在我的程序中的某个时刻,我计算整数除数d.从那时起d,这将是不变的.

稍后在代码中我将除以它d几次 - 执行整数除法,因为值d不是编译时已知常量.

鉴于与其他类型的整数运算相比,整数除法是一个相对较慢的过程,我想优化它.我可以存储一些替代格式d,以便分割过程执行得更快吗？也许是某种形式的倒数？

我不需要d其他任何东西的价值.

值d是任何64位整数,但通常很适合32位.

Answer 1

这个libdivide有一个库:

libdivide是一个用于优化整数除法的开源库

libdivide允许您使用相对便宜的乘法和位移来替换昂贵的整数除法.编译器通常会这样做,但只有在编译时才知道除数.libdivide允许您在运行时利用它.结果是整数除法可以变得更快 - 更快.此外,libdivide允许您将SSE2向量除以运行时常量,这特别好,因为SSE2没有整数除法指令!

libdivide是免费的开源许可证.名称"libdivide"有点儿玩笑,因为本身没有库:代码完全打包为单个头文件,同时包含C和C++ API.

你可以在这个博客上阅读它背后的算法; 例如,这个条目.

基本上,它背后的算法与编译器用于通过常量优化除法的算法相同,除了它允许在运行时完成这些强度降低优化.

注意:您可以创建更快的libdivide版本.这个想法是,对于每个除数,你总是可以创建一个三元组(mul/ add/ shift),所以这个表达式给出了结果:(num*mul+ add)>> shift(乘法是这里的宽乘法).有趣的是,这种方法可以击败编译器版本,以便对几个微基准测试进行持续划分!

这是我的实现(这不是开箱即用的可编译,但可以看到一般算法):

struct Divider_u32 {
    u32 mul;
    u32 add;
    s32 shift;

    void set(u32 divider);
};

void Divider_u32::set(u32 divider) {
    s32 l = indexOfMostSignificantBit(divider);
    if (divider&(divider-1)) {
        u64 m = static_cast<u64>(1)<<(l+32);
        mul = static_cast<u32>(m/divider);

        u32 rem = static_cast<u32>(m)-mul*divider;
        u32 e = divider-rem;

        if (e<static_cast<u32>(1)<<l) {
            mul++;
            add = 0;
        } else {
            add = mul;
        }
        shift = l;
    } else {
        if (divider==1) {
            mul = 0xffffffff;
            add = 0xffffffff;
            shift = 0;
        } else {
            mul = 0x80000000;
            add = 0;
            shift = l-1;
        }
    }
}

u32 operator/(u32 v, const Divider_u32 &div) {
    u32 t = static_cast<u32>((static_cast<u64>(v)*div.mul+div.add)>>32)>>div.shift;

    return t;
}

Answer 2

"Hacker's delight"这本书有"第10章:整数除以常数",共74页.您可以在此目录中免费找到所有代码示例:http: //www.hackersdelight.org/hdcode.htm 在您的情况下,图.10-1.,10-2和10-3是你想要的.

除以常数d的问题相当于多次乘以c = 1/d.这些算法为您计算这样的常数.一旦你有c,你计算股息就是这样:

int divideByMyConstant(int dividend){
  int c = MAGIC; // Given by the algorithm

  // since 1/d < 1, c is actually (1<<k)/d to fit nicely ina 32 bit int
  int k = MAGIC_SHIFT; //Also given by the algorithm

  long long tmp = (long long)dividend * c; // use 64 bit to hold all the precision...

  tmp >>= k; // Manual floating point number =)

  return (int)tmp;
}