我可以降低这种计算的复杂性？
https://stackoverflow.com/questions/383728
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
好了，我的是巨大的减缓计划，因为它是线性的复杂代码这一点，但叫了很多次使得程序复杂平方。如果可能的话，我想，以减少它的计算复杂性，但否则我就优化它在那里我可以。到目前为止，我已经减少到：
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字典已memoized功能...
解决方案
根据关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
其他提示
忽略算法一会儿（是的，我知道，坏主意），这样做的运行时间可以减少的巨大的只是由while切换到for。
for a in range(1, n / 2 + 1)
（希望这不具有差一错误，我容易使这些。）
这我想尝试另一件事是看如果步宽度可以被递增。
看一看 http://modular.fas.harvard.edu/ent/ent_py 。 功能sqrtmod做这项工作如果设置= -1且p = N。
您错过了一个小的一点是，你的改进算法的运行时间仍是n的平方根的顺序。只要你只有少量素数N（比方说小于2 ^ 64）没关系，你或许应该更喜欢您的实现更复杂的一个。
如果素数n变大，你可能需要切换到使用数论的一点点的算法。据我所知，您的问题只能用时间的log（n）^ 3概率算法来解决。如果我没有记错，假设黎曼假设成立（其中大多数人一样），可以显示出下面的算法的运行时间（以红宝石 - 对不起，我不知道蟒蛇）是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位的素数仍小于一秒。
考虑预先计算的结果并将它们存储在一个文件中。现在很多平台上有一个巨大的磁盘容量。然后，获得的结果将是一个O（1）的操作。
（亚当的回答大厦。） 看Wikipedia页面上二次互：
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
...
它看起来像你想找到的-1模n的平方根。不幸的是，这不是一个简单的问题，这取决于什么样的价值观n的输入到你的函数。根据n，有可能甚至是一个解决办法。请参阅维基百科获得有关此问题的详细信息。
修改2：出人意料地，强度降低的平方减少了很多时间，至少在我的python2.5安装。 （我很惊讶，因为我想解释的开销正在采取的大部分时间，而这并没有减少在内部循环操作的次数）减少了时间从0.572s到0.146s的表（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发布相同的想法但我想象的那么严格的代码。此外，壶的回答是最好的。
<强>原来的答复：在的康拉德鲁道夫的顶部另一个平凡编码TWEAK：
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的。 （学术因为有更好的算法。）
是否有可能为你缓存的结果？
在计算你给出了较低的结果N为几乎是免费的。一个大的n
一件事，你正在做的是*一个一遍又一遍的重复计算-a。
创建的值一次的一个表，并然后执行查找在主循环。
此外，虽然这可能并不适用于你，因为你的函数名是表，但如果你调用一个函数，需要一定的时间来计算，你应该缓存结果在表只是做一个表中查找，如果你再次调用它以相同的值。这为您节省计算所有值的时候，你第一次运行，但你不要浪费时间重复计算不止一次。
我经历了和固定哈佛的版本，使其与巨蟒-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
