質問

私は速く、現在の通常の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()
ご覧のとおり、

、それは複雑な何も、わずか数回の乗算ません。しかし、それは、2.5秒の下で最大100000桁の数字を処理する必要があります。

私は助け機能のいくつかのスニペットまたは単にリンクより高速乗算機能のいくつかの実装に、または何かをたいと思います。

役に立ちましたか？

解決

あなたは DecIntモジュールの（純粋なPythonのバージョンの実装を見ているかもしれません最速ものの利用可能（Toom-クック） gmpyする）を使用している場合、それはおそらくになります。

他のヒント

私はので、私はいくつかのコメントを作ってあげるDecInt（小数点整数）ライブラリの作者です。

DecIntライブラリーは、具体的には、小数点形式に変換するために必要な非常に大きな整数で動作するように設計されました。小数点形式に変換の問題点は、ほとんどの任意精度ライブラリがバイナリの値を格納することです。これは、メモリを利用しますが、通常は遅い2進数から10進数への変換するための最速かつ最も効率的です。変換を10進数にPythonのバイナリはO（N ^ 2）のアルゴリズムを使用し、非常に迅速に遅くなります。

DecIntが大きい10進数250桁のブロック内（通常10 ^ 250）に格納する非常に大きな数を使用します。小数点形式に非常に多数の変換今O（N）で実行されます。

ナイーブな、または小学校、乗算はO（N ^ 2）の運転時間を持っています。 PythonはOの時間（N ^ 1.585）を実行したカラツバ乗算を使用しています。 DecIntはO（n個の*のLN（N））の運転時間を取得するためにカラツバ、Toom-クック、およびNussbaumer畳み込みの組み合わせを使用します。

DecIntがはるかに高いオーバーヘッドを持っているにもかかわらず、

、Oの組み合わせ（N * LN（n））を乗算し、O（n）の変換は、最終的には、PythonのはO（n ^ 1.585）乗算とO（N ^ 2）よりも高速になります変換。

ほとんどの計算は10進形式で表示されるすべての結果を必要としないので、それは計算が容易になりますので、

、ほぼすべての任意精度ライブラリはバイナリ使用しています。 DecIntは、非常に小さなニッチを対象としています。十分に大きい数値の場合、DecIntは、ネイティブのPythonよりも乗算や除算のために速くなります。あなたは純粋なパフォーマンスの後にある場合でも、GMPYのようなライブラリが最速になります。

私はあなたがDecIntが役に立ったと評価してくれてうれしいます。

私の遅いノートブック上の15.9ミリ。それはあなたを減速されるプリントです。小数に進数に変換すると、それをプリントアウトする必要なステップである、非常に遅いです。あなたは出力に番号が必要な場合は、DecInt ChristopheDは、すでに述べたように試してみてください。

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桁の文字列を変換することは、すでに

〜このコンピュータ上で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

私は、あなたがちょうど約すべてのPythonの数学のツールがこれまで圧延作ったセージ数学のツールを、取得示唆します一つのパッケージに。あなたのニーズを満たすセージでの素敵な高速の任意精度数学のツールがあるかどうかを確認します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top