2

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?

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
Popovici Sebi
  • 258
  • 3
  • 13
  • 4
    https://gmplib.org/ – David Ranieri Aug 30 '16 at 09:54
  • Unfortunately I can not use MGP library , and their code is not really reusable for me – Popovici Sebi Aug 30 '16 at 10:13
  • Is it about arbitrary number modulo or module with some power 2 number (set higher bits to zero)? – grek40 Aug 30 '16 at 10:26
  • @grek40 arbitrary , it is no special rule except the length – Popovici Sebi Aug 30 '16 at 10:27
  • @ZangMingJie: not really a duplicate. This is a 128*32 = 4096 bit integer. But the same principles apply, indeed. – Rudy Velthuis Aug 30 '16 at 15:07
  • The question is unclear. So one number is type `BigNumber`, the "one about 4096 bits". The other number " the other 2048 bits" is of what type? Is the modulo " one about 4096 bits" modulo "the other 2048 bits" or visa-versa? Posting what you have done rather than musing "only way I can think to do it is subtract multiple times" would add clarity. Detailing about timing goals would help too. – chux - Reinstate Monica Aug 30 '16 at 15:48
  • @chux number A is 4096 bits (type BigNumber) , number B 2048 bits (type is also BigNumber to be easier at operations ["2048Xzero " and the actual number]) , I need to calculate A%B , what I already made is : "while (A>B) A=A-B " , and I am looking for something like a scheme to increase my eficiency – Popovici Sebi Aug 31 '16 at 06:32

3 Answers3

2

To calculate m % n:

modulus(m, n) {
  if (m < n) return m
  elif (m < (n<<1)) return m - n
  else return modulus((modulus(m>>1, n)<<1 + m&1), n)
}
Zang MingJie
  • 5,164
  • 1
  • 14
  • 27
2

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;
  BigNumber_Shift_Right(&AHalf);

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

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

  // mod is in A
}
Community
  • 1
  • 1
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

You can divide a by b and get a whole number x. Now subtract x from a and you get the modulus. With arbitrary divisors you won't get around the division. For big divisors this might be faster than multiple subtractions, but divisions are still expensive.

You may also have to implement the divison algorithm manually for such big numbers. There is one out there, which results in qoutient and remainder (modulus) at the same time, but i cannot recall its name now.

Chris Tophski
  • 930
  • 1
  • 6
  • 23