4

任意のバイト数と1バイトの間でモジュロ演算を行う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の累乗以外の場合はどうでしょうか。

私は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;
}
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 に答える