Popovici Sebi Popovici Sebi - 3 months ago 14
C Question

Does anyone know a better way for modulo on bits?

I have 2 big numbers, one about 4096 bits and the other 2048 bits, stored in a structure:

typedef uint32_t word;
typedef struct BigNumber {
word words[128];
} BigNumber;

I have to make the modulo of those and only way I can think to do it is subtract multiple times, but this take some time.

Does any one know a better way to do this?


Code based on @caf with my correction. Leave OP to code the 4 helper functions.

void BigNumber_Shift_Right(BigNumber *x);
void BigNumber_Shift_Left(BigNumber *x);
int BigNumber_Compare(const BigNumber *a, const BigNumber *b);
void BigNumber_SubtractEqual(BigNumber *a, const BigNumber *b);

void BigNumber_ModHalfSizeEqual(BigNumber *A, const BigNumber *B) {
  BigNumber X = *B;
  BigNumber AHalf = *A;

  while (BigNumber_Compare(&X, &AHalf) <= 0) {

  while (BigNumber_Compare(A, B) >= 0) {
    if (BigNumber_Compare(A, &X) >= 0) {
      BigNumber_SubtractEqual(A, &X); 

  // mod is in A