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

Question

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

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

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

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

По-видимому, это обычная техника в генераторах случайных чисел, которые выполняют умножения 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 (начиная с < 100 и b < 100), поэтому это можно вычислить, если вы можете использовать только несколько двузначных чисел вместе , и добавить их.

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

Начинать с a и b, то есть 32 бит. Предположим, вы хотите размножить их mod 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

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

Answer 3

Предположим, вы можете вычислить 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 4

Для уменьшения стоимости модульного вычисления умножения на каждом шаге вы можете использовать Montgomery reduction (есть другие descriptions). Тем не менее, это свойство не использует свойства N как плюса/минуса, равного двум.

Answer 5

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

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

Answer 6

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