2

Pythonで大きな素数を扱う効率的​​な方法は何ですか? ここやグーグルで検索すると、そのためのさまざまな方法が見つかります...ふるい、素数テストアルゴリズム...より大きな素数にはどの方法が機能しますか?

4

3 に答える 3

11

数値が素数であるかどうかを判断するには、ふるいと素数テストがあります。

# for large numbers, xrange will throw an error.
# OverflowError: Python int too large to convert to C long
# to get over this:

def mrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# benchmarked on an old single-core system with 2GB RAM.

from math import sqrt

def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))

# benchmark is_prime(100**10-1) using mrange
# 10000 calls, 53191 per second.
# 60006 function calls in 0.190 seconds.

これが最速のようです。ご覧のとおり、別のバージョンがありnot anyます。

def is_prime(num)
    # ...
    return not any(num % i == 0 for i in mrange(3, int(sqrt(num)) + 1, 2))

ただし、ベンチマークでは、素数であるかどうかをテストしながら70006 function calls in 0.272 seconds.の使用を乗り越えました。all 60006 function calls in 0.190 seconds.100**10-1

次に高い素数を見つける必要がある場合、この方法は役に立ちません。素数性テストを行う必要があります。Miller-Rabinアルゴリズムが適切な選択であることがわかりました。フェルマー法より少し遅いですが、擬素数に対してはより正確です。上記の方法を使用すると、このシステムで +5 分かかります。

Miller-Rabinアルゴリズム：

from random import randrange
def is_prime(n, k=10):
    if n == 2:
        return True
    if not n & 1:
        return False

    def check(a, s, d, n):
        x = pow(a, d, n)
        if x == 1:
            return True
        for i in xrange(s - 1):
            if x == n - 1:
                return True
            x = pow(x, 2, n)
        return x == n - 1

    s = 0
    d = n - 1

    while d % 2 == 0:
        d >>= 1
        s += 1

    for i in xrange(k):
        a = randrange(2, n - 1)
        if not check(a, s, d, n):
            return False
    return True

Fermatアルゴリズム:

def is_prime(num):
    if num == 2:
        return True
    if not num & 1:
        return False
    return pow(2, num-1, num) == 1

次に高い素数を取得するには:

def next_prime(num):
    if (not num & 1) and (num != 2):
        num += 1
    if is_prime(num):
        num += 2
    while True:
        if is_prime(num):
            break
        num += 2
    return num

print next_prime(100**10-1) # returns `100000000000000000039`

# benchmark next_prime(100**10-1) using Miller-Rabin algorithm.
1000 calls, 337 per second.
258669 function calls in 2.971 seconds

Fermatテストを使用すると、 のベンチマークが得られました45006 function calls in 0.885 seconds.が、疑素素数の可能性が高くなります。

したがって、数値が素数かどうかを確認する必要がある場合は、最初の方法で問題なくis_prime機能します。メソッドを併用すると最速ですmrange。

理想的には、生成された素数を保存し、next_primeそこから読み取るだけです。

たとえば、次のアルゴリズムを使用next_primeします。Miller-Rabin

print next_prime(10^301)

# prints in 2.9s on the old single-core system, opposed to fermat's 2.8s
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000531

return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))これをタイムリーに行うことはできません。この古いシステムではそれさえできません。

そして、と が正しい値next_prime(10^301)を生成することを確認するために、と のアルゴリズムMiller-Rabinを使用してこれもテストされました。FermatSolovay-Strassen

参照: gist.github.comのfermat.py、miller_rabin.py、およびsolovay_strassen.py

編集：バグを修正しましたnext_prime

于 2013-06-25T13:04:57.313 に答える
0

の不正確さの可能性に対応して、呼び出しmath.sqrtを実行するための 2 つの異なる方法をベンチマークしました。この記事とこのCコードから来ていますisqrt(n)isqrt_2(n)

見られる最も一般的な方法：

def isqrt_1(n):
    x = n
    while True:
        y = (n // x + x) // 2
        if x <= y:
            return x
        x = y

cProfile.run('isqrt_2(10**308)')

ベンチマーク結果:

isqrt_1 at 10000 iterations: 12.25
Can perform 816 calls per second.

         10006 function calls in 12.904 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   12.904   12.904 <string>:1(<module>)
        1    0.690    0.690   12.904   12.904 math.py:10(func)
    10000   12.213    0.001   12.213    0.001 math.py:24(isqrt_1)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}
        2    0.000    0.000    0.000    0.000 {time.time}

この方法は非常に遅いです。そこで、次の方法を試します。

def isqrt_2(n):
    if n < 0:
        raise ValueError('Square root is not defined for negative numbers.')
    x = int(n)
   if x == 0:
        return 0
    a, b = divmod(x.bit_length(), 2)
    n = 2 ** (a + b)
    while True:
        y = (n + x // n) >> 1
        if y >= n:
            return n
        n = y

cProfile.run('isqrt_2(10**308)')

ベンチマーク結果:

isqrt_2 at 10000 iterations: 0.391000032425
Can perform 25575 calls per second.

         30006 function calls in 1.059 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.059    1.059 <string>:1(<module>)
        1    0.687    0.687    1.059    1.059 math.py:10(func)
    10000    0.348    0.000    0.372    0.000 math.py:34(isqrt_2)
    10000    0.013    0.000    0.013    0.000 {divmod}
    10000    0.011    0.000    0.011    0.000 {method 'bit_length' of 'long' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}
        2    0.000    0.000    0.000    0.000 {time.time}

ご覧のとおり、 と の違いはisqrt_1(n)驚くisqrt_2(n)ほど11.858999967575 seconds高速です。

Ideone.comでこの動作を確認するか、コードを入手してください。

注: Ideone.com では実行タイムアウトが発生したisqrt_1(n)ため、ベンチマークは10**200

于 2013-06-27T19:30:16.053 に答える
0

これについて、どの方法がより高速かを確認するために、ベンチマークとともに 2 つの記事を書きました。

Prime Numbers with PythonBaillie-PSWは、素数性テストを知る前に作成されました。

その後、 Python v2Lucas pseudoprimesを使用した素数が作成され、Baillie-PSW素数テストのベンチマークが行われました。

于 2013-06-27T16:06:28.640 に答える