CODEWITHSUNDEEP
algorithmmath
SIGSTP
SIGSTP

Reputation: 1155

Remainder of a very very large number using a prime number

I am stuck with a problem where I need to find remainder of a very large number using a prime number. Actual problem is that the number is quite large, around 10^100. So we can not store it in any variable and only option is to store it in an array.

Now we need to find remainder of this number using a prime number say (10^9)+7.

I can't think of any idea, any suggestions?

P.S.: Programming language is C++.

Upvotes: 1

Views: 1884

Answers (3)

maxim1000
maxim1000

Reputation: 6365

A decimal number (e.g. 1234) can be built from its digits in the following way:

x=1;
x=x*10+2;
x=x*10+3;
x=x*10+4;//x=1234

(you start from the most significant digit and take next one every time).

Since addition and multiplication allow to move modulus operation into them, you can simply apply modulus (e.g. 7) on every step:

x=1;
x=(x*10+2)%7;
x=(x*10+3)%7;
x=(x*10+4)%7;//x=1234%7

If your prime is around 10^9, 32-bit integers will not be sufficient, but 64-bit will be more than enough.

Upvotes: 2

argentage
argentage

Reputation: 2778

In general I would exploit the fact that 

a^n mod b == (a mod b)^n mod b

So in this example, you might calculate

= 10^100 mod 10^9 + 7 = (10^10 mod 10^9 + 7)^10  mod 10^9 + 7

= (999999937) ^ 10 mod 10^9 + 7
= ((999999937) ^ 2 mod 10^9 + 7) ^ 5 mod 10^9 + 7
= 4900 ^ 5 mod 10^9 +7
= 226732710

etc.

Upvotes: 2

kainaw
kainaw

Reputation: 4334

What programming language? C/C++, Java, PHP, Perl, JavaScript... all have some form of Big Integer that allows you to have integers up to the maximum length of a null-terminated string. The actual syntax depends on the language, but would be something like:

$num = new BigInt("1234567891234567912346579865432165498765462132165498765431");
$prime = new BigInt("54657613216846346874321638743");
$mod = $num.mod($prime);

Upvotes: 2

Related Questions