Самый эффективный способ сделать х = х * х мод (р) в Python: (я знаю, что х < р)x * x mod (p) наиболее эффективный питонический путь?
x = pow(a, 2, p)
или
x = x*x % p
или
x *= x
x %= p
(Я думаю, что x * x совпадает с x ** 2, если измеряется по эффективности, если нет, чем исправить меня).
Python имеет timeit модуль для тестирования именно такого рода вещи:
$ python -m timeit 'x = 2000; p = 2002; x = pow(x, 2, p)'
10000000 loops, best of 3: 0.115 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x = (x * x) % p'
10000000 loops, best of 3: 0.0542 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x *= x; x %= p'
10000000 loops, best of 3: 0.0614 usec per loop
Ваш ответ, что (x * x) % p и x *= x; x %= p примерно одинаковы, но pow гораздо медленнее.
Спасибо! можете ли вы разместить свой код? – Tom
Вот и все! Котируемый бит здесь скопирован с терминала с терминала. Биты в кавычках оцениваются 10M раз модулем 'timeit', который является частью стандартной библиотеки. –
Второй или третий. Первый имеет произвольный показатель и, таким образом, будет иметь вокруг него некоторые * структуры управления *. Но разница между вторым и третьим будет очень маленькой. –
Я предполагаю, что * a * должен быть * x *. И почему вы спрашиваете об этом, когда вы можете легко сделать тест самостоятельно и измерить время, необходимое для повторения каждой операции 1000000 раз. – trincot
Python включает функцию [timeit] (https://docs.python.org/2/library/timeit.html). Попробуй это. – TemporalWolf