9

好吧，我有这段代码大大减慢了程序的速度，因为它是线性复杂度，但被调用了很多次，使程序成为二次复杂度。如果可能的话，我想降低它的计算复杂度，否则我会尽可能地优化它。到目前为止，我已经减少到：

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 字典记住了该函数......

4

10 回答 10

6

暂时忽略算法（是的，我知道，坏主意），只需while从for.

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

（希望这没有一个错误的错误。我很容易犯这些。）

我会尝试的另一件事是查看步长是否可以增加。

于 2008-12-20T20:55:28.197 回答
5

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

你错过了一个小点，因为你改进算法的运行时间仍然是 n 的平方根。只要你只有小的素数 n（比如说小于 2^64），没关系，你可能应该更喜欢你的实现而不是更复杂的实现。

如果素数 n 变大，您可能需要切换到使用一点数论的算法。据我所知，您的问题只能使用时间 log​​(n)^3 中的概率算法来解决。如果我没记错的话，假设黎曼假设成立（大多数人都这样做），可以证明以下算法的运行时间（在 ruby​​ 中 - 对不起，我不知道 python）是 log(log(n))*日志（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 位素数仍然不到一秒。

于 2008-12-20T22:18:13.020 回答
4

考虑预先计算结果并将它们存储在文件中。现在很多平台都有巨大的磁盘容量。然后，获得结果将是一个 O(1) 操作。

于 2008-12-20T21:58:22.267 回答
3

（以亚当的回答为基础。）查看关于二次互易的维基百科页面：

x^2 ≡ −1 (mod p) 当且仅当 p ≡ 1 (mod 4) 是可解的。

然后，您可以避免为那些与 1 模 4 不相等的奇数素数 n 精确地搜索根：

def table(n):
    if n == 2: return 1
    if n%4 != 1: return None   # or raise exception
    ...
于 2008-12-20T21:53:59.903 回答
2

看起来您正试图找到 -1 modulo 的平方根n。不幸的是，这不是一个简单的问题，具体取决于n函数中输入的值。取决于n，甚至可能没有解决方案。有关此问题的更多信息，请参阅Wikipedia。

于 2008-12-20T21:03:53.453 回答
2

编辑 2：令人惊讶的是，减少平方的强度会大大减少时间，至少在我的 Python2.5 安装中是这样。（我很惊讶，因为我认为解释器开销占用了大部分时间，这并没有减少内部循环中的操作计数。）将 table(1234577) 的时间从 0.572 秒减少到 0.146 秒。

 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 发布了相同的想法，但我认为编码不那么紧密。再一次，水罐的答案是最好的。

原始答案： Konrad Rudolph 之上的另一个微不足道的编码调整：

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. （学术，因为有更好的算法。）

于 2008-12-20T22:10:14.253 回答
2

基于 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
于 2008-12-21T01:36:52.620 回答
1

你可以缓存结果吗？

当您计算较大的 n 时，您几乎可以免费获得较低 n 的结果。

于 2008-12-20T21:28:10.797 回答
1

您正在做的一件事是一遍又一遍地重复计算 -a*a。

一次创建一个值表，然后在主循环中查找。

此外，虽然这可能不适用于您，因为您的函数名称是表，但是如果您调用一个需要时间计算的函数，您应该将结果缓存在表中，如果您再次调用它，只需进行表查找价值。这可以节省您在第一次运行时计算所有值的时间，但您不会浪费时间多次重复计算。

于 2008-12-20T22:38:48.627 回答
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)

此版本运行上述测试用例大约需要 3ms。

使用素数进行比较 1234577
OP Edit2 745ms
接受的答案 522ms
上述函数 0.2ms

于 2008-12-30T08:06:34.123 回答