Что ж, у меня есть этот фрагмент кода, который сильно замедляет программу, потому что это линейная сложность, но вызывается много раз, делая программу квадратичной сложностью. Если возможно, я хотел бы уменьшить его вычислительную сложность, но в противном случае я просто оптимизирую его, где смогу. Пока что я сократил до:
def table(n):
a = 1
while 2*a <= n:
if (-a*a)%n == 1: return a
a += 1
Кто-нибудь видит что-нибудь, что я пропустил? Спасибо!
Обновлено: я забыл упомянуть: n всегда является простым числом.
Обновлено еще раз: Вот моя новая улучшенная программа (спасибо за все вклады!):
def table(n):
if n == 2: return 1
if n%4 != 1: return
a1 = n-1
for a in range(1, n//2+1):
if (a*a)%n == a1: return a
РЕДАКТИРОВАТЬ 3: И тестируя его в реальном контексте, он много быстрее! Что ж, этот вопрос кажется решенным, но есть много полезных ответов. Я также должен сказать, что, помимо описанных выше оптимизаций, я запомнил функцию с помощью словарей Python ...
Вероятно ли, что некоторые значения n будут вызываться несколько раз? (в этом случае может быть какое-то значение в сохранении вычисленных значений, чтобы сохранить повторный запуск вычисления)
Какое значение имеет максимальное значение n и какое оно обычно?
Я добавил улучшенную (более быструю) версию вашего кода ... Проверьте это в моем ответе.
Эта функция вызывается (и запоминается) для множества различных простых чисел n. Некоторые большие, некоторые маленькие ... страннее, спасибо!
Я откатил его, так как "опечатка" на самом деле не была опечаткой. В Python три // выполняет «целочисленное деление», где / не усекает. Мы хотим, чтобы последнее было так, как положено.
@PythonPower, держу пари, вас смутила подсветка синтаксиса Stackoverflow. // комментарии в стиле C++. Это меня тоже смутило (я не знал оператора Python) и сначала подумал, что это опечатка. Потом я понял, что это целочисленное деление.
Игнорируя алгоритм на мгновение (да, я знаю, плохая идея), время его работы можно уменьшить чрезвычайно, просто переключившись с while
на for
.
for a in range(1, n / 2 + 1)
(Надеюсь, здесь нет ошибки разницы на единицу. Я склонен делать это.)
Еще я бы попробовал посмотреть, можно ли увеличить ширину шага.
Вы имели в виду, что время работы может быть уменьшился?
Похоже, вы пытаетесь найти квадратный корень из -1 по модулю n
. К сожалению, это непростая проблема, в зависимости от того, какие значения n
вводятся в вашу функцию. В зависимости от n
решения может и не быть. См. Википедия для получения дополнительной информации об этой проблеме.
n всегда является простым числом, так что это может помочь.
Возможно ли кеширование результатов?
Когда вы вычисляете большое n, вам почти бесплатно выдаются результаты для меньших n.
(Основываясь на ответе Адама.) Взгляните на страницу Википедии на квадратичная взаимность:
x^2 ≡ −1 (mod p) is solvable if and only if p ≡ 1 (mod 4).
Тогда вы можете избежать поиска корня именно для тех нечетных простых чисел n, которые не сравнимы с 1 по модулю 4:
def table(n):
if n == 2: return 1
if n%4 != 1: return None # or raise exception
...
Рассмотрите возможность предварительного вычисления результатов и сохранения их в файле. В настоящее время многие платформы имеют огромную дисковую емкость. Тогда получение результата будет операцией O (1).
Я бы не стал делать это на диск, только на память.
@ me.yahoo.com / loren.pechtel, он имеет ввиду загружать файл в память при запуске, а не вычислять таблицу каждый раз при запуске приложения.
Это непрактично: их вычисление изначально было слишком медленным. Но обычно это вариант.
Изменить 2: Удивительно, но уменьшение квадрата силы значительно сокращает время, по крайней мере, на моей установке Python2.5. (Я удивлен, потому что я думал, что накладные расходы интерпретатора занимают большую часть времени, и это не уменьшает количество операций во внутреннем цикле.) Уменьшает время с 0,572 с до 0,146 с для таблицы (1234577).
def table(n):
n1 = n - 1
square = 0
for delta in xrange(1, n, 2):
square += delta
if n <= square: square -= n
if square == n1: return delta // 2 + 1
Strager отправил та же идея, но я думаю, что он менее жестко закодирован. Опять же, ответ кувшина лучше всего.
Оригинальный ответ: Еще одна тривиальная настройка кода поверх настроек Конрада Рудольфа:
def table(n):
n1 = n - 1
for a in xrange(1, n // 2 + 1):
if (a*a) % n == n1: return a
Заметно ускоряет его на моем ноутбуке. (Около 25% для стола (1234577).)
Редактировать: Я не заметил тега python3.0; но главным изменением было исключение части вычислений из цикла, а не использование xrange
. (Академический, поскольку есть лучший алгоритм.)
Это ускорение не должно касаться Python 3.0, только более старых версий. Однако использование //
, конечно, лучше.
Я имел в виду изменение n-1 (или -a) из цикла. Это составляет большую часть ускорения.
Взгляните на http://modular.fas.harvard.edu/ent/ent_py. Функция sqrtmod выполнит свою работу, если вы установите a = -1 и p = n.
Вы упустили одну мелочь, потому что время работы вашего улучшенного алгоритма по-прежнему порядка квадратного корня из n. Пока у вас есть только маленькие простые числа n (скажем, менее 2 ^ 64), это нормально, и вам, вероятно, следует предпочесть свою реализацию более сложной.
Если простое число n становится больше, возможно, вам придется переключиться на алгоритм, использующий немного теории чисел. Насколько мне известно, ваша проблема может быть решена только с помощью вероятностного алгоритма за время log (n) ^ 3. Если я правильно помню, если предположить, что гипотеза Римана верна (что делает большинство людей), можно показать, что время работы следующего алгоритма (в ruby - извините, я не знаю python) - log (log (n)) * журнал (п) ^ 3:
class Integer
# calculate b to the power of e modulo self
def power(b, e)
raise 'power only defined for integer base' unless b.is_a? Integer
raise 'power only defined for integer exponent' unless e.is_a? Integer
raise 'power is implemented only for positive exponent' if e < 0
return 1 if e.zero?
x = power(b, e>>1)
x *= x
(e & 1).zero? ? x % self : (x*b) % self
end
# Fermat test (probabilistic prime number test)
def prime?(b = 2)
raise "base must be at least 2 in prime?" if b < 2
raise "base must be an integer in prime?" unless b.is_a? Integer
power(b, self >> 1) == 1
end
# find square root of -1 modulo prime
def sqrt_of_minus_one
return 1 if self == 2
return false if (self & 3) != 1
raise 'sqrt_of_minus_one works only for primes' unless prime?
# now just try all numbers (each succeeds with probability 1/2)
2.upto(self) do |b|
e = self >> 1
e >>= 1 while (e & 1).zero?
x = power(b, e)
next if [1, self-1].include? x
loop do
y = (x*x) % self
return x if y == self-1
raise 'sqrt_of_minus_one works only for primes' if y == 1
x = y
end
end
end
end
# find a prime
p = loop do
x = rand(1<<512)
next if (x & 3) != 1
break x if x.prime?
end
puts "%x" % p
puts "%x" % p.sqrt_of_minus_one
Медленная часть теперь находит простое число (что требует приблизительно log (n) ^ 4 целочисленной операции); нахождение квадратного корня из -1 занимает для 512-битных простых чисел меньше секунды.
Одна вещь, которую вы делаете, - это повторяете вычисление -a * a снова и снова.
Создайте таблицу значений один раз, а затем выполните поиск в основном цикле.
Кроме того, хотя это, вероятно, не относится к вам, потому что имя вашей функции - таблица, но если вы вызываете функцию, которая требует времени для вычисления, вы должны кэшировать результат в таблице и просто выполнить поиск таблицы, если вы снова вызовете ее с тем же значение. Это сэкономит вам время на вычисление всех значений при первом запуске, но вы не будете тратить время на повторение расчета более одного раза.
Поиск, вероятно, будет медленнее, чем умножение. Умножение довольно дешево по сравнению с модулем без знака.
Это академично, так как есть лучший алгоритм, но мой ответ вывел часть вычисления -a * из цикла.
На основе второго редактирования OP:
def table(n):
if n == 2: return 1
if n%4 != 1: return
mod = 0
a1 = n - 1
for a in xrange(1, a1, 2):
mod += a
while mod >= n: mod -= n
if mod == a1: return a//2 + 1
должно быть пока mod> = n: mod - = n
@Rex Logan, Хм ... Думаю, ты прав, но когда я тестировал значения 0..31337, все они работали. Я думаю, это потому, что a1 = n-1: если бы это было a1 = n-1, я, возможно, мог бы сделать mod> n-1. Думаю, странный побочный эффект в мою пользу. Я исправлю это в любом случае. Спасибо!
Я просмотрел и исправил версию для Гарварда, чтобы она работала с python 3. http://modular.fas.harvard.edu/ent/ent_py
Я внес несколько небольших изменений, чтобы результаты были точно такими же, как у функции OP. Есть два возможных ответа, и я заставил его вернуть меньший ответ.
import timeit
def table(n):
if n == 2: return 1
if n%4 != 1: return
a1=n-1
def inversemod(a, p):
x, y = xgcd(a, p)
return x%p
def xgcd(a, b):
x_sign = 1
if a < 0: a = -a; x_sign = -1
x = 1; y = 0; r = 0; s = 1
while b != 0:
(c, q) = (a%b, a//b)
(a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
return (x*x_sign, y)
def mul(x, y):
return ((x[0]*y[0]+a1*y[1]*x[1])%n,(x[0]*y[1]+x[1]*y[0])%n)
def pow(x, nn):
ans = (1,0)
xpow = x
while nn != 0:
if nn%2 != 0:
ans = mul(ans, xpow)
xpow = mul(xpow, xpow)
nn >>= 1
return ans
for z in range(2,n) :
u, v = pow((1,z), a1//2)
if v != 0:
vinv = inversemod(v, n)
if (vinv*vinv)%n == a1:
vinv %= n
if vinv <= n//2:
return vinv
else:
return n-vinv
tt=0
pri = [ 5,13,17,29,37,41,53,61,73,89,97,1234577,5915587277,3267000013,3628273133,2860486313,5463458053,3367900313 ]
for x in pri:
t=timeit.Timer('q=table('+str(x)+')','from __main__ import table')
tt +=t.timeit(number=100)
print("table(",x,") = ",table(x))
print('total time=',tt/100)
Эта версия занимает около 3 мсек для выполнения описанных выше тестовых случаев.
Для сравнения используется простое число 1234577
OP Edit2 745 мс
Принятый ответ 522ms
Вышеупомянутая функция 0,2 мс
Вы вызываете это много раз: для множества различных значений n? Это образец для значений n?