大型整數加速「基本轉換」

我正在使用基本轉換算法從大整數（拆分爲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而不進行調整，則結果乘以（10^digit/2^shift）。是否有一個棘手的方法來消除這個因素與小數位？即使有調整因素，這看起來會更快 - 標準庫爲什麼不使用這個vs divide和mod？

來源

2010-11-25 Lucky Fruit

我無法理解你的第二個算法。 – 2010-11-25 13:16:08

@GregS - 請告訴我，如果您認爲存在問題 - 理論上它會使用乘法/面具從右側（msb）中去除值，而使用mod/divide去除右側（lsb）中的值。 – 2010-11-25 18:13:32

-1

不知道算法，但你使用的算法似乎很簡單，所以我真的不知道如何優化算法。

您可以使用替代方法：

使用ASM（彙編） - 從我的經驗，經過了很長時間試圖找出如何應該有一定的算法將在ASM來寫的，它最終被較慢比編譯器生成的版本:)可能是因爲編譯器也知道如何佈局代碼，所以CPU緩存會更有效率，和/或什麼樣的指令實際上更快，什麼情況下（這是在GCC/linux上）。
使用多處理：
- 讓你的算法多線程，並確保您有相同數量的線程可用的CPU內核數量的運行（大多數CPU的nowdays確實有多個核心/多線程）
- 化妝你的算法能夠在網絡上的多臺機器上運行，並設計一種將這些號碼發送給網絡中的機器的方法，因此你可以使用它們的CPU功率。

來源

2010-12-08 12:56:55 Quamis

看到你是（根據我的計算ñ< 35）談論號碼，如2^128 /（N！），似乎在你的問題N的將是相當小的。我建議以原始算法爲出發點;首先切換回路的方向：

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

現在改變循環來做每次迭代的幾個排列。我猜劃分的速度是一樣的，無論我的號碼是多少，只要我< 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的大數值，比如N = 1000）。

來源

2010-12-08 17:42:46 anatolyg

大型整數加速「基本轉換」

回答

相關問題