2011-09-18 46 views
6

Karatsuba's 2-split multiplicationをPythonで実装したいと思います。しかし、書式で数値を書くと、xは基底(x = b^m)をsqrt(A)に近似した次の累乗である。karatsubaの乗算に関する質問

除算と乗算を使用することができない場合は、どうすればxを見つけることができますか?桁数を数え、Aを桁数の半分だけ左にシフトする必要がありますか?

ありがとうございました。

+1

特にb = 2の場合は? (一般化されたbより簡単です) – smci

+0

Pythonのlongの乗算はKaratsubaの乗算を内部的に使用していますか?あなたはいくつかのアイデアが必要な場合は、常にPythonのソースを見て回ることができます。 –

答えて

4

ほぼ。あなたはAの数字を半分の数字でシフトしません。もちろん、これは基数が2の累乗である場合にのみ効率的です。なぜなら、基数10の "シフト"(例えば)は乗算で行われなければならないからです。

Python 3.1以降を使用している場合は、ビット数を数えるのは簡単ですが、それ以外の場合は、 3.1がint.bit_length()メソッドを導入したためです。 Pythonの他のバージョンでは、Aをコピーして0になるまでビット数を数えることができます。これはバイナリ検索メソッドの一種でO(log N)時間(N =桁数)で行うことができます。私はこれを書き始めたので、多くのビット、それは0だならば、それはあまりにも多くいたが、その他

+0

情報ありがとう!私は基盤2のためにそれに取り組んでいます。それはすべてうまくいくと思います。準備ができたら解決策を投稿します。 – kaiseroskilo

+0

int.bit_length()メソッドは、Python 2.7でも利用できます。 – casevh

3

は、あなたはすでに答えを受け入れ、しかし:トムは言った

何: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) 
2

ご質問は、すでにあなたが呼ばれた記事に答えている:「カラツバの基本的なステップは、任意のベースBのために働きます任意のMが、再帰的なアルゴリズムは、あるn ...「切り上げMはN/2に等しい場合に最も効率的で役立つかもしれない桁数、および0 < = value_of_digit < B.

一部透視:

あなたは許可されています(必須です)小計number_of_digits // 2divmod(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を入力パラメータとして、数字を数字のリストとして表現することができます。