Finding the value of a 100 digit number mod 10^9+7 in C

Question

Say I'm given 100 digit number (input can be string) . I want to find the value of that number % mod , where mod is 10^9+7. How can I go about getting the answer. I have already implemented the addition and subtraction functions on large numbers using string manipulation.

Thanks in advance !

As i said , I have only done addition and subtraction on strings. I tried all data types but get runtime error when I try to find very large numbers % mod such as 10^100 — anirudh_raja, Mar 01 '13 at 17:10
10 bucks says this is a Project Euler of some sort and that you don't actually need to compute that 100 digit number to begin with. — Mysticial, Mar 01 '13 at 17:10
There should be a C++ library with arbitrary-length integers. Unless you're only doing it once (or doing it as a challenge), using string manipulation for large-integer arithmetic seems like a bad idea. — Reinstate Monica -- notmaynard, Mar 01 '13 at 17:13
@AnirudhRaja If you show the signatures of your addition and subtraction, things may go a little better: at least we'll have a better idea of the interfaces that you are building. — Sergey Kalinichenko, Mar 01 '13 at 17:13
@Steve Jessop : So, I should perform division of the two numbers and then possibly get the remainder , is it ? — anirudh_raja, Mar 01 '13 at 17:14
@SteveJessop One can skip multiplication and go straight to long division in binary, or even in decimal by repeatedly adding a number to itself for two to nine times :) — Sergey Kalinichenko, Mar 01 '13 at 17:14
Is there any mathematical hint , like some sort of pattern repetition or something — anirudh_raja, Mar 01 '13 at 17:15
@AnirudhRaja There's no pattern, because `10^9+7` is a prime number (in fact, it's the first prime with ten digits). — Sergey Kalinichenko, Mar 01 '13 at 17:16
This can be done with a single O(N) time pass over the entire string. Here's a hint: Use [Horner's method](http://en.wikipedia.org/wiki/Horner%27s_method) combined with intermediate modular reductions. — Mysticial, Mar 01 '13 at 17:19
Use the [Grid method](http://en.wikipedia.org/wiki/Grid_method_multiplication) to implement multiplication. — andre, Mar 01 '13 at 17:20
@FredOverflow : Its actually a part of a problem which requires this — anirudh_raja, Mar 01 '13 at 17:22

Joni · Accepted Answer · 2013-03-01T18:13:23.530

2

10⁹ is -7 modulo 1000000007.

Break the 100 digit number N into blocks of 9 digits (a₀, a₁, ...) starting from the right. We have:

N = a0 + a1*10^9 + a2*10^18 + ...

The modulus is a₀ - 7*a₁ + 49*a₂ - ...

For example, suppose you are to calculate 87564875326485487234854862386245865486238654862 modulo 1000000007. You break this string of digits into blocks of 9 starting from the right:

a₀ = 238654862
a₁ = 245865486
a₂ = 245865486
a₃ = 854862386
a₄ = 485487234
a₅ = 564875326
a₆ = 87

Now you convert each block into an integer and calculate m = a₀ - 7*a₁ + 49*a₂ - 323*a₃ +... (hint: use 64 bit integers).

Now N = m (mod 1000000007).

edited Mar 01 '13 at 18:13

answered Mar 01 '13 at 17:27

Joni

108,737
14
143
193

This is in fact the correct answer. Even a bit more optimized than the one I had in mind. – Mysticial Mar 01 '13 at 17:28
So, basically calculation of a0 is the imp one . ? – anirudh_raja Mar 01 '13 at 17:30
ok, but I can't accept such a huge number in C++ , so I take it in as a string. Then how to proceed – anirudh_raja Mar 01 '13 at 17:32
a0 is the number that consists of the 9 right most digits, a1 is the following 9, and so on. – Joni Mar 01 '13 at 17:32
@Joni could you please help me out . How to convert the string into the value I require – anirudh_raja Mar 01 '13 at 17:37
Are you asking how to break a string into blocks of 9 characters, or how to convert a string of 9 digits into an integer? – Joni Mar 01 '13 at 17:45
Yes, as I can't input a large number as an integer. I'll take it as a string . Then how to use the formula you have suggested for the set of characters in a string – anirudh_raja Mar 01 '13 at 17:48
I've added an example to the answer. – Joni Mar 01 '13 at 18:14
@Joni , Thanks a ton ! Brilliant explanation . – anirudh_raja Mar 02 '13 at 03:20

Finding the value of a 100 digit number mod 10^9+7 in C

1 Answers1