大きい整数の「基底変換」のスピードアップ

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未満であることを知っているので、それらの数字を1つの単語から取り出し、残りの部分をマージできますか？
または、一度に1つずつインディペンデントを引き出すためのアーティチョークデコーダーを変更する方法はありますか？

質問2：好奇心の便宜上
- I変換する乗算を使用する場合、数は調整せずに10を底とするが、その結果は、（10 ^桁/ 2 ^シフト）が乗算されます。小数点を扱うこの要素を削除する手間のかかる方法はありますか？調整の要素があっても、これは速くなるように思えます。なぜ、標準ライブラリがこのvs divideとmodを使用しないのですか？

Answer 1

アルゴリズムについて知っていることはありませんが、使用するアルゴリズムはかなりシンプルなように見えるので、どのようにアルゴリズムを最適化するかは本当に分かりません。

あなたは別のアプローチを使用可能性があります

• 使用ASM（アセンブラ） - 私の経験から、特定のアルゴリズムがASMに書き込まれるべきか把握しようと、長い時間の後、それが遅くなることになったがおそらく、コンパイラは、CPUキャッシュがより効率的になるように、そして/またはどの命令が実際に高速でどのような状況（これはGCC/Linux上にあった）になるようにコードをレイアウトする方法も知っているからです。
• マルチプロセッシングを使用：
• （ほとんどのCPUのnowdaysは、複数のコア/マルチスレッドを持っている）あなたのアルゴリズムのマルチスレッドを作成し、使用可能なCPUコアの数とスレッドの数が同じで実行してくださいメイク
  • をネットワーク上の複数のマシン上で実行可能なアルゴリズムを使用し、これらの数値をネットワーク内のマシンに送信する方法を工夫して、CPUパワーを使用することができます。あなたは2^128 /（N！）のような数字について話していることを見て

Answer 2

、あなたの問題で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 
} 

ここで、ループを変更して繰り返しごとに複数の並べ替えを行います。私は分割の速度は、私が< 2^32である限り、番号iに関係なく同じであると思います。
範囲を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のような大きな値の場合）。