バイト配列と8ビット整数を持つモジュロアルゴリズム：8bit = bytes％8bit

Question

任意のバイト数と1バイトの間でモジュロ演算を行うCで実装されたアルゴリズムを作成する必要があります。 2のべき乗の場合

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

} 

&（B-1）を使用することができますが、どのような2のべき乗以外について：これを参照してください？

私は1つの方法は実現： - UBigIntDivisionWithUInt8とUBigIntMultiplicationWithUInt8とUBigIntSubtractionWithUBigIntを使用するために必要となるのb *（A/B）

。これを行うより効率的な方法がありますか？

ありがとうございます。

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; 
} 

Answer 1

あなたはホーナー法のバリエーションを使用することができます。

これは私が今持っている実装です。
この式でバイトごとに処理します。
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のルールに似た方法でアクションを逆にすると、提示されたスニペットが得られます。