最有效的方法來評估一個二進制標產品模2

我目前執行傅立葉變換的一些物理問題，我的算法的一個巨大的瓶頸來自於標產品模2最有效的方法來評估一個二進制標產品模2

對於一個給定的評價整數N，我必須用二進制表示所有數字，最多2^N-1。（例如15 = 2^3 + 2^2 + 2 + 2^0 =（1,1,1,1,0，...，0,1,2） 0））我必須評估它的標量乘以0到2^N-1的二進制數形式的模數2.

（例如，標量乘積1.15 =（1,0,0，... ，0）。（1,1,1,1,0，...，0）= 1 * 1 + 1 * 0 + ... = 1 mod 2）

請注意，組件保持二進制（1,1）= 1 * 1 + 1 * 1而不是1 * 1 + 2 * 2

這基本上是2 ^（2N）的標量積，我必須執行和減少模2

我有困難獲得超過N = 18。

我想知道是否一些巧妙的數學訣竅可以用來大大減少花在做它們上的時間。

我正在考慮某種遞歸（即在文件中保存N的結果並推導N + 1的結果），但我不確定這會有所幫助。事實上，通過這種遞歸，知道N的結果，我可以將N + 1的矢量對應於N部分加上一個附加數字，然後在每個標量乘積上剪切，而不是評估標量乘積，我不得不告訴我的電腦去讀大文件（因爲我可能無法將它全部保存在動態存儲器中），這可能比較耗時，可能比我必須爲每個產品執行的約20次乘法運算。

是否有任何已知的優化的數理論算法允許非常快速地評估這樣的標量乘積模2？有沒有我不知道我可以利用的規則或想法？

對不起，糟糕的格式，我只是無法讓LateX在這裏工作。

來源

2017-04-08 Evariste

您可以只計算[按位與]（https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#and（java.math.BigInteger））的這兩個數字，然後檢查奇偶性（見，如果[數的1比特]（https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#bitCount（））很奇怪）。 – kennytm

他們是如何使用的，也許評估的數量也可以減少？你是否只想要高層次的建議或針對特定體系結構的實施策略（哪些？）？ Btw乳膠沒有在SO上啓用。 – harold

* N *有最大值嗎？ – trincot

對應的比特的乘積的總和，模2，將等於1個比特的兩個數的和數目，模2

，你可以得到一個數的二進制表示很容易，實際上可能不需要爲它們創建一個位數組，但只需在編程語言中使用整數數據類型，該數據類型允許至少32位。許多語言都提供位操作符，如AND（&）和XOR（^）。

通過variable-precision SWAR algorithm可以計算數字中的1位。

這裏是Python程序，計算該產品模2 2號：

def numberOfSetBits(i): 
    i = i - ((i >> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 

def product(a, b): 
    return numberOfSetBits(a & b) % 2

，而不是與numberOfSetBits計數位，你可以在位連同異或摺疊，第16個最顯著具有16個最低有效位的位，然後導致8個最高有效位和8個最低有效位，直到你剩下一位。再次在Python：

def bitParity(i): 
    i = (i >> 16)^i 
    i = (i >> 8)^i 
    i = (i >> 4)^i 
    i = (i >> 2)^i 
    i = (i >> 1)^i 
    return i % 2 

def product(a, b): 
    return bitParity(a & b)

來源

2017-04-08 21:24:23 trincot

對不起，我猜我還不夠清楚，我會進一步編輯：mod 2適用於以二進制形式保存的組件的總和！（即15.5 =（1,1,1,1,0，..）*（1,1,0，...）= 1 + 1 = 2 = 0 mod 2） – Evariste

請您寫出完整的「產品「（這顯然是一筆款項）？爲什麼是1 + 1？ – trincot

我試圖實現的是從常規整數獲得矢量的標量積。例如，對於15，我得到（1,1,1,1,0 ...），就是這樣。我從不改回十進制。然後，我使用通常的點乘積規則x1 * x1 + x2 * x2 + ...，其中x1，x2，... = 0或1總是，然後我減少了mod 2，所以1.15 = 1 * 1 + 0 * 1 + 0 * 1 + 0 * 1 + 0 * 0 + ... + 0 * 0 = 1 = 1 mod 2 – Evariste

如果更改您正在評估這些對的順序（大小的矩陣2 ^Ñ×2 ^Ñ），那麼就可以有效地找出哪些產品-MOD-2在您的評估的每一行中更改。

使用Gray code，您可以按照特殊順序遍歷每個值0 ... 2 ⁿ -1，其中每次外部循環值只有1位發生更改。你可以存儲1位從0每個值... 2 ^ň -1較前行的產品-MOD-2的值，然後改變它的基礎上不斷變化的位是否有任何影響，它只做當另一個（內部循環）數中的對應位是1（如果它是0，那麼無論其他位的值如何，二進制AND都將爲0）。

在C：

int N = 5; 
int max = (1 << N) - 1; 
unsigned char* prev = calloc((1 << N)/8, 1); 

// for the first row all the products will be zero, so start at row 1 
for(int a = 1; a <= max; a++) 
{ 
    int grey = a^(a >> 1); // compute the grey code 
    int prev_grey = (a - 1)^((a - 1) >> 1); 
    int changed_bit = grey^prev_grey; 

    for(int b = 0; b <= max; b++) 
    { 
     // the product will be changed only if b has a 1 at the same place 
     // (otherwise it will be 0 regardless) 
     if(b & changed_bit) 
     { 
      prev[b >> 3] ^= (1 << (b & 7)); 
     } 
     int mod = (prev[b >> 3] & (1 << (b & 7))) != 0; 
     printf("mod value of %d and %d is %d\n", grey, b, mod); 
    } 
}

內環可以更進行優化，因爲可以很容易地找出哪些B的值具有在變更後的比特的位置的非零值：例如，如果它是在位置10，那麼在一行0和1之間將會有1024的運行等等。所以你知道你有1024個值，其中product-mod-2與前一行中的值相同等等。不清楚我是否這可以幫助你，因爲我不知道你在用這些產品做什麼。

內循環也可以展開（例如32或64次），以便每次不讀寫數組，而是每次處理32或64位數據塊。

來源

2017-04-08 23:07:11 samgak

最有效的方法來評估一個二進制標產品模2

回答

相關問題