關於karatsuba乘法的問題

我想在Python中實現Karatsuba's 2-split multiplication。然而，寫入數字的形式爲關於karatsuba乘法的問題

A=c*x+d

其中x是基數（let x = b^m）接近sqrt（A）的冪。

我該如何找到x，如果我甚至不能使用除法和乘法？我是否應該計算位數並將A左移數位的一半？

謝謝。

來源

2011-09-18 kaiseroskilo

特別針對base b = 2？（比普通b更容易） – smci

你知道python中longs的乘法在內部使用Karatsuba乘法嗎？如果你想要一些想法，你總是可以眯着眼睛看蟒蛇的來源。 –

差不多。你不要把A移位數字的一半;當然，如果基數是2的冪，則這是唯一有效的，因爲基數10（例如）中的「移位」必須用乘法完成。（編輯：好吧，你好，可以乘以移位和加法，但它的功能更加簡單。）

如果你使用的是Python 3.1或更高版本，計數位很容易，因爲3.1引入了int.bit_length()方法。對於其他版本的Python，可以通過複製A並將它右移直到它爲0來計數位。這可以在O（log N）時間（N =數位數）中用一種二進制搜索方法完成 - 許多位，如果是0，那麼這是太多了，等

來源

2011-09-18 13:36:34

感謝您的信息！我正在爲基地工作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。

首先我們通過二進制搜索得到n位移。（真的，我們只需要n/2，所以這是不必要的最後一次迭代）。後來，當我們ň知道，獲得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)

來源

2011-09-18 14:22:27 smci

你的問題的文章中已經回答到你提到：「Karatsuba的基本步驟適用於任何鹼B和任何米，但遞歸算法是最有效的，當m是等於N/2，向上取整」 ... n是可能幫助的位數，和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中的實現來實現什麼，它使用B == 2，數字由Python ints表示，在C中的實現已經使用Karatsuba算法來乘以足夠大的數字讓它值得。它不可能是速度。

作爲一種學習練習，您可能想嘗試將數字表示爲數字列表，其中基數B是輸入參數。

來源

2011-09-19 00:20:01

關於karatsuba乘法的問題

回答

相關問題