張貼日期：Jun 02, 2019 8:9:10 AM
作者：郭君逸 副教授（國立臺灣師範大學數學系）
基礎數學一開始就學「數數」，要會數 1, 2, 3, ⋯，接下來才能學加法，例如：8+5 就是 8 往後數 5 個…9, 10, 11, 12, 13，所以 8+5=13。但每次都這樣做建構式的加法太慢，成不了大事，於是大家就背了「九九加法表」（雖然老師沒提這個表，但事實上大家的確背了！）來快速處理一位數的加法，後來再學直式加法搭配進位，就能夠計算多位數的加法。
學習乘法也是差不多的歷程。正整數的乘法本質上就是「重複做很多次加法」，例如 6 × 4 其實就等於 6+6+6+6 或是 4+4+4+4+4+4，但很快地我們馬上就會發現這樣進行建構式的乘法，速度太慢，成不了大事，於是大家就背了「九九乘法表」來快速處理一位數的乘法，然後再學直式乘法搭配進位，來處理多位數的乘法。
加法跟乘法都可以應用到高位數，但讀者覺得，是作加法比較快，還是作乘法較快呢？
若是一位數對一位數的話，答案是一樣快。因為「九九加法表」跟「九九乘法表」我們都倒背如流了；但當「2位數加2位數」與「2位數乘2位數」來比呢？
很明顯，乘法的運算量比加法多。光直式乘法最後的 522+3480 就超越了 87+46 的加法數，何況還要做 7×6, 8×6, 7×4, 8×4 四次乘法；然後 7×6 與 8×6 也要做一個加法才能算出 522，7×4 與 8×4 也一樣。一般來說 n 位數加 n 位數，連進位都算進去的話，要做 2n-1 次一位數加法；但 n 位數乘 n 位數的話，最多會用到 2n(n-1) 的一位數加法，與 n2 次的一位數乘法。可見，乘法的運算次數是隨著位數的平方成長，所以計算乘法比較慢。
1960 年，俄羅斯的大數學家 Andrey Kolmogorov 在一次研究討論中提出他的猜測:
兩個 n 位數的乘法必須用到至少 n2 數量級的一位數乘法？
例如 2 位數乘以 2 位數必須進行 4 次一位數乘法，他認為不能再快了。結果一個禮拜後他的學生 Anatoly Karatsuba就推翻這項猜測，找到僅需 3 次一位數乘法的計算方式。以 87×46 為例，Karatsuba的方法是，先算十位相乘8×4=32，與個位相乘 7×6=42，這個部份與傳統直式乘法一樣，神妙之處在於他只用一次乘法就算出了 8×6 和 7×4 且同時把它們加起來。我們先將傳統直式乘法的步驟細分如下：
中間的綠色方框就是要計算 8×6 加 7×4，Karatsuba 巧妙的用 (8+7)×(4+6)－8×4－7×6 來達到同樣的效果。注意到，上式中只有第一個乘號要算，後兩個剛剛已經算過了，也就是說 Karatsuba 用一個加法與兩個減法向代數之神交易了一個乘法。
Anatoly Karatsuba （credited by himself)
https://en.wikipedia.org/w/index.php?curid=26804032
拿一個一位數乘法去換三個加減法值得嗎？
讀者這時可能會想說，拿一個一位數乘法去換三個加減法，又不是頭殼壞去，這樣不是反而慢嗎？
有這種直覺的讀者數感不錯，對! 也不對! 端看計算的數字規模有多大。我們先來看一下 4 位數的情況，2531×1467 一樣先算 25×14 與 31×67，然後中間的 25×67+31×14 用 (25+31)×(14+67)－25×14－31×67 計算，最後加總起來。
如同前面的分析，此處一樣用到三個二位數乘法，而每個二位數乘法又用到三個一位數乘法，所以總共用到 3×3=9 次一位數乘法。因此一般 n 位數的乘法，用這種技巧，可以只用到 3log n =nlog 3 約為 n1.58 個一位數乘法。註: 本文 log 皆以 2為底。位數越高，用到的一位數乘法量就會越接近 n1.58 的常數倍。對於人來說，把一個乘法換三個加減法，並沒有比較快，何況還要遞迴的操作；但是，對電腦而言就不是這樣了。
電腦的本質上是二進位的系統 (哪有！我用電腦這麼多年，沒看到什麼二進位啊！那是現在電腦發展很快，事實上隨便顯示一張小圖、或一個字，背後都做了數百萬次的二進位運算。)而電腦的加法是用位元的邏輯運算來達成，就是 AND, OR, XOR, NOT, Shift 這些東西來組成的，而位元邏輯運算超快，詳細我們就不說了，總之電腦的加法非常快。那電腦的乘法，真的是用 Karatsuba 的方法嗎？其實也不是，我們先來看一下 8 位元的電腦怎麼做乘法好了。以 11 乘以14 來說，化成二進位變成 00001011 與 00001110 (前面要補 0，因為 8 位元的電腦它就是用 8 個位元儲存數字。)
這不就是直式乘法嗎？這樣哪有比較快？有的。因為人類習慣十進位，所以要背「九九乘法表」；電腦用的是二進位，所以要背「一一乘法表」！！沒錯，所以等於不用背，二進位的直式乘法，其實只是被乘數的平移(如上圖所示)，然後加起來而已。換句話說，其實乘法也是一堆位元邏輯運算而已，所以也是超快的。
Karatsuba 演算法好用在數字很大很大的時候，例如尋找超大質數
那 Karatsuba 的方法用在哪呢？用在很大很大的數字相乘的時候。電腦的乘法雖快，但 8 位元電腦，最大就只能處理28 －1=255 以內的乘法，乘完後超過 255 的話就不能處理了，16 位元電腦最大可以處理到 65536 以內的數，而現在的 64 位元電腦就可以處理到……一個非常大的數，呵呵。那超過電腦能處理的數的話，到頭來，還是要用傳統的方法來處理，為了不要讓數字太大，我們以 8 位元的電腦為例，處理數字就會看成 256 進位來處理，533×499 就會變成下面這樣，所以當數字大的時候，這時 Karatsuba 的方法就有用了。
值得一提的是，當電腦硬體從 8 位元升級到 16 位元時，軟體若沒有改成 65536 進位的話，而用 16 位元電腦來存 255 以內的數，前面就會補了更多的 0，處理起反而會浪費時間。而若軟體有跟著處理成 65536 進位的話，533×499 就會變只有位元邏輯運算而已，會超快。這就是為什麼電腦硬體剛進入 64 位元時代時，軟體沒有跟上的話，執行程式反而變慢的原因。
Karatsuba 的方法，在數字大的時候的確可以加快乘法，以一千位數的乘法來說，此法的速度大約是傳統乘法的 17倍。接下來幾年之間持續有些微進展，直到 1971 年，Arnold Schönhage 與 Volker Strassen 利用快速傅立葉變換構想出目前廣為人知的 Schönhage–Strassen 演算法，將結果改進為 O(n log n loglog n)，在差不多三萬位數以上的乘法，會比 Karatsuba 方法還要快。此法也是過去數十年來大數字乘法的主流，著名的梅森質數搜尋網 (Great Internet Mersenne Prime Search，在2018年12月找到第51個) 就是用 Schönhage–Strassen 演算法來達到快速乘法。
David Harvey 與 Joris Van Der Hoeven 成功了
事隔三十幾年到了2007，Martin Fürer 再次利用快速傅立葉變換，將複雜度下降到 O(16log* n n log n)，其中log* n 是計算 n 取幾次 log 會讓這個數小於1，是一個成長很緩慢的函數，幾乎可以視為常數，因此這個接近可能最佳解 O(n log n) 的結果在當年受到相當大的矚目。不過，David Harvey 與 Joris Van Der Hoeven 對這樣的結果仍不滿意，持續研究改進 16 這個惱人的常數至 8 然後再下降到 4，直到 2019 年，終於成功證明了 Schönhage 與 Strassen 的猜測上界 O(n log n)。
大矩陣乘法的故事
值得一提的是， Strassen 除了是「大整數乘法」的始祖外，他也是「大矩陣乘法」的始祖(筆者寫到這裡，不自覺的跪了下來)。以 2×2 的矩陣來說，傳統計算下面式子時，
由於 x=ae+bg, y=af+bh, z=ce+dg, w=cf+dh，總共需要 8 次的乘法，但 1969 年，Strassen 說，先計算下面 7 個值，
然後讀者可以自行驗證 x, y, z, w 可以用這 7 個值表示。
因此他只用了 7 個乘法就完成了。天啊！這是怎麼想到的！
一般 n × n 矩陣乘法，用 Strassen 演算法只需要 O(nlog 7 ) 約等於 O(n2.8 ) 次乘法。從此大家才知道，原來矩陣乘法竟然可以比 n3 還要快，矩陣乘法的改進也有相當精彩的發展歷史，詳細就不再一一介紹了，目前最好的結果是 2014 年 François Le Gall 將指數的 2.8 改進到約 2.3728639。
不管是大整數乘法或大矩陣乘法，目前都是以 Schönhage–Strassen 演算法與 Strassen 演算法為主流，沒有採用後來看起來較好的方法主因是後來的方法太複雜，且要在很大很大很大的整數(矩陣)執行，效能才會比較好，已經超越了人類目前所需要的計算尺度。另一方面，電腦硬體的發展快速，會直接把這些演算法寫到晶片，變成指令集，讓程式直接呼叫，甚至是多條相同的指令可以平行處理，經由硬體的加速，乘法的速度已經超越了演算法改進的速度（尤其是矩陣的乘法）。不過只要還沒達到最佳解，相信數學家們都還是會繼續為超快速乘法的運算極限而努力。
參考文獻
1) A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281–292, 1971.
2) M. Fürer. Faster integer multiplication. In Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing, STOC 2007, pages 57–66, New York, NY, USA, 2007. ACM Press.
3) David Harvey, Joris Van Der Hoeven. Integer multiplication in time O(n log n). 2019. hal-02070778