Skip to content
Learn Netverks
2

Modulus of Very large Number

asked 9 hours ago by @qa-mmhs8cnsuvjywhemgeq0 0 rep · 163 views

c algorithm numeric

You are given a very large number N (which goes upto 1e10000)
and a 64 bit integer P.
How do i find N % P?
for example:

N= 8290826691135830692772803 , P = 95972011
modulus (N % P) = 60316167

obviously we cannot store N as a number and BigInteger does not exist in the C programming language (gmp is out of the question)
How else can this be solved

Comments on this question (0)

Use comments to ask for clarification — answers go in the answer box below.

Log in to comment on this question.

6 answers

2

Why is GMP "out of the question"? There may be alternatives that satisfy your requirements, if only we knew what they were.

Otherwise, you might look to create an equivalent of the well-known methods for mentally calculating modulus of large numbers with small numbers (e.g. for % 7, we repeatedly multiply most-significant digit by 10-7=3 and add it to the next one, mod 7, until there's only a single digit left).

Blake Brooks · 0 rep · 9 hours ago

2

Hint: (10a+b)%P. Watch out for overflow in even the simplest arithmetic operations with P.

Cameron Price · 0 rep · 9 hours ago

1

The first step would be to figure out how to compute (a+b) mod c when both a and b are less than c but (a+b) may overflow. The rest should easily follow.

Riley Brooks · 0 rep · 9 hours ago

0

https://cs.stackexchange.com, obviously this is a better site for such a question.

Morgan Chen · 0 rep · 9 hours ago

0

obviously we cannot store N as a number

This is not certainly true.

Select implementations of standard C23 allow very wide integers types.
My C compiler allows a bit width up to 65535. C specifies at least 64.
8290826691135830692772803 needs 83 bits.

#include <stdio.h>

int main() {
  unsigned _BitInt(128) N = 8290826691135830692772803WB;
  unsigned long P = 95972011;
  unsigned long M = (unsigned long) (N%P);
  printf("8290826691135830692772803 %% 95972011 --> %lu\n", M);
}

8290826691135830692772803 % 95972011 --> 60316167

Sam Price · 0 rep · 9 hours ago

0

1e1000 needs something like _BitInt(33220), good luck with finding a supporting implementation.

Reese Diaz · 0 rep · 9 hours ago

Your answer