4

我需要创建一个用 C 实现的算法，该算法在任意数量的字节和一个字节之间进行模运算。看到这个：

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

}

对于 2 的幂，可以使用 a & (b-1)，但是非 2 的幂呢？

我意识到一种方法是：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;
}
4

1 回答 1

6

您可以使用霍纳方法的变体。
使用以下公式逐字节处理：
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]。以类似于霍纳规则的方式反转动作会给你呈现的片段。

于 2012-05-04T00:54:55.437 回答