加速大整数的"基本转换"

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,我可以从一个单词中提取这些数字,并合并到"剩余"中吗？
或者,有没有办法修改一个arithetic解码器,一次拉出一个指标？

问题2:
为了好奇 - 如果我使用乘法将数字转换为基数10而不进行调整,则结果乘以(10 ^位数/ 2 ^移位).是否有一种棘手的方法来删除使用十进制数字的这个因素？即使有调整因子,这似乎会更快 - 为什么标准库不会使用这个vs divide和mod？

Answer 1

不了解算法，但你使用的算法看起来很简单，所以我真的不知道如何优化算法。

您可以使用替代方法：

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