How can I implement a modular operation with unsigned ints with limited hardware in C

Question

I have a machine that only supports 32-bit operations, it has not been working on this computer for a long time. I have one 64-bit quantity represented as two unsigned int 32. The question is how can I execute mod on this 64-bit quantity with a 32-bit divider.

r = a mod b

Where:

a is a 64-bit value, and b is a 32-bit value

I thought I could imagine part of the mod by doing: a = a1 * (2 ^ 32) + a2 (where a1 is the upper bits, a2 is the lower bits)

(a1 * (2 ^ 32) + a2) mod b = ((a1 * 2 ^ 32) mod b + a2 mod b) mod b

((a1 * 2 ^ 32) mod b + a2 mod b) mod b = (a1 mod b * 2 ^ 32 mod b + a2 mod b) mod b

but the problem is that 2 ^ 32 mod b can sometimes be equal to 2 ^ 32, and therefore the multiplication will overflow. I looked at trying to convert multiplication to complement, but it also requires me to use 2 ^ 32, which if my mod gave me 2 ^ 32 again :), so I'm not sure how to execute an unsigned mod of a 64-bit value with 32 bit.

I assume that a simple solution would be to perform the following operations:

• a / b = c

• a = a - floor (c) * b

• execute 1 until c is 0, and use a as your answer.

but I'm not sure how to combine these two integers together to form a 64-bit value

Just to be complete, here are some links for binary division and subtraction: http://www.exploringbinary.com/binary-division/

and description of the binary division algorithm: http://en.wikipedia.org/wiki/Division_algorithm

Answer 1

Works: Tested with 1000 M random combinations against 64-bit % .

Similar to the early division of high school a/b (but in base 2), subtract b from a , if possible, then shift by moving 64 times. Return the balance.

 #define MSBit 0x80000000L uint32_t mod32(uint32_t a1 /* MSHalf */, uint32_t a2 /* LSHalf */, uint32_t b) { uint32_t a = 0; for (int i = 31+32; i >= 0; i--) { if (a & MSBit) { // Note 1 a <<= 1; a -= b; } else { a <<= 1; } if (a1 & MSBit) a++; a1 <<= 1; if (a2 & MSBit) a1++; a2 <<= 1; if (a >= b) a -= b; } return a; } 

Note 1: This is the hidden part for 33-bit subtraction. Since the code knows that n has an MSBit set, 2*n will be larger than b , then n = 2*n - b . This is due to an unsigned wrapper.

---

[change]

Below is a generic modu() that works with any size of the array a and an unsigned integer of any size.

 #include <stdint.h> #include <limits.h> // Use any unpadded unsigned integer type #define UINT uint32_t #define BitSize (sizeof(UINT) * CHAR_BIT) #define MSBit ((UINT)1 << (BitSize - 1)) UINT modu(const UINT *aarray, size_t alen, UINT b) { UINT r = 0; while (alen-- > 0) { UINT a = aarray[alen]; for (int i = BitSize; i > 0; i--) { UINT previous = r; r <<= 1; if (a & MSBit) { r++; } a <<= 1; if ((previous & MSBit) || (r >= b)) { r -= b; } } } return r; } UINT modu2(UINT a1 /* MSHalf */, UINT a2 /* LSHalf */, UINT b) { UINT a[] = { a2, a1 }; // Least significant at index 0 return modu(a, sizeof a / sizeof a[0], b); } 

Answer 2

Do this the same way as a long separation with pencil and paper.

 #include <stdio.h> unsigned int numh = 0x12345678; unsigned int numl = 0x456789AB; unsigned int denom = 0x17234591; int main() { unsigned int numer, quotient, remain; numer = numh >> 16; quotient = numer / denom; remain = numer - quotient * denom; numer = (remain << 16) | (numh & 0xffff); quotient = numer / denom; remain = numer - quotient * denom; numer = (remain << 16) | (numl >> 16); quotient = numer / denom; remain = numer - quotient * denom; numer = (remain << 16) | (numl & 0xffff); quotient = numer / denom; remain = numer - quotient * denom; printf("%X\n", remain); return 0; }