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

Question

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.

Answer 1

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.

Answer 2

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=(10ⁿ-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.

Answer 3

1) Just find a language or package that does arbitrary precision arithmetic - in my case I'd try java.math.BigDecimal.

2) If you are doing this yourself, you can avoid having to do division by using doubling and subtraction. E.g. 10 mod 3 = 10 - 3 - 3 - 3 = 1 (repeatedly subtracting 3 until you can't any more) - which is incredibly slow, so double 3 until it is just smaller than 10 (e.g. to 6), subtract to leave 4, and repeat.

Answer 4

Try Montgomery reduction on how to find modulo on large numbers - http://en.wikipedia.org/wiki/Montgomery_reduction