3

これに似た質問が既にあることは知っていますが、GMPY2 (または GMP に類似したもの) を使用して高速化したいと考えています。これが私の現在のコードです。それはまともですが、もっと良くなるでしょうか?

編集: 新しいコード、除数 2 と 3 をチェック

def factors(n):
    result = set()
    result |= {mpz(1), mpz(n)}


    def all_multiples(result, n, factor):
        z = mpz(n)
        while gmpy2.f_mod(mpz(z), factor) == 0:
            z = gmpy2.divexact(z, factor)
            result |= {mpz(factor), z}
        return result

    result = all_multiples(result, n, 2)
    result = all_multiples(result, n, 3)

    for i in range(1, gmpy2.isqrt(n) + 1, 6):
        i1 = mpz(i) + 1
        i2 = mpz(i) + 5
        div1, mod1 = gmpy2.f_divmod(n, i1)
        div2, mod2 = gmpy2.f_divmod(n, i2)
        if mod1 == 0:
            result |= {i1, div1}
        if mod2 == 0:
            result |= {i2, div2}
    return result

可能であれば、除数のみを使用した実装にも興味がありますn^(1/3) and 2^(2/3)*n(1/3)

例として、mathematicafactor()は python コードよりもはるかに高速です。10 進数で 20 ～ 50 桁の数値を因数分解したいと考えています。私は、ggnfs がこれらを 5 秒以内に因数分解できることを知っています。

Pythonにも高速因数分解を実装するモジュールが存在するかどうかに興味があります。

4

2 に答える 2

7

冗長な名前検索をなくすために、コードに簡単な変更を加えました。アルゴリズムは同じですが、私のコンピューターでは約 2 倍高速です。

import gmpy2
from gmpy2 import mpz

def factors(n):
    result = set()
    n = mpz(n)
    for i in range(1, gmpy2.isqrt(n) + 1):
        div, mod = divmod(n, i)
        if not mod:
            result |= {mpz(i), div}
    return result

print(factors(12345678901234567))

他の提案では、数値のサイズなどに関するより多くの情報が必要になります。たとえば、すべての可能な要因が必要な場合は、すべての素因数からそれらを構築する方が速い場合があります。このアプローチでは、先に進むにつれて範囲ステートメントの制限を減らすことができ、2 ずつ増やすこともできます (2 の要素をすべて削除した後)。

更新 1

コードに追加の変更を加えました。all_multiplies()あなたの機能は正しくないと思います。range()2 は再度チェックされるため、ステートメントは最適ではありませんが、最初の修正でさらに悪化しました。

新しいコードは、剰余が 0 になるまで余因子の計算を遅らせます。また、組み込み関数を可能な限り使用するようにしました。たとえば、mpz % integergmpy2.f_mod(mpz, integer) または gmpy2.f_mod(integer, mpz) よりも高速です。ここintegerで、 は通常の Python 整数です。

import gmpy2
from gmpy2 import mpz, isqrt

def factors(n):
    n = mpz(n)

    result = set()
    result |= {mpz(1), n}

    def all_multiples(result, n, factor):
        z = n
        f = mpz(factor)
        while z % f == 0:
            result |= {f, z // f}
            f += factor
        return result

    result = all_multiples(result, n, 2)
    result = all_multiples(result, n, 3)

    for i in range(1, isqrt(n) + 1, 6):
        i1 = i + 1
        i2 = i + 5
        if not n % i1:
            result |= {mpz(i1), n // i1}
        if not n % i2:
            result |= {mpz(i2), n // i2}
    return result

print(factors(12345678901234567))

の平方根より小さいすべての素因数を見つけて、n後ですべての余因子を構築するようにプログラムを変更します。n次に、因子を見つけるたびに減少しn、素数であるかどうかを確認し、素数でない場合にのみさらに因子を探しますn。

更新 2

pyecmモジュールは、因数分解しようとしているサイズの数値を因数分解できるはずです。次の例は、約 1 秒で完了します。

>>> import pyecm
>>> list(pyecm.factors(12345678901234567890123456789012345678901, False, True, 10, 1))
[mpz(29), mpz(43), mpz(43), mpz(55202177), mpz(2928109491677), mpz(1424415039563189)]
于 2014-05-17T13:50:16.973 に答える