我可以降低这个的计算复杂度吗？

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

暂时忽略算法(是的,我知道,坏主意),只需切换到,就可以大大减少运行时间.whilefor

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

(希望这不会有一个错误.我很容易做出这些.)

我要尝试的另一件事是查看步长是否可以递增.

Answer 2

看看http://modular.fas.harvard.edu/ent/ent_py.如果设置= -1和p = n,则函数sqrtmod可以完成这项工作.

您错过的一个小点是,改进算法的运行时间仍然是n的平方根的顺序.只要你只有小素数n(比如说小于2 ^ 64)就可以了,你应该更喜欢你的实现更复杂的.

如果素数n变大,则可能必须使用一些数论来切换到算法.据我所知,您的问题只能通过时间log(n)^ 3中的概率算法来解决.如果我没记错的话,假设Riemann假设成立(大多数人都这样做),可以证明以下算法的运行时间(在ruby中 - 抱歉,我不知道python)是log(log(n))*的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

基于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