Toom-Cook乘法算法實現

我有一個任務來實現Toom-Cook 3-way乘法算法。我正在關注維基百科http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication的描述，並且我設法將兩個大數字存儲到字符串中，並根據維基百科頁面上的「拆分」步驟將字符串拆分爲較小的數字。下一步是「評估」，我必須計算一個新的數字p0 = m0 + m2（Bordrato的「快速評估」 - 可在同一頁上找到），其中m0和m2是我通過分割大數字創建的數字（在前面的步驟中）。問題是我不能簡單地加上m0和m2，因爲這兩個數字仍然很大，不可能以標準方式加在一起。這是否意味着我必須實現我自己的算法來添加大量數據（以及減少和分割，因爲它們也是需要的），還是我錯過了一些東西？如果任何人都可以鏈接我一個可能的實現，甚至一個僞代碼，這將不勝感激。Toom-Cook乘法算法實現

來源

2013-05-08 Marko

加兩個大整數非常簡單。添加和運載，添加和運載，添加和運載...減法同樣容易。 Division稍微強硬一些，但它基本上只是在陣列上進行長時間的劃分。 – Patashu 2013-05-08 00:28:37

我假設你說你存儲的字符串中的數字，你的意思是一些適當的大k（如32）基數2^k數字的數組。使用字符串會很愚蠢。對於bignum操作，爲什麼不使用像'gmp'或者'mini-gmp'這樣的已建立的C庫？ – Gene 2018-01-02 01:06:25

@Gene你是什麼意思的「基數2^k數字數組」？你能給個例子嗎？ – Marko 2018-01-02 02:36:28

LibTomMath是開源的，包含Toom-Cook乘法;看一看。

來源

2013-05-08 00:37:08

難以閱讀所有的在線錯誤處理。 – greybeard 2018-01-01 19:04:07

你必須實現你自己的方法，用於加，減，模等等。前一段時間我試圖實現一個BigInteger庫，我發現了一些可能對你有用的資源。

BIGNUM數學書（如指出由以前的答案）
的Java OpenJDK的 BigInteger implementation，與文檔
算法和數據結構的基本工具箱，（我認識到這本書的Karatsube）。

順便說一下，我建議您使用base 2作爲您的號碼（see here.），因爲您可以利用計算機的性質使您的操作更加輕鬆快捷。

來源

2013-05-08 03:16:36 rendon

Toom-Cook乘法算法實現

回答

相關問題