4

Pythonで数万桁の数字を扱っています。long 型は、これらの数値に対して計算を実行する際に美しく機能しますが、これらの数値の最上位桁に十分に高速な方法でアクセスすることはできません。数字に含まれる桁数が正確にはわからないことに注意してください。「最上位の桁」とは最上位の桁を指し、最下位の桁はモジュラスを使用してすばやくアクセスできます。

Python でこれらの数字にアクセスするには 2 つの方法が考えられますが、どちらも私の目的には遅すぎます。文字列に変換し、配列メソッドを介して数字にアクセスしようとしましたが、10,000 桁以上の場合、型変換が遅くなります。または、単純にビットをマスクして切り捨てることもできますが、これには long の桁数を知っている必要があります。long の桁数を見つけるには、カウンターとマスク テストのループが必要です。これは、文字列変換よりも確実に遅くなります。

ここの説明から、long 型には実際には bignum 配列が含まれているようです。long を格納する基になるデータ構造にアクセスしたり、基本型から long の桁数を確認したりする方法はありますか?

人々が興味を持っている場合は、ベンチマークの例を提供できます。

4

3 に答える 3

7

長いタイプの低レベルの実装を掘り下げることなく、単純なアプローチ：

>>> n = 17**987273 # 1.2 million digits number

>>> digits = int(math.log10(n))

>>> k = digits - 24 # i.e. first 24 digits

>>> n / (10 ** k)
9953043281569299242668853L

私のマシンでは非常に高速に実行されます。この数値の文字列表現を取得しようとしましたが、非常に時間がかかります。

Python 3.xの場合、n // (10 ** k)

この大きな数のいくつかのタイミング（140倍高速です）：

%timeit s = str(n)[:24]
1 loops, best of 3: 57.7 s per loop

%timeit n/10**(int(math.log10(n))-24)
1 loops, best of 3: 412 ms per loop


# With a 200K digits number (51x faster)

%timeit s = str(n)[:24]
1 loops, best of 3: 532 ms per loop

%timeit n/10**(int(math.log10(n))-24)
100 loops, best of 3: 10.4 ms per loop


# With a 20K digits number (19x faster)

%timeit s = str(n)[:24]
100 loops, best of 3: 5.4 ms per loop

%timeit n/10**(int(math.log10(n))-24)
1000 loops, best of 3: 272 us per loop
于 2012-11-25T01:16:24.710 に答える
3

Python 2.7には、bit_length()整数に関するメソッドがあります。

于 2012-11-25T01:19:00.790 に答える
1

以下は、最初の数桁の 10 進数を抽出する非常に醜いワンライナーです。

(x >> (x.bit_length()-50))*(10**(math.fmod((x.bit_length()-50)*math.log(2)/math.log(10), 1)))

x の値が 10 進数で約 10,000 桁の長さである場合、約 12 桁程度の正確な答えが得られるはずです。x が大きくなると、精度が低下します。

外部モジュールを使用する場合は、gmpy2を参照してください。gmpy2 ライブラリは、多倍精度整数および小数演算用の GMP (または MPIR) ライブラリ、多倍精度浮動小数点演算用の MPFR ライブラリ、および多倍精度複素演算用の MPC ライブラリへのアクセスを提供します。gmpy2 整数は、Python のネイティブな long よりも高速であり、long 整数を浮動小数点数に変換して、先頭の数字だけを抽出できます。上記のライナーは次のようになります。

gmpy2.mpfr(x).digits()[0]

gmpy2 アプローチは、数値が大きくなっても精度を維持します。

免責事項: 私は gmpy2 を保守しています。

于 2012-11-25T02:44:00.933 に答える