How to find modulus of a very large number

[zephyrus360]

This is about a technique to find the mod of a very large integer with a normal small integer.

I recently encountered this problem when I needed to compute the modulus of a very large number with a normal integer. I needed this in a C++ program running on a 32-bit UNIX platform. The problem was that the number was 28 digits long and no native datatype in c++ could store a number of that size.
(Eg: 1088263455689473669888943602 % 380)
Not even unsigned long long or long double could help; they all were of 8bytes.
I figured out that it can be done the following way.


Solution- Divide and conquer:
The entire number doesn't have to be processed in one go. A divide and conquer strategy can be used in this case. Divide the number into smaller numbers; find remainders of these smaller numbers. Add up the remainders and repeat the process. As long as the remainders are retained, the final answer won’t change.

Suppose, you need to find nBig%a
1) Take a manageable portion (say x) of the input large number nBig and subtract it from nBig (nBig = nBig - x)
2) Compute mod of x (mod = x%a)
3) Add the mod to nBig (nBig = nBig + mod)
This way the number nBig can be reduced without affecting the actual answer.

Eg: To find 27%8:
1) Let x = 17. So nBig = nBig - x = 27-17 = 10
2) mod = x % a = 17 % 8 = 1
3) nBig = nBig + mod = 10 + 1 = 11
So nBig is reduced from 27 to 11 without affecting the answer which is 3.


Finding mod of large numbers:
Extending the same logic, the above problem can be solved as follows:-
Let input be:
nBig: String representing a 30 digit large number (Eg: "123456789033333333335555555555")
a: Integer (Eg: 320)

To find nBig % a:

Iteration 1:
1) Extract few digits from LHS of nBig.
So tmp = 1234567890 and nBig = “33333333335555555555"
2) Find mod of tmp.
mod = tmp % a = 210
3) Prefix mod to nBig.
nBig = "21033333333335555555555"

Now repeating above steps:
Iteration 2:
1) tmp = 2103333333 and nBig = "3335555555555"
2) mod = tmp % a = 213
3) nBig = "2133335555555555"

Iteration 3:
1) tmp = 2133335555 and nBig = "555555"
2) mod = tmp % a = 195
3) nBig = "195555555"

Iteration 4:
1) tmp = 195555555 and nBig = ""
2) mod = tmp % a = 35

Answer = 35


Pseudo code:
To find nBig % a:
Let d = the number of digits that can be processed at a time.

Repeat while val( nBig ) >= a
1. tmpStr := d digits from the LHS of nBig.
2. nBig := Remaining portion of nBig
3. tmpNum := toInteger( tmpStr )
4. tmpNum := tmpNum % a
5. tmpStr := toString( tmpNum )
6. nBig := tmpStr + nBig

Selecting d:
d should satisfy following constraint
max no. of digits in Mod a < d <= max. digits in tmpNum - max no. of digits in Mod a
(For eg: If a = 512 (Mod ranges 0..511), and tmpNum can store max 16 digits, then
3 < d <= 16-3)
(For eg: If a = 100 (Mod ranges 0..99), and tmpNum can store max 16 digits, then
2 < d <= 16-2)