Karatsuba's 2-split multiplicationをPythonで実装したいと思います。しかし、書式で数値を書くと、xは基底(x = b^m)をsqrt(A)に近似した次の累乗である。karatsubaの乗算に関する質問
除算と乗算を使用することができない場合は、どうすればxを見つけることができますか?桁数を数え、Aを桁数の半分だけ左にシフトする必要がありますか?
ありがとうございました。
Karatsuba's 2-split multiplicationをPythonで実装したいと思います。しかし、書式で数値を書くと、xは基底(x = b^m)をsqrt(A)に近似した次の累乗である。karatsubaの乗算に関する質問
除算と乗算を使用することができない場合は、どうすればxを見つけることができますか?桁数を数え、Aを桁数の半分だけ左にシフトする必要がありますか?
ありがとうございました。
ほぼ。あなたはAの数字を半分の数字でシフトしません。もちろん、これは基数が2の累乗である場合にのみ効率的です。なぜなら、基数10の "シフト"(例えば)は乗算で行われなければならないからです。
Python 3.1以降を使用している場合は、ビット数を数えるのは簡単ですが、それ以外の場合は、 3.1がint.bit_length()
メソッドを導入したためです。 Pythonの他のバージョンでは、Aをコピーして0になるまでビット数を数えることができます。これはバイナリ検索メソッドの一種でO(log N)時間(N =桁数)で行うことができます。私はこれを書き始めたので、多くのビット、それは0だならば、それはあまりにも多くいたが、その他
情報ありがとう!私は基盤2のためにそれに取り組んでいます。それはすべてうまくいくと思います。準備ができたら解決策を投稿します。 – kaiseroskilo
int.bit_length()メソッドは、Python 2.7でも利用できます。 – casevh
は、あなたはすでに答えを受け入れ、しかし:トムは言った
何:Pythonの3.xの中で、あなたは、n = int型得ることができます.bit_length()を直接呼び出します。 Python 2.xでは、以下のようにバイナリ検索でO(log2(A))時間でnを取得します。
両方を計算するコードは(2.x)です。 xの基数2の指数をn、すなわちx = 2 ** nとする。
まず、シフトすることによって2進検索でnを得る。 (実際にはn/2だけが必要なので、不要な最後の1回の繰り返しです)。 はその後、我々がn知っているとき、X、Cを取得し、dは(まだ使用して除算)簡単です
def karatsuba_form(A,n=32):
"""Binary-search for Karatsuba form using binary shifts"""
# First search for n ~ log2(A)
step = n >> 1
while step>0:
c = A >> n
print 'n=%2d step=%2d -> c=%d' % (n,step,c)
if c:
n += step
else:
n -= step
# More concisely, could say: n = (n+step) if c else (n-step)
step >>= 1
# Then take x = 2^(n/2) ˜ sqrt(A)
ndiv2 = n/2
# Find Karatsuba form
c = (A >> ndiv2)
x = (1 << ndiv2)
d = A - (c << ndiv2)
return (x,c,d)
ご質問は、すでにあなたが呼ばれた記事に答えている:「カラツバの基本的なステップは、任意のベースBのために働きます任意のMが、再帰的なアルゴリズムは、あるn
...「切り上げMはN/2に等しい場合に最も効率的で役立つかもしれない桁数、および0 < = value_of_digit < B.
一部透視:
あなたは許可されています(必須です)小計number_of_digits // 2
とdivmod(digit_x * digit_x, B)
...のような演算で、Bが10の場合、divmod(9 * 8, 10)
が(7, 2)
を生成することを知る必要があります。
コンピュータで大規模な算術演算を実装する場合、Bを基本乗算演算を便利にサポートする2の最大乗数にするのが通常です。たとえば、32ビットマシン上のCPython実装では、Bは2 ** 15(つまり32768)になるように選択されます。これは、product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF;
がオーバーフローなしで、符号ビットを心配することなく動作するためです。
Python intsで表される数値で、B == 2を使用するPythonでの実装で達成しようとしていることはよく分かりません。Cでの実装では、Karatsubaアルゴリズムを使用して、それを価値あるものにする。それはスピードではありません。
学習の練習として、ベースBを入力パラメータとして、数字を数字のリストとして表現することができます。
特にb = 2の場合は? (一般化されたbより簡単です) – smci
Pythonのlongの乗算はKaratsubaの乗算を内部的に使用していますか?あなたはいくつかのアイデアが必要な場合は、常にPythonのソースを見て回ることができます。 –