圖姆-庫克演算法

圖姆-庫克演算法，有時也被稱為Toom-3演算法，由安德魯·圖姆命名，他提出了這種演算法的基本原理，而斯蒂芬·庫克則最先用簡潔的形式描述並改進了這種演算法，將其作為大整數的乘法演算法。圖姆-庫克演算法的原理是：對於給定的兩個大整數formula_1和formula_2 ，將formula_1和formula_2分成formula_5個較小的部分，每個部分的長度為formula_6 ，並對這些部分執行運算。隨著formula_5的增長，可以組合許多乘法子運算，從而降低演算法的整體複雜度，然後再次使用圖姆-庫克演算法遞迴計算乘法子運算，依此類推。Toom-3和圖姆-庫克兩個術語有時會被錯誤的混用，但事實上Toom-3只是圖姆-庫克演算法在formula_8時的特例。Toom-3將9次乘法降低至僅需5次，使其在formula_9的時間裡執行。通常，Toom-formula_5的時間複雜度為formula_11 ，其中formula_12。formula_13是在乘法子運算上花費的時間，formula_14則是花費在對小常數進行的加法和乘法運算上的時間。著名的Karatsuba演算法實際上是圖姆-庫克演算法的特例，在Karatsuba演算法中，原始乘數被拆分成兩個較小的數，而原本的4次乘法運算縮減為3次，使之在formula_15的時間內完成運算。Toom-1等價於普通的長乘法，具有formula_16的複雜度。儘管可以透過增加formula_5來使指數formula_18任意接近1，但函式formula_14增長速度非常快。混合級別圖姆-庫克演算法的增長率直到2005年仍然是一個廣為研究的開放性問題。根據高德納所描述演算法的一種實現，其複雜度可降低至formula_20。由於工作時的開銷，當乘數包括較小的數時，圖姆-庫克演算法會比長乘法更慢，因此它適用於中等規模的乘法。對於更大規模的資料，則有漸進更快的史恩哈格·施特拉森演算法。這一演算法由安德魯·圖姆1963年首次描述，並在斯蒂芬·庫克1966年的博士學位論文中得到漸進等效的改進。細節.本節將討論對於任意給定 formula_5 值， Toom-formula_5究竟是如何運作的，這是馬可·波德拉託對圖姆-庫克多項式乘法的簡化描述。這個演算法包括五個主要步驟：在典型的大整數實現中，每個整數都表示為formula_2進位制的數字序列。設要相乘的兩個大整數formula_29 、 formula_30分別是：這對乘數實際上比圖姆-庫克演算法通常要處理的資料小很多，在此使用學校裡學習的普通乘法可能會更快，但這個示例仍有助於說明圖姆-庫克演算法的工作原理。拆分.第一步是選擇基數formula_31，使得兩個數字formula_29和formula_30可以分成formula_5段大小不超過formula_35的數字。formula_36常常根據如下公式求得：formula_37我們的示例將演繹Toom-3演算法的運算過程，因此確定formula_38，接著把formula_29和formula_30拆分為3段，即formula_41和formula_42，則有：formula_43然後，我們把這些數作為formula_44階多項式formula_45和formula_46的係數，with the property that formula_47 and formula_48：formula_49formula_50定義這些多項式的目的在於：如果計算出它們的乘積formula_51，我們的答案就會是formula_52。如果乘數位數不同，對於formula_29、formula_30分別取不同的formula_5值十分有用，我們將其稱為formula_56和formula_57。例如，演算法“Toom-2.5”是指formula_58且formula_59時的圖姆-庫克演算法。這時formula_31中的formula_36通常被確定為：formula_62求值.圖姆-庫克演算法包含一種常用的方法，來計算多項式formula_63、formula_64的乘積。注意，次數為formula_65的多項式可以透過formula_66個空間中的點確定。這個方法是在各個點上求值formula_67和formula_68，然後把這些點相乘以獲得多項式乘積上的點，最後進行插值以找到其係數。由於formula_69，我們將需要formula_70個點來確定最終結果formula_65。在Toom-3的情況下，formula_72。無論選擇什麼點，該演算法都可以工作，但為了簡化演算法，最好選擇較小的整數值，例如formula_73 、formula_74 、formula_75和formula_76。無窮大是一個常被使用的不尋常點，其記作formula_77或formula_78。求多項式formula_45在無窮大時的值，實際上意味著令formula_80的上限為formula_81 且趨向無窮大。因此，formula_82總是其高階係數的值。在我們的Toom-3示例中，我們將使用點formula_73 、 formula_74 、 formula_75 、 formula_76和formula_77，這些選擇簡化了求值，如下式子：formula_89對於formula_46也是如此。在示例中，我們得到的值是：如上所示，這些值可以包括負值。為了下文的闡述，把這個求值過程視作矩陣向量乘法較為有用。其中，矩陣的每一行都包含求值點之一的冪，且向量包含多項式的係數：formula_91The dimensions of the matrix are  formula_65 by  formula_56 for  formula_45 and  formula_65 by  formula_57 for  formula_46。除最後一列的 formula_74 以外，無窮大的行總是formula_73。更快的求值.與上述公式相比，多點求值可能會減少基本運算：此序列需要進行五次加/減運算，比簡單求值少一次，同時節省了在計算formula_101時乘以formula_102的開銷。點乘.與對多項式formula_67和formula_68所進行的乘法不同，將formula_105 和formula_106被求出的值相乘僅涉及整數相乘——這是原始問題的較小例項。我們遞迴呼叫我們的乘法過程來使每對已求值的點相乘。在實踐中，隨著乘數減小，演算法將逐漸過渡為教科書長乘法。令formula_107為多項式乘積，我們將得到：如上所示，這些值也可以是負數。對於足夠大的數值，這裡是最昂貴的、唯一與formula_29、formula_30大小不成線性關係的步驟。插值.這一步最為複雜。與求值相反：給定多項式乘積formula_110上的formula_65點，我們需要確定其係數。換句話說，我們要在右側求解其向量的矩陣方程：formula_112此矩陣的構造與求值步驟中的矩陣相同，不過它是formula_113的。我們可以用高斯消元法來求出方程的解，但這樣非常昂貴。根據以下事實：只要求值點的選擇合適，這個矩陣就是可逆的。因此我們有：formula_114接下來即要求得該矩陣的向量積。儘管矩陣中包含分數，但所得的係數卻是整數——因此所有這些都可以在整數算術中完成，僅僅是與小常數進行加減乘除。圖姆-庫克設計時面臨的一個困難挑戰就是找到有效的操作順序來計算該乘積。下面是波德拉託為Toom-3找到的一組順序，透過上面的示例演示：現在我們知道多項式乘積formula_107：formula_116如果我們使用不同的formula_56、formula_57或求值點，矩陣和我們的插值將改變。但是它不依賴於輸入，因此可以對任何給定的引數集進行硬編碼。重組.最後，我們將求出formula_119的值以獲得最終結果。很顯然，由於formula_35是formula_2的冪，因此對formula_35的冪的乘法同樣也可以應用於所有以formula_2為底數的數值。在這個示例中，formula_124且formula_38。這實際上是formula_126與formula_127的乘積。formula_5在其他取值時的插值矩陣.這裡我們給出了幾種formula_56和formula_57取常見較小值的插值矩陣。Toom-1.Toom-1需要一個求值點，這裡選擇formula_73。它退化為長乘法，並且使用恆等矩陣的插值矩陣。formula_133Toom-1.5.Toom-1.5需要兩個求值點，這裡選擇formula_73和formula_77，且其插值矩陣就是恆等矩陣。formula_137這裡亦退化為長乘法：一個因數的兩個係數都乘以另一個因數的兩個係數。Toom-2.Toom-2需要三個求值點，這裡選擇formula_73、formula_74和formula_77。它與 Karatsuba 演算法相同，其插值矩陣為：formula_142Toom-2.5.Toom-2.5需要四個求值點，這裡選擇formula_73、formula_74、formula_75和formula_77。它的插值矩陣為：formula_148