不瞞你説，我有特殊的算數技巧~_風聞
中科院物理所-中科院物理所官方账号-2019-10-02 13:26
原創：中科院物理所
作者：Patrick Honner
翻譯：Nuor
審校：重光
跟你計算乘法的方式不同，計算機使用了更快的乘法算法。
今年夏天，熱榜上被一個簡單的數學問題刷屏：8÷2(2+2)=?
如果先用8除以2你會得到16；如果先用2乘(2+2)，會得到1。所以，那個結果是對的？這個問題的分歧很大以至於上了紐約時報的新聞。正如部分評論所言，即使是專業的數學家也無法將這兩者統一。
問題的關鍵是我們如何理解除法的含義。“÷”意味着其作用於後面的一位數字還是後面的所有數字與符號？對於數學家們來説，由於他們不常使用這個運算，所以這個不是很重要。如果讓他們解這個問題，他們可能僅僅將其視為一個乘法運算，一旦將其寫為：
分歧就消失了，結果顯而易見。作為一個乘法問題，這個問題不會出現什麼別的問題。
但是數學家們發現的有關乘法的有趣的事情可能會使你驚訝：計算乘法最好的方法是什麼？
假如讓你來計算25乘以63。如果你跟大多數人一樣的話，你可能打開你的計算器來運算。但是如果你手頭上找不到的話，你可能會用你在小學學到的數的基本運算來計算：用一個數乘以兩位數然後另一個數乘以兩位數最後相加得到結果：
倘若你擅長心算的話，你可能利用乘法分配律來使運算更加簡單：
評估計算機算法效率是很複雜的，但我們可以根據兩個假設利用一種簡單的方法來評估。第一個假設是：兩個大數的乘法總可以分解為一系列小的數的乘法和加法運算。第二個假設是：對大多數計算機而言，小的數的加法比乘法運算快很多。所以當評估乘法算法的效率時，我們最關心的是小的數的乘法運算。
考慮到效率，重新來看25×63的乘法運算。為了利用標準算法來計算25×63，我們可以執行四個小的乘法：3×5，3×2，6×5，6×2，小的乘法給出的額四個結果是：15，60，300，1200，加起來是1575。需要注意的是，利用標準算法，3×2其實是3×2×10=60，6×5其實是6×10×5=300，6×2其實是6×10×2×10=1200。但是，考慮到算法的效率，計算時不考慮10的作用。計算機的乘以10的操作跟人是一樣的，只需要將數字整體左移動一位，同理，乘以100，1000也是同樣的道理。
因此，我們計算25×63只需要四個小的乘法和一些加法。乘法分配律呢？
在計算25×60時，需要用2和5乘6，在25×3時，需要用2和5乘3，仍然是四個小的乘法。因為兩種方法都需要四個小的乘法，因此在效率上，他們是等價的。因此，標準的乘法運算只是乘法分配律的一個應用，這不足為奇。讓我們來看看原因。
考慮兩個隨機的兩位數的乘法‘AB’和‘CD’。這裏用單引號裏的符號代表一個數：‘AB’的十位數是A，個位數是B。另一方面來説，‘AB’是10A+B，意味着，如果‘AB’為25的話，A是2，B是5。如果‘CD’是63的話，C是6，D是3。
為了求解‘AB’和‘CD’的乘積，需要兩個數字相乘：10A+B和10C+D。我們可以通過兩次****乘法分配律來計算：
如果我們用標準的乘法運算來計算的話，過程類似於這樣：
值得注意的是，所有標準的乘法運算的步驟都類似，所不同的是它們的順序不同。就效率而言，在這種情況下都有相同的乘法部分：3×5，3×2，6×5和6×2。因此這兩個方法在本質上是一樣的。每種方法都要做：A×C，A×D，B×C和B×D的步驟。這四個小的乘法定義了乘法效率的極限。
但是1960年，俄羅斯的數學家阿納託利·卡拉蘇巴發現了另外一種極限，利用他自己的分配率找到了另一種更加高效的乘法方式。卡拉蘇巴注意到，計算‘AB’和‘CD’的乘積所需的所有四個小的乘法都是在我們將它們的數字之和‘A+B’和‘C+D’相乘時出現的：
這四個小的乘法之和不是我們所求的結果，但是卡拉蘇巴可以利用其得到我們的結果。
卡拉蘇巴在計算‘AB’בCD’時，首先計算兩個小的乘法：A×C和B×D。這是最終結果的百位數(A×C)和個位數(B×D)。（這裏可能有加法進位，但是記住，加法比乘法快很多。）不考慮加法進位，就得到我們想得到的四項中的兩項：
完成整個乘法運算，需要：
所以還需要10(A×D)和10(B×C)。卡拉蘇巴聰明的小技巧就可以用上了。我們可以重新排列下式：
得到：
我們需要計算的10(A×D)+10(B×C)和10(A×D+B×C)一樣，所以可以在上式左右兩邊乘以10得到：
乍一看，這個似乎並沒有很大的改善，我們只是把有兩個乘法的運算：10(A×D+B×C)變成三個乘法的運算：10((A+B)×(C+D)-A×C-B×D)。但是卡拉蘇巴最終的目的是使得計算變得更加容易，更加高效。方法的關鍵是我們不需要再次計算A×C和B×D：這些是之前已經算過了的，是已知的！
前面我們用兩個小的乘法——A×C和B×D以及一個小的乘法(A+B)×(C×D)——來替代A×D和B×C。這代表我們能通過三個小的乘法：A×C，B×D以及(A+B)×(C+D)來計算‘AB’בCD’。
如何更快地計算大數的乘法
傳統的25×63計算：需要四個個位數的乘法以及一些加法。
卡拉蘇巴的方法：需要三個個位數的乘法以及一些加減法。
乘法的效率
隨着數字尺度的增加，卡拉蘇巴的方法能夠不斷重複使用，將大的數變成小的，從而節省更多的個位數乘法。
傳統的乘法計算：2531×1467需要16個個位數的乘法：
卡拉蘇巴的方法計算2531×1467需要9個個位數的乘法：
對於只是單純地計算25×63的乘法，你可能並不想只是為了節省一個乘法運算而使用卡拉蘇巴的方法。這個方法需要更多的加法，(A+B)×(C+D)也不是很小。（不過，想想看，A+B或者C+D的最大值也不會比個位數大多少。）重要的是，在乘以非常大的數時，比如計算機使用數字技術對秘密信息或者敏感信息進行加密和解密時，這些小的權衡取捨加起來就會在速度上有很大的提高。
比如説，假如我們需要計算兩個四位數的乘法，像是1234和5678。傳統的計算方法需要一個數字的每一位乘以另一個數字的每一位，一共需要4×4=16次小的乘法。但是卡拉蘇巴的方法可以很容易地減少這個乘法：把1234看做12×100+34，把5678看做56×100+78，利用分配律，可以得到：
這需要四對兩位數的乘積，每對需要四個小的乘法。但是通過卡拉蘇巴的方法，可以將兩位數的乘積減少到三個小的乘法，總共是12次。而這僅是一個開始，隨着卡拉蘇巴方法的進一步應用，可以減少更多的乘法步驟，從而更多地節省內存。
當利用傳統的方法將兩位數相乘時，我們需要n×n=n2個小數乘法（第一個數字的每個數乘以第二個數字的每個數），但利用卡拉蘇巴方法可以只需要大概n1.58個乘法。隨着數字的增多，這兩種方法的差異越來越大。用傳統的方法乘以兩個10位數需要10×10=100的小的乘法，但是卡拉蘇巴只需要101.58=38個小的乘法，減少了62%的運算。對於兩個100位的數字，分別是1002=10000和1001.58≈1445，運算減少了85%！
在算小數時，你可能不會使用這種算法。但是在乘以大數時，卡拉蘇巴的方法是一個很大的進步。自從1960年，卡拉蘇巴開啓了快速乘法的大門之後，數學家們就利用了先進的技術比如説傅立葉變換創造了新的速度記錄。這種方法將乘法的問題轉換為了乘法多項式的問題，從而指向了更加令人驚訝的更快的算法，計算機至今還在使用這種算法。這些改進在今年早些時候達到了頂點，兩位研究人員驗證了一個近有50年曆史的關於乘法的最大效率的猜想，最終解決了最快乘法的問題。
但是，你如何做乘法運算的問題依然是開放的。瞭解你的算法，選擇最適合你的算法。記住，乘法不是一種競賽，除非你想創造一個新的速度記錄。
原文來源：https://www.quantamagazine.org/the-math-behind-a-faster-multiplication-algorithm-20190923/
互動問題
【互動問題：假如計算機和人的算力大幅度提升，會對你的生活產生什麼影響？】