Вычисление (a * b) mod c быстро для c = 2 ^ N + -1

Question

В 32-битной целочисленной математике базовые математические операции сложения и умножения вычисляются неявно, как мод 2 ^ 32, что означает, что ваши результаты будут младшими битами сложения или умножения.

Если вы хотите вычислить результат с другим модулем, вы, безусловно, можете использовать любое количество классов BigInt на разных языках. А для значений a, b, c <2 ^ 32 вы можете вычислить промежуточные значения в 64-битных целых числах и использовать встроенные операторы%, чтобы уменьшить до нужного значения </p>

Но мне сказали, что есть специальные приемы для эффективного вычисления a * b mod C, когда C имеет форму (2 ^ N) -1 или (2 ^ N) +1, которые не используют 64 bit math или библиотека BigInt и являются довольно эффективными, в большей степени, чем произвольная оценка модуля, а также правильно вычисляют случаи, которые обычно переполняют 32-битное целое, если вы включаете промежуточное умножение.

К сожалению, несмотря на слух о том, что в таких особых случаях применяется быстрый метод оценки, я фактически не нашел описания метода. "Разве это не в Кнуте?" "Разве это не где-то в Википедии?" это бормотание, которое я слышал.

Это, очевидно, распространенная техника в генераторах случайных чисел, которые делают умножения a * b mod 2147483647, так как 2147483647 - простое число, равное 2 ^ 31 -1.

Так что я спрошу у экспертов. Что это за умный особый метод умножения с модом, о котором я не могу найти никакого обсуждения?

Answer 1

Я думаю, что уловка заключается в следующем (я собираюсь сделать это в базе 10, потому что это проще, но принцип должен держаться)

Предположим, вы умножаете a*b mod 10000-1 и

a = 1234 = 12 * 100 + 34
b = 5432 = 54 * 100 + 32

сейчас a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 =  648 * 10000
34 * 54 * 100   = 1836 * 100
12 * 32 * 100   =  384 * 100
34 * 32         = 1088

Поскольку x * 10000 ≡ x (mod 10000-1) [1], первое и последнее слагаемые становятся 648 + 1088. Второе и третье слагаемые - вот где «трюк». Обратите внимание:

1836 = 18 * 100 + 36
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1).

Это по сути круговое смещение. Дать результаты 648 + 3618 + 8403 + 1088. И также обратите внимание, что во всех случаях умноженные числа <10000 (так как a <100 и b <100), так что это можно вычислить, если вы могли бы только умножить 2-значные числа вместе и добавьте их. </p>

В двоичном коде все будет работать аналогично.

Начните с a и b, оба - 32 бита. Предположим, вы хотите умножить их мод 2 ^ 31 - 1, но у вас есть только 16-битный множитель (давая 32 бита). Алгоритм будет выглядеть примерно так:

 a = 0x12345678
 b = 0xfedbca98
 accumulator = 0
 for (x = 0; x < 32; x += 16)
     for (y = 0; y < 32; y += 16)
         // do the multiplication, 16-bit * 16-bit = 32-bit
         temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF)

         // add the bits to the accumulator, shifting over the right amount
         total_bits_shifted = x + y
         for (bits = 0; bits < total_bits_shifted + 32; bits += 31)
             accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF

         // do modulus if it overflows
         if (accumulator > 0x7FFFFFFFF)
             accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF);

Уже поздно, поэтому аккумуляторная часть этого, вероятно, не будет работать. Я думаю, что в принципе это правильно, хотя. Кто-то не стесняется редактировать это, чтобы сделать это правильно.

Развернутый, это также довольно быстро, это то, что, как я полагаю, использует PRNG.

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

Предположим, вы можете вычислить a * b как p*2^N+q. Это может потребовать 64-битных вычислений, или вы можете разделить a и b на 16-битные части и вычислить на 32-битных.

Тогда a*b mod 2^N-1 = p+q mod 2^N-1, так как 2^N mod 2^N-1 = 1.

И a*b mod 2^N+1 = -p+q mod 2^N+1 с 2^N mod 2^N+1 = -1.

В обоих случаях деление на 2^N-1 или 2^N+1.

отсутствует.

Answer 3

Быстрый поиск обнаружил следующее: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf. К сожалению, для меня уже слишком поздно понимать смысл этого, чтобы просто писать в упрощенной формуле, но, вероятно, где-то в этой статье.

Answer 4

Идентификация, которую вы ищете, - x mod N = (x mod 2^q)- c*floor(x/2^q), учитывая, что N = 2^q + c и c - любое целое число (но обычно ± 1).

Возможно, вы захотите прочитать раздел 9.2.3: «Модули специальной формы» в «Простые числа: вычислительная перспектива» Ричарда Крандалла и Карла Померанса. Помимо теории, он содержит псевдокод для алгоритма, реализующего вышеуказанное соотношение.

Answer 5

Вместо того, чтобы выполнять модульное сокращение на каждом шаге, вы можете использовать Сокращение Монтгомери (есть другие описания ), чтобы уменьшить стоимость вычисления модульного умножения. Это все еще не использует свойства N, являющегося плюс / минус степенью два, все же.

Answer 6

Я нашел довольно обширную страницу по этой самой теме, обсуждающую не только алгоритм, но даже конкретную историю проблемы и решения и способы, которыми люди использовали решение ,