Быстрое умножение и операция по модулю

ProgramBox

Быстрое умножение и операция по модулю

Post author:admin
Запись опубликована:14 ноября, 2022
Post category:Вопросы по программированию

#python #python-2.7

Вопрос:

Мне нужно вычислить:

 x=(x*a b)/2 % 2**128

много раз. x, a, b — 128-битные числа (выбираются случайным образом). Как сделать это самым быстрым способом? Я подумал о numpy, может ли это как-то помочь? Теперь это примерно в 100 раз медленнее… Есть ли способ сделать это быстрее? Конечно, это нужно делать отдельно, шаг за шагом, алгоритм более сложный, чем этот (a, b изменяется через несколько шагов), поэтому мы не можем пытаться выполнять здесь какую-либо математику или быстрое возведение в степень.

Пример более полного кода:

 a=333
b=555
c=777
d=999
x=12345

for i in range(128):
    if x % 2 == 1:
        x=((x * a   b)/2) % 340282366920938463463374607431768211456
    else:
        x=(x * c/2   d) % 340282366920938463463374607431768211456
    print(x)

1. Почему вы используете Python 2? Срок его службы истек.

2. Что вы подразумеваете под » вычислением «? Вы решаете уравнение?

3. Простым шагом является предварительное вычисление 2 ** 128.

4. В каком формате или структуре данных находятся многие x s? И что вы имеете в a виду под и b изменением, изменением как? Вы вычисляете деление на 2 по модулю 2 ^ 128 — я предполагаю, что вы вычисляете целочисленные значения и не заботитесь о том, чтобы нечетные числа делились на 2? Это также означает, что вы можете получить более быстрые результаты путем сдвига битов вместо фактического умножения и деления, поскольку все это степени 2.

5. Пожалуйста, изучите битовые операции Python. Это почти наверняка быстрее с операциями сдвига и маски. Более того, я предполагаю, что вы работаете со 128-битным линейным конгруэнтным генератором случайных чисел. Если это так, то публикация этих вопросов предполагает, что вы должным образом не исследовали эту парадигму, потому что тогда у вас уже были бы реализованы побитовые операции.

Ответ №1:

У вас возникнут некоторые проблемы из-за того, что вы выполняете неэффективные операции: 128-битные целые числа не являются родными для большинства реализаций Python и будут подвергаться штрафам за операции longint. Однако вы можете сократить время выполнения примерно на 20%, если будете использовать операции сдвига и маски вместо деления и деления по модулю на степени 2:

 import timeit

a=333
b=555
c=777
d=999
x=12345
two_128 = 2 ** 128
mask = two_128 - 1

def rng_orig(x):
    for i in range(128):
        if x % 2 == 1:
            x=((x * a   b)/2) % two_128
        else:
            x=(x * c/2   d) % two_128


def rng_bit(x):
    for i in range(128):
        if x amp; 1:
            x=((x * a   b) >> 1) amp; mask
        else:
            x=(x * (c >> 1)   d) amp; mask


repeat = 100000
print(timeit.timeit(lambda: rng_orig(x), number = repeat))
print(timeit.timeit(lambda: rng_bit (x), number = repeat))

Результаты синхронизации:

 5.1968478000000005
3.965898900000001

1. Спасибо. Это работает! Я где-то читал об этом, я подумал, что это можно сделать по-другому, но не знал точно, как. Теперь это кажется очевидным и тривиальным.

2. Что-то здесь не так: x=(x * (c >> 1) d) . Оно не равно x=(x * c / 2 d). Также x=(x * (c / 2) d) не равно x=(x * c / 2 d). x= (x * c >> 1 d) также неверно.

3. Я думаю, что я это исправил. Это может быть x=((x >> 1) * c d).

Ответ №2:

Если предполагается, что это целочисленная арифметика, вы должны использовать целочисленные деления. Это позволит избежать ненужного преобразования в числа с плавающей запятой. Кроме того, использование побитовых операций для модуля, вероятно, будет быстрее.

 mask128 = 2**128 - 1

x = ( (x*a b)//2 ) amp; mask128