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: 108826345568947 3669888943602 % 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: "12345678903333 333333555555555 5")
a: Integer (Eg: 320)
To find nBig % a:
Iteration 1:
1) Extract few digits from LHS of nBig.
So tmp = 1234567890 and nBig = “33333333335555 555555"
2) Find mod of tmp.
mod = tmp % a = 210
3) Prefix mod to nBig.
nBig = "21033333333335 555555555"
Now repeating above steps:
Iteration 2:
1) tmp = 2103333333 and nBig = "3335555555 555"
2) mod = tmp % a = 213
3) nBig = "21333355555555 55"
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)
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: 108826345568947 3669888943602 % 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: "12345678903333 333333555555555 5")
a: Integer (Eg: 320)
To find nBig % a:
Iteration 1:
1) Extract few digits from LHS of nBig.
So tmp = 1234567890 and nBig = “33333333335555 555555"
2) Find mod of tmp.
mod = tmp % a = 210
3) Prefix mod to nBig.
nBig = "21033333333335 555555555"
Now repeating above steps:
Iteration 2:
1) tmp = 2103333333 and nBig = "3335555555 555"
2) mod = tmp % a = 213
3) nBig = "21333355555555 55"
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)