4

現在の通常の Python の長い乗算よりも高速なアルゴリズムが必要です。

まともなカラツバの実装を見つけようとしましたが、できません。

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

ご覧のとおり、これは複雑なことではなく、数回の掛け算だけです。ただし、最大 100000 桁の数字を 2.5 秒未満で処理する必要があります。

関数のスニペット、またはより高速な乗算関数の実装へのリンク、または役立つものをお願いします。

4

4 に答える 4

27

私は DecInt (Decimal Integer) ライブラリの作成者なので、いくつかコメントします。

DecInt ライブラリは、10 進数形式に変換する必要がある非常に大きな整数を扱うように特別に設計されています。10 進形式への変換に関する問題は、ほとんどの任意精度ライブラリが値を 2 進数で格納することです。これはメモリを利用する上で最も高速で効率的ですが、通常、2 進数から 10 進数への変換は低速です。Python の 2 進数から 10 進数への変換は O(n^2) アルゴリズムを使用するため、すぐに遅くなります。

DecInt は大きな 10 進数 (通常は 10^250) を使用し、非常に大きな数を 250 桁のブロックに格納します。非常に大きな数値を 10 進数形式に変換すると、O(n) で実行されるようになりました。

素朴な、または小学校の乗算の実行時間は O(n^2) です。Python では、実行時間が O(n^1.585) のカラツバ乗算を使用しています。DecInt は、からつば、Toom-Cook、および Nussbaumer 畳み込みの組み合わせを使用して、O(n*ln(n)) の実行時間を取得します。

DecInt のオーバーヘッドははるかに高くなりますが、O(n*ln(n)) 乗算と O(n) 変換の組み合わせは、Python の O(n^1.585) 乗算と O(n^2) 変換よりも最終的に高速になります。

ほとんどの計算では、すべての結果を 10 進形式で表示する必要はないため、ほぼすべての任意精度ライブラリでは、計算が簡単になる 2 進数が使用されます。DecInt は、非常に小さなニッチをターゲットにしています。数値が十分に大きい場合、DecInt はネイティブの Python よりも乗算と除算が高速になります。ただし、純粋なパフォーマンスを求める場合は、GMPY のようなライブラリが最も高速です。

DecInt がお役に立てて光栄です。

于 2009-12-04T09:06:59.123 に答える
9

遅いノートブックで15.9ミリ秒。あなたを遅くしているのはプリントです。2進数から10進数への変換は非常に遅く、これは印刷に必要な手順です。数値を出力する必要がある場合は、すでに説明したDecIntChristopheDを試してください。

DecIntは乗算の実行が遅くなりますが、印刷ははるかに高速になります

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

これは、コードのバージョンを少し変更した例です。このコンピュータでは、100000桁の文字列をlongに変換するのにすでに約1秒かかることに注意してください

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop
于 2009-12-02T22:10:14.110 に答える
2

Sage math toolを入手することをお勧めします。これには、これまでに作成されたほぼすべての Python 数学ツールが 1 つのパッケージにまとめられています。Sage に、あなたのニーズに合った高速な任意精度の数学ツールがあるかどうかを確認してください。

于 2009-12-02T21:14:42.593 に答える
2

DecInt モジュールの実装を見ることができます(純粋な Python バージョン (Toom-Cook) が利用可能ですが、gmpyを使用するとおそらく最速になります)。

于 2009-12-02T22:00:32.433 に答える