Modulo algorithm with byte array and 8 bit integer: 8bit = bytes % 8bit

algorithm, c, modulo

Solution

You can use a variation on Horner's method. Process a byte by byte with this formula: `a % b = ((a // 256) % b) * (256 % b) + (a % 256) % b`, where x // y is the rounding division (normal C integer division). The reason this will work is that congruence modulo b is an equivalence relation. With this you have an `O(length)` algorithm, or `O(log(a))`. Example snippet (untested, my C skills are rusty):

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

Some justification: `a = (a // 256) * 256 + (a % 256)`, therefore `a % b = ((a // 256) * 256) % b + ((a % 256) % b)`. However `a % 256 = a[n-1]` and `a // 256 = a[0 .. n-2]`. Reversing the actions in a way similar to Horner's rule gives you the presented snippet.

Problem

I need to create an algorithm implemented in C that do modulo arithmetic between an arbitrary number of bytes and one byte. See this: ``` typedef struct{ u_int8_t * data; u_int16_t length; }UBigInt; u_int8_t UBigIntModuloWithUInt8(UBigInt a,u_int8_t b){ } ``` For powers of two a & (b-1) can be used but what about non powers of two? I realise one method is: a - b*(a/b) That would require to use UBigIntDivisionWithUInt8 and UBigIntMultiplicationWithUInt8 and UBigIntSubtractionWithUBigInt. There might be a more efficient way to do this? Thank you. This is the implementation I now have: ``` 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; } ```

Original source