9

さて、私はプログラムを非常に遅くしているこのビットのコードを持っています。これは線形複雑ですが、何度も呼び出されてプログラムを二次複雑にするためです。可能であれば、計算の複雑さを減らしたいと思いますが、それ以外の場合は、できる限り最適化します。これまでのところ、次のように削減しました。

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

      a += 1

私が見逃したものを見た人はいますか？ありがとう！

編集: 言い忘れました: n は常に素数です。

EDIT 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

EDIT 3:実際のコンテキストでテストすると、はるかに高速です! この質問は解決されたように見えますが、多くの有用な回答があります。また、上記の最適化と同様に、Python 辞書を使用して関数をメモしました...

4

10 に答える 10

6

アルゴリズムをしばらく無視すると (はい、わかっています、悪い考えです)、からに切り替えるだけで、この実行時間を大幅に短縮できます。whilefor

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

（これにオフバイワンエラーがないことを願っています。私はこれらを作成する傾向があります。）

私が試みるもう 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 ビットの素数が 1 秒未満かかります。

于 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) の場合のみです。

次に、4 を法とする 1 と一致しない奇数の素数 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、解決策がない場合もあります。この問題の詳細については、ウィキペディアを参照してください。

于 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 のものに加えて、もう 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。（より良いアルゴリズムがあるため、学術的です。）

于 2008-12-20T22:10:14.253 に答える
2

OPの2番目の編集に基づく：

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

あなたがしていることの1つは、計算-a*aを何度も繰り返すことです。

値のテーブルを一度作成してから、メインループで検索します。

また、関数名がテーブルであるため、これはおそらく当てはまりませんが、計算に時間がかかる関数を呼び出す場合は、結果をテーブルにキャッシュし、同じもので再度呼び出す場合はテーブルルックアップを実行する必要があります。価値。これにより、最初に実行したときにすべての値を計算する時間を節約できますが、計算を2回以上繰り返す時間を無駄にすることはありません。

于 2008-12-20T22:38:48.627 に答える
1

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

于 2008-12-30T08:06:34.123 に答える
1

結果をキャッシュすることは可能ですか?

大きな n を計算すると、低い n の結果がほとんど無料で得られます。

于 2008-12-20T21:28:10.797 に答える