Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I take the modulus of two very large numbers?

Tags:

algorithm

math

I need an algorithm for A mod B with

  1. A is a very big integer and it contains digit 1 only (ex: 1111, 1111111111111111)
  2. B is a very big integer (ex: 1231, 1231231823127312918923)

Big, I mean 1000 digits.

like image 446
complez Avatar asked Oct 22 '10 17:10

complez


2 Answers

To compute a number mod n, given a function to get quotient and remainder when dividing by (n+1), start by adding one to the number. Then, as long as the number is bigger than 'n', iterate:

number = (number div (n+1)) + (number mod (n+1))
Finally at the end, subtract one. An alternative to adding one at the beginning and subtracting one at the end is checking whether the result equals n and returning zero if so.

For example, given a function to divide by ten, one can compute 12345678 mod 9 thusly:

12345679 -> 1234567 + 9
 1234576 -> 123457 + 6
  123463 -> 12346 + 3
   12349 -> 1234 + 9
    1243 -> 124 + 3
     127 -> 12 + 7
      19 -> 1 + 9
      10 -> 1

Subtract 1, and the result is zero.

like image 149
supercat Avatar answered Sep 28 '22 17:09

supercat


1000 digits isn't really big, use any big integer library to get rather fast results.

If you really worry about performance, A can be written as 1111...1=(10n-1)/9 for some n, so computing A mod B can be reduced to computing ((10^n-1) mod (9*B)) / 9, and you can do that faster.

like image 39
sdcvvc Avatar answered Sep 28 '22 15:09

sdcvvc