Как я могу взять модуль двух очень больших чисел?

Question

Мне нужен алгоритм для A mod B с

1. A является очень большим целым числом и содержит только цифру 1 (например: 1111, 1111111111111111)
2. B - очень большое целое число (например, 1231, 1231231823127312918923)

Большой, я имею в виду 1000 цифр.

Answer 1

Чтобы вычислить число mod n, учитывая функцию для получения коэффициента и остатка при делении на (n + 1), начните с добавления единицы к числу. Затем, пока число больше 'n', итерируйте:

number = (number div (n+1)) + (number mod (n+1))

Наконец, в конце вычтите единицу. Альтернативой добавлению единицы в начале и вычитанию единицы в конце является проверка, равняется ли результат n, и возврат нуля, если так.

Например, если функция делится на десять, можно вычислить 12345678 mod 9 следующим образом:

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

Вычтите 1, и в результате получите ноль.

Answer 2

1000 цифр не очень большие, используйте любую большую целочисленную библиотеку, чтобы получить довольно быстрые результаты.

Если вы действительно беспокоитесь о производительности, A можно записать как 1111 ... 1 = (10 ⁿ -1) / 9 для некоторого n, поэтому вычисление A mod B может быть сведено к вычислению ( (10 ^ n-1) мод (9 * B)) / 9, и вы можете сделать это быстрее .

Answer 3

Попробуйте сокращение Монтгомери о том, как найти по модулю большие числа - http://en.wikipedia.org/wiki/Montgomery_reduction

Answer 4

1) Просто найдите язык или пакет, который выполняет арифметику произвольной точности - в моем случае я бы попробовал java.math.BigDecimal.

2) Если вы делаете это самостоятельно, вы можете избежать деления, используя удвоение и вычитание. Например. 10 мод 3 = 10 - 3 - 3 - 3 = 1 (многократно вычитая 3, пока вы больше не можете) - что невероятно медленно, поэтому удвойте 3, пока он не станет меньше 10 (например, до 6), отнимите, чтобы оставить 4, и повторите.