2

Edited:

I have a big number that C does not have a type for it natively. I have to use a char array to hold it. As an example, I create a 32-byte array. It represents a large number up to 2 ^ 256.

unsigned char num[32]; // The size could be any number for this question.

I want to apply modulo operation on it, for example, I want to mod the big number by a small divisor and get an integer type result.

int divisor = 1234; // Note that the divisor is much smaller than the big number
int result;

// do something here
// to produce a result
// like result = number mod divisor

I do not want to use other library. How can I do it?

Luke
  • 281
  • 2
  • 7
  • 19
  • 3
    Said like this, it has little sense. What do you expect in result? – rocambille Jul 25 '16 at 15:25
  • and there are many ways...do you want to know how to convert a _string_ to an integer? – Sourav Ghosh Jul 25 '16 at 15:26
  • 2
    I suspect this is a question about implementing the `%` operation in arbitrary-precision arithmetic without using a library meant for that purpose –  Jul 25 '16 at 15:26
  • I want to treat the char array as a big number and apply modulo. – Luke Jul 25 '16 at 15:27
  • If you're asking how to treat `hash` as one large number and perform modulo by `length`, you either need a bigint library such as `gmp` or you need to do long division by hand in your code. – dbush Jul 25 '16 at 15:27
  • 3
    Your first job: use `unsigned char` instead. `char` could be signed 1's complement. That will completely mess things up. – Bathsheba Jul 25 '16 at 15:30
  • So you want to write a bignum mod function... related question: http://stackoverflow.com/questions/10522379/bignum-division-with-an-unsigned-8-bit-integer-c also this one: http://stackoverflow.com/questions/3199727/how-to-implement-long-division-for-enormous-numbers-bignums –  Jul 25 '16 at 15:30
  • @chux b is actually much smaller than a. – Luke Jul 25 '16 at 16:10
  • Don't break your fingers on the downvote button, fellows. – Armen Michaeli Jul 25 '16 at 16:18

1 Answers1

5

To perform mod an a large number, use mod one unsigned char (@Bathsheba) at a time.

% is C's remainder operator. For positive operands it has the same functionality as mod.

unsigned mod_big(const unsigned char *num, size_t size, unsigned divisor) {
  unsigned rem = 0;
  // Assume num[0] is the most significant
  while (size-- > 0) {
    // Use math done at a width wider than `divisor`
    rem = ((UCHAR_MAX + 1ULL)*rem + *num) % divisor;
    num++;
  }
  return rem;
}
Community
  • 1
  • 1
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256