Вычисления (a*b) модификация c быстро для c=2^N +-1
Попробуйте:
my_list = [
[ 'A', 'A1', { .... }],
[ 'A', 'A2', { .... }],
[ 'B'. 'B1', { .... }],
....
]
results = []
for item in my_list:
if item[0] == <criteria1> and item[1] == <criteria2>:
results.append(item)
6 ответов
Я думаю, что хитрость заключается в следующем (я собираюсь сделать это в базе 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 (мод 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-значные числа вместе и сложить их.
В двоичном коде это сработает аналогично.
Начните с 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)
Предположим, вы можете вычислить 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 .
Быстрый поиск обнаружил это: http://home.pipeline.com/~hbaker1/AB -Mod-N.pdf . К сожалению, для меня уже слишком поздно понимать смысл этого, чтобы просто писать в упрощенной формуле, но это, вероятно, где-то в этой статье.
Идентификатор, который вы ищете: x mod N = (x mod 2 ^ q) - c * floor (x / 2 ^ q) , учитывая, что N = 2 ^ q + c и c - любое целое число (но обычно ± 1).
Вы можете прочитать раздел 9.2.3: «Модули особой формы» в «Простые числа: Вычислительная перспектива " Ричарда Крэндалла и Карла Померанса. Помимо теории, он содержит псевдокод для алгоритма, реализующего вышеуказанное соотношение.
I have found a rather extensive page on this very topic, discussing not just the algorithm but even the specific history of the problem and solution and the ways people have used the solution.
Вместо того, чтобы делать модульное сокращение на каждом шаге, вы можете использовать сокращение Монтгомери (есть и другие описания ) для снижения стоимости модульного умножения. Это все еще не использует свойства N, являющегося плюс / минус степенью два, все же.