帶字節數組和8位整數的模算法：8位=字節％8位

我需要創建一個在C中實現的算法，可以在任意數量的字節和一個字節之間進行模運算。看到這一點：帶字節數組和8位整數的模算法：8位=字節％8位

typedef struct{ 
    u_int8_t * data; 
    u_int16_t length; 
}UBigInt; 
u_int8_t UBigIntModuloWithUInt8(UBigInt a,u_int8_t b){ 

}

對於兩個大國一個&（B-1）可以使用，但怎麼樣的兩個非權力？

我認識一個方法是：A - B *（A/B）

這將需要使用UBigIntDivisionWithUInt8和UBigIntMultiplicationWithUInt8和UBigIntSubtractionWithUBigInt。可能有更有效的方法來做到這一點？

謝謝。

這是我現在已經實現：

u_int8_t UBigIntModuloWithUInt8(UBigInt a,u_int8_t b){ 
    if (!(b & (b - 1))) 
     return a.data[a.length - 1] & b - 1; // For powers of two this can be done 
    // Wasn't a power of two. 
    u_int16_t result = 0; // Prevents overflow in calculations 
    for(int x = 0; x < a.length; x++) { 
     result *= (256 % b); 
     result %= b; 
     result += a.data[x] % b; 
     result %= b; 
    } 
    return result; 
}

來源

2012-05-03 Matthew Mitchell

你說'a'是任意字節數;如果你有什麼話可以說b？它是不變的？如果是的話有什麼價值 – violet313

我想'b'是一個任意的8位（無符號？）整數。 –

b可能是1-255。我需要執行它58，但可能會有更多的情況。如果有58個專門優化的解決方案，那麼這將是很好的，但我可能需要爲任何實現它。 –

您可以使用Horner的方法的變化。
用此公式處理一個字節：
a % b = ((a // 256) % b) * (256 % b) + (a % 256) % b，其中x // y是舍入除法（標準C整數除法）。這將起作用的原因是同餘模b是一個等價關係。
有了這個，你有一個O(length)算法，或O(log(a))。
實施例片斷（未經測試，我的C技能是生鏽）：

u_int16_t result = 0; // Just in case, to prevent overflow 
for(i = 0, i<a.length; i++) { 
    result *= (256 % b); 
    result %= b; 
    result += (a[i] % b); 
    result %= b; 
}

一些理由： a = (a // 256) * 256 + (a % 256)，因此 a % b = ((a // 256) * 256) % b + ((a % 256) % b)。但是a % 256 = a[n-1]和a // 256 = a[0 .. n-2]。以類似Horner規則的方式反轉這些動作會給你提供的片段。

來源

2012-05-04 00:54:55

我不知道它是如何工作的，但從單個測試來看似乎是這樣。將實施它並測試並回饋給你。謝謝。 –

天才！有用。這很棒。 :-) –

謝謝，我用Python測試了它（本機支持任意大小的整數）：http://codepad.org/Eo00RNEJ騎車2分鐘後似乎沒有給出任何錯誤，所以我猜對了;）請注意，我沒有覆蓋除零。 –

帶字節數組和8位整數的模算法：8位=字節％8位

回答

相關問題