この計算の複雑さを軽減することはできますか?

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

オフに基づいて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

Answer 2

一瞬のアルゴリズムを無視して（はい、私は、悪い考えを知っている）、これを実行している時は、ちょうどwhileするforから切り替えることで、の非常の減少することができます。

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

（これはoff-by-oneエラーを持っていません願っています。私はこれらを作るためにがちです。）

私がしようとするだろうもう一つは、ステップ幅がインクリメントできるかどうかを調べることです。

Answer 3

http://modular.fas.harvard.edu/ent/ent_pyを見てみましょうに。 あなたは= -1と、p = Nを設定している場合、機能sqrtmodが仕事をしていません。

あなたは逃した小さな点は、お使いの改善アルゴリズムの実行中の時間は、nの平方根のためにまだあるということです。限り、あなたはn個のみの小さな素数を持っていることは大丈夫です、あなたはおそらく、より複雑なものに実装を好むはずです（さんが2未満^ 64をしましょう）。

プライムnが大きくなる場合は、

、あなたは数論の少しを用いたアルゴリズムに切り替える必要がある場合があります。私の知る限りでは、あなたの問題は、時間のログ（N）^ 3で確率的アルゴリズムで解くことができます。 （ - 申し訳ありませんが、私のpythonを知らないRubyで）ログ（）N（ログ）*は、私の記憶が正しければ、（ほとんどの人がそうする）リーマン仮説が成り立つと仮定すると、1は次のアルゴリズムの実行中の時間があることを示すことができますログ（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

遅い部分は、現在（約とる^ 4整数演算）N（ログ）素数を見つけることです。 -1の平方根を求めること秒よりもさらに少ない512ビットの素数要する。

Answer 4

の結果を事前に計算して、ファイルにそれらを保存することを検討してください。今日では多くのプラットフォームは、巨大なディスク容量を持っています。次いで、結果を得ることはO（1）操作になります。

Answer 5

（アダムの答えのビル。）

：平方剰余の相互法則の上のWikipediaのページを見てください

  

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

Answer 6

あなたは-1を法n平方根を見つけようとしているように、

に見えます。残念ながら、これはあなたの関数に入力されるnのどのような値に応じて、簡単な問題ではありません。 nに応じて、でも解決策は存在しない可能性があります。この問題の詳細については、ウィキペディアのを参照してください。

Answer 7

編集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

ストレンジャーが投稿した 同じ考え しかし、それほど厳密にコード化されていないと思います。また、 ジャグの答え 最高です。

元の答え: Konrad Rudolph のものに加えて、もう 1 つの簡単なコーディングの調整:

def table(n):
    n1 = n - 1
    for a in xrange(1, n // 2 + 1):
          if (a*a) % n == n1: return a

私のラップトップでは速度が大幅に向上しました。(テーブル(1234577)の場合は約25%。)

編集： python3.0 タグには気づきませんでした。しかし、主な変更点は、計算の一部をループの外に巻き上げたことであり、 xrange. 。(より優れたアルゴリズムがあるので学術的です。)

Answer 8

あなたは結果をキャッシュすることは可能ですか？

あなたは、大きなNを計算するときは、

あなたは、下の結果を与えられたn個の自由のために、ほとんどですされます。

Answer 9

あなたは*何度も繰り返し計算-aを繰り返しているやっていることの一つます。

メインループで調べるか、一度、その後、値のテーブルを作成します。

あなたの関数名が表ですが、あなたは計算に時間がかかる関数を呼び出す場合は、テーブルに結果をキャッシュする必要があり、あなたは再びそれを呼び出す場合だけテーブルが見上げるんので

また、これはおそらくあなたには適用されませんが、同じ値を持ちます。あなたが最初の実行ができますが、複数回の計算を繰り返して時間を無駄にしないとき、これはあなたのすべての値を計算する時間を節約できます。

Answer 10

私が通過したと、それは、Python 3で動作させるためにハーバード大学のバージョンを固定しました。   http://modular.fas.harvard.edu/ent/ent_pyする

私はOPの関数としての結果はまったく同じにするために、いくつかのわずかな変更を加えました。 2つのがあり可能な答えがあると私は小さな答えを返すために、それを強制ます。

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 745ms
受け入れ答えの522msの
上記の機能0.2msの