通过乘法生成查找table除以10位整数

Question

我有一个整数，它是 256 和 131072 之间的 256 的倍数我想将它除以 1 到 1024

之间的整数

这是我代码内部循环中的一个热点，对其进行注释可显着加快我的应用程序速度。

我能否进行大小为 1024 的查找 table，这将有助于在比 x86_64 cpu 上的实际除法更短的时间内将除法转换为 "multiplication plus shift"？

有人可以帮忙想出代码来生成查找 table 以允许除以这 1024 个可能的除数之一吗？

我很想看到一种模板元编程方式来生成相关 table 作为 constexpr。

Answer 1

由于股息和除数的选择非常有限，因此可以使用一种比您找到的 Torbjörn Granlund 和 Peter Montgomery 在 paper 中使用的方法更简单的方法。我不精通 C++ 模板元编程，但我可以演示生成和使用 table 适当缩放倒数的方法。

首先我们注意到被除数都是 256 的倍数，因此可以通过简单的预右移 8 位将它们减少到 1 ... 0x200。由于我们不希望在减少的被除数与比例倒数相乘期间溢出无符号 32 位整数，因此理想情况下，倒数被缩放到 0x00200000 < rcp <= 0x00400000 范围内。

如果有快速计数前导零指令可用，它可用于在 table 预计算期间将向上倒数缩放到此范围内，基于在除数的以 2 为底的对数上，然后在运行时间使用相同的动态计算的比例因子来按比例向下减少股息和比例倒数的乘积因素。当放大倒数时，我们需要将结果四舍五入 up 到下一个整数，以补偿通过右移缩小的 t运行cating 性质。下面代码中的变体 0 使用这种方法。

没有快速计数前导零指令怎么办？我们需要用足够多的位数来存储缩放后的倒数，以保持计算的准确性。事实证明，由于对除数范围的严格限制，我们在这里很幸运，并且可以只用两个不同的比例因子来凑合，这两个比例因子可以很容易地从运行时间的除数计算出来：一个因子 <= 32 , 另一个是 (32, 1024) 中的除数。这用于代码的变体 1，其中两个比例因子计算为 2¹⁴ 和 2¹⁹.

最后，我们可能不想即时计算比例因子，而是将其与比例倒数一起存储，方法是使用每个 table 条目的最高有效位来存储它们，而较少的有效位用于倒数本身。一个缺点是需要额外的操作来从 table 条目中提取比例倒数和比例因子，这使得这种方法比其他两种方法更不 suitable 。这显示在下面的代码变体 2 中。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

#define VARIANT 0  // variants available: 0 ... 2

extern int __clz (uint32_t x); // intrinsic for access to CLZ instruction

uint32_t rcp [1025]; // table of scaled reciprocals (& possibly scale factors)

#define PRE_SCALE     (8)  // downscaling for dividends, since multiples of 256
#define POST_SCALE_1 (14)  // upscale factor #1 for reciprocals
#define POST_SCALE_2 (19)  // upscale factor #2 for reciprocals
#define RECIP_BITS   (24)  // bits used in table entry for scaled reciprocal

// helper function: logarithm base-2 of an 32-bit integer    
int ilog2 (uint32_t x)
{
    return 31 - __clz (x);
}

// division for dividends n*256, n in [1,512], divisor in [1,1024]    
uint32_t fast_div (uint32_t dividend, uint32_t divisor)
{
#if VARIANT == 0
    uint32_t scale = POST_SCALE_1 + ilog2 (divisor);
    return ((dividend >> PRE_SCALE) * rcp[divisor]) >> scale;
#elif VARIANT == 1
    uint32_t scale = (divisor > 0x20) ? POST_SCALE_2 : POST_SCALE_1;
    return ((dividend >> PRE_SCALE) * rcp[divisor]) >> scale;
#elif VARIANT == 2
    uint32_t scale = rcp[divisor] >> RECIP_BITS;
    return ((dividend >> PRE_SCALE) * (rcp[divisor] & ((1 << RECIP_BITS) - 1))) >> scale;
#else
#error non-existing VARIANT
#endif
}

int main (void)
{
    uint32_t dividend, divisor, res, ref;
    int i;

    // precompute table of recprocals
    for (i = 1; i < 1025; i++) {
#if VARIANT == 0
        uint32_t scale = POST_SCALE_1 + ilog2 (i);
        rcp[i] = ((uint32_t)(pow (2.0, PRE_SCALE + scale) / i + 0.99999));
#elif VARIANT == 1
        uint32_t scale = (i > 0x20) ? POST_SCALE_2 : POST_SCALE_1;
        rcp[i] = ((uint32_t)(pow (2.0, PRE_SCALE + scale) / i + 0.99999));
#elif VARIANT == 2
        uint32_t scale = (i > 0x20) ? POST_SCALE_2 : POST_SCALE_1;
        rcp[i] = ((uint32_t)(pow (2.0, PRE_SCALE + scale) / i + 0.99999) +
                  (scale << RECIP_BITS));
#else
#error non-existing VARIANT
#endif
    }

    // test all supported dividens and divisors exhaustively
    divisor = 1;
    while (divisor <= 1024) {
        dividend = 256;
        while (dividend <= 131072) {
            res = fast_div (dividend, divisor);
            ref = dividend / divisor;
            if (res != ref) {
                printf ("n=%08x  d=%08x  res=%08x  ref=%08x  rcp=%08x\n", 
                        dividend, divisor, res, ref, rcp[divisor]);
                return EXIT_FAILURE;
            }
            dividend += 256;
        }
        divisor++;
    }
    printf ("division test passed\n");
    return EXIT_SUCCESS;
}

通过乘法生成查找table除以10位整数

Generate a lookup table to divide by a 10 bit integer through multiplication

template-meta-programming

lookup-tables

integer-division