Могу ли я уменьшить вычислительную сложность этого?

Question

Ну, у меня есть этот фрагмент кода, который сильно замедляет программу, потому что это линейная сложность, но многократно вызываемая программа делает квадратичную сложность программы. Если возможно, я бы хотел уменьшить его вычислительную сложность, но в противном случае я просто оптимизирую его там, где могу. До сих пор я сократил до:

def table(n):
    a = 1
    while 2*a <= n:
      if (-a*a)%n == 1: return a

      a += 1

Кто-нибудь видит что-то, что я пропустил? Спасибо!

РЕДАКТИРОВАТЬ: я забыл упомянуть: n всегда простое число.

РЕДАКТИРОВАТЬ 2: Вот моя новая улучшенная программа (спасибо за все вклады!):

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 ...

Answer 1

Игнорируя алгоритм на мгновение (да, я знаю, плохая идея), время работы этого можно уменьшить в огромном размере , просто переключившись с while на for.

for a in range(1, n / 2 + 1)

(Надеюсь, в этом нет единой ошибки. Я склонен делать это.)

Еще одна вещь, которую я бы попробовал - посмотреть, можно ли увеличить ширину шага.

Answer 2

Взгляните на 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-битных простых чисел, которые все еще меньше секунды.

Answer 3

Рассмотрите возможность предварительного вычисления результатов и сохранения их в файле. В настоящее время многие платформы имеют огромную емкость диска. Тогда получение результата будет операцией O (1).

Answer 4

(Опираясь на ответ Адама.) Посмотрите на страницу Википедии о квадратичной взаимности :

x ^ 2 ≡ −1 (mod p) разрешима тогда и только тогда, когда p ≡ 1 (mod 4).

Тогда вы можете избежать поиска корня именно для тех нечетных простых n, которые не совпадают с 1 по модулю 4:

def table(n):
    if n == 2: return 1
    if n%4 != 1: return None   # or raise exception
    ...

Answer 5

На основании второго редактирования ОП:

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

Answer 6

Редактировать 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. (Академический, поскольку есть лучший алгоритм.)

Answer 7

Похоже, вы пытаетесь найти квадратный корень из -1 по модулю n. К сожалению, это не простая проблема, в зависимости от того, какие значения n введены в вашу функцию. В зависимости от n, может даже не быть решения. См. Википедия для получения дополнительной информации по этой проблеме.

Answer 8

Я прошел и исправил версию Гарварда, чтобы она работала с питоном 3. http://modular.fas.harvard.edu/ent/ent_py

Я сделал несколько небольших изменений, чтобы результаты были точно такими же, как и у функции ОП. Есть два возможных ответа, и я заставил его вернуть меньший ответ.

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мс
Принятый ответ 522мс
Вышеуказанная функция 0,2 мс

Answer 9

Одна вещь, которую вы делаете, это повторение вычисления -a * a снова и снова.

Создайте таблицу значений один раз, а затем посмотрите в главном цикле.

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

Answer 10

Можно ли кешировать результаты?

Когда вы вычисляете большое n, вы получаете результаты для более низких n почти бесплатно.