加速大整数的“进制转换”

Question

我将使用一种进制转换算法，从一个大整数中（分成32位字）生成一个排列。

我使用的是相对标准的算法：

/* N = count,K is permutation index (0..N!-1) A[N] contains 0..N-1 */
i = 0;
while (N > 1) {
   swap A[i] and A[i+(k%N)]
   k = k / N
   N = N - 1
   i = i + 1
}

很不幸，每次迭代都会累加除法和取模运算，特别是在处理大整数时。但是，看起来我可以使用乘法！

/* As before, N is count, K is index, A[N] contains 0..N-1 */
/* Split is arbitrarily 128 (bits), for my current choice of N */
/* "Adjust" is precalculated: (1 << Split)/(N!) */
a = k*Adjust; /* a can be treated as a fixed point fraction */
i = 0;
while (N > 1) {
   a = a*N;  
   index = a >> Split;         
   a = a & ((1 << Split) - 1);  /* actually, just zeroing a register */       
   swap A[i] and A[i+index]
   N = N - 1
   i = i + 1
}

这很好，但是进行大整数乘法仍然很慢。

问题1：
有没有更快的方法？

例如。由于我知道N*(N-1)小于2^32，我可以从一个字中取出这些数字，并合并“剩余部分”吗？
或者，是否有一种修改算术解码器以逐个提取索引的方法？

问题2：
出于好奇，如果我使用乘法将数字转换为十进制而不进行调整，则结果将乘以(10^digits/2^shift)。是否有一种巧妙的方法来处理十进制数字而不需要这个因子？即使考虑了调整因子，这似乎也会更快--为什么标准库不使用这种方法而使用除法和取模？

- Lucky Fruit

---

我无法理解你的第二个算法。 - President James K. Polk

@GregS - 请告诉我您是否认为存在问题 - 理论是使用乘法/掩码从左侧（msb）移除值，而使用模数/除法从右侧（lsb）移除值。 - Lucky Fruit

Answer 1

看到你提到了2^128/(N!)这样的数字，似乎在你的问题中N将会是相当小的（根据我的计算，N<35）。 我建议以原始算法为起点，首先改变循环的方向：

i = 2;
while (i < N) {
    swap A[N - 1 - i] and A[N - i + k % i]
       k = k / i
       i = i + 1
}

现在将循环更改为每次迭代执行多个排列。我猜除法的速度与数字i无关，只要i<2^32即可。
将范围2...N-1拆分成子范围，使得每个子范围中的数字乘积小于2^32：

2, 3, 4, ..., 12: product is 479001600
13, 14, ..., 19:  product is 253955520
20, 21, ..., 26:  product is 3315312000
27, 28, ..., 32:  product is 652458240
33, 34, 35:       product is 39270

然后，不要通过i来除以乘积，而是通过长数字k来除以它们。每次迭代都会产生一个余数（小于2^32）和一个更小的数字k。当你有了余数之后，可以在内部循环中使用原始算法来处理它；现在速度更快，因为它不涉及长除法。
以下是一些代码：

static const int rangeCount = 5;
static const int rangeLimit[rangeCount] = {13, 20, 27, 33, 36};
static uint32_t rangeProduct[rangeCount] = {
    479001600,
    253955520,
    3315312000,
    652458240,
    39270
};

for (int rangeIndex = 0; rangeIndex < rangeCount; ++rangeIndex)
{
    // The following two lines involve long division;
    // math libraries probably calculate both quotient and remainder
    // in one function call
    uint32_t rangeRemainder = k % rangeProduct[rangeIndex];
    k /= rangeProduct[rangeIndex];

    // A range starts where the previous range ended
    int rangeStart = (rangeIndex == 0) ? 2 : rangeLimit[rangeIndex - 1];

    // Iterate over range
    for (int i = rangeStart; i < rangeLimit[rangeIndex] && i < n; ++i)
    {
        // The following two lines involve a 32-bit division;
        // it produces both quotient and remainder in one Pentium instruction
        int remainder = rangeRemainder % i;
        rangeRemainder /= i;
        std::swap(permutation[n - 1 - i], permutation[n - i + remainder]);
    }
}

当然，这段代码可以扩展到超过128位。
另一个优化可能涉及从范围的乘积中提取2的幂；这可能通过使范围更长而稍微加速。不确定这是否值得（也许对于像N=1000这样的大值）。

- anatolyg

Answer 2

虽然我不太了解算法，但你使用的算法似乎相当简单，所以我不太清楚你如何优化算法。

您可以尝试以下替代方法：

• 使用汇编语言（ASM）- 根据我的经验，在长时间尝试弄清楚某个算法应该如何在ASM中编写后，最终生成的版本比编译器生成的版本慢:) 可能是因为编译器也知道如何布局代码，使CPU缓存更有效，或者哪些指令实际上更快以及什么情况（这是在GCC / linux上）。
• 使用多处理：
  • 将您的算法变成多线程，并确保您使用与可用CPU核心数量相同的线程数运行（现在大多数CPU都具有多个核心/多线程）
  • 使您的算法能够在网络上的多台计算机上运行，并设计一种发送这些数字到网络中的计算机的方法，以便您可以利用它们的CPU功率。

- Quamis

---

-1，因为这些建议都不是好的建议——第一个建议对于任何性能问题都很少是好的建议，而尽管第二个建议是好的建议，但似乎并不适用于这个问题。当然，如果您能提出如何并行化的建议，我很乐意撤回我的投票。 - Tom Anderson

1: 自定义汇编语言实际上很好，但前提是你知道你在做什么，并且可移植性不是真正的问题（如果它将始终在特定硬件上运行）。 2: 我假设这个算法被大量调用，在一个类似于for的循环中，否则速度并不重要。在这种情况下，循环可以分成较小的部分并并行运行。 - Quamis