地表最速乘法傳說！碰到大得要命的數字，這是最快的乘法方式

非阿貝爾理論

量子色動力學與弱核力理論有個更為奇特的性質，兩者都是「非阿貝爾理論」 （non-Abeliantheories）。非阿貝爾的意思是強核力與弱核力理論核心（參見【科學解釋 6】）的對稱群代數是不可交換的。簡單來說就是「A 乘 B」不等於「B 乘 A」。

一般人的常識會告訴你，如果隨便拿兩個數字 A 和 B，用 A 乘 B 的結果永遠會和用 B 乘 A 一樣，你用計算機怎麼試答案都不變。一個袋子裝三塊錢、兩個袋子總共是六塊錢；一個袋子裝兩塊錢，三個袋子總共還是六塊錢。

這件事對數字永遠都成立，是千真萬確的事實。然而，我們有個很好的方法能定義出一套數學架構，其中的 AB 不等於 BA。實際上，數學家已經鑽研這個領域很多年了。

條條大路通數學

或許更驚人的是，物理學家竟然也在許多地方應用這套數學，因為某些和物理學相關的事物也是 AB 不等於 BA。矩陣就是我們表示這些東西的一種方式。現在我在倫敦大學學院為新生上的數學方法課就有介紹矩陣力學。以前我的學校制定了一套「新數學」的課綱，所以我在年僅十五歲的時候就多少認識一點矩陣了。

數學的一個矩陣是一群按照行列排列整齊的數字。把兩個矩陣 A 和 B 相乘，會得到另一個矩陣 C，方法是把對應的列和行上面的數字依序相乘。

這種矩陣聽起來可能不像某部電影裡面那掌控一切、創造虛擬實境的超級電腦一樣迷人，卻有用的多。這部電影的角色身穿黑色皮衣，還有出現著名的慢動作躲子彈鏡頭^＊。

我來舉個例子。

你可以用一個矩陣來描述你移動某個物體的結果。相乘的順序（AB 或 BA）在這個例子有明顯的區別。物體先在原地轉九十度再向前直直走十公尺，和先走十公尺再轉九十度，兩種移動方式最後的終點顯然不會相同。假設矩陣B代表旋轉，矩陣 A 代表直行，那麼合在一起的「旋轉後直行」就是矩陣（C = AB）；這和「直行後旋轉」的矩陣（D = BA）必定不會相同。C 不等於 D，所以 AB 不等於 BA。要是 AB 和 BA 永遠相同，我們就沒辦法用矩陣來描述這類的移動過程了。正是因為矩陣的乘法不可交換―非阿貝爾，這個工具才會如此有用。

數學和真實世界密不可分

在狄拉克試圖要找出能描述高速電子的量子力學方程式時，矩陣被證實是他所需要的工具。實際上，電子有某項特性讓狄拉克不得不使用矩陣來表示它，這項特性與他描述電子自旋的語言同出一轍；所有原子的行為和元素周期表的規律，都與自旋有深刻的關聯。除此之外，這個性質也啟發狄拉克去預測有反物質的存在。

數學和真實世界之間似乎有緊密的關係，這讓我讚嘆不已。優秀的研究要能解決問題、也要能提出好的問題。而問題永遠比解答還要多，為了研究我們要付出許多的時間和金錢，因此大家得做出抉擇。數學是威力極大的工具，能幫助科學家檢查實驗數據、並從結果當中尋找最有趣的新實驗方向。就算有些方法和結論，好比矩陣及反物質，看起來可是相當古怪的。

秉持著這份精神，我要在繼續討論希格斯粒子搜索實驗之前，先繞個路來講微中子，最後這回要介紹的是一個很重要的真實結果。2012 年 3 月 7 日，中國的大亞灣核反應爐微中子實驗（DayaBay Reactor Neutrino Experiment）發表了最新的研究成果。

他們的實驗結果不但對標準模型影響重大，也會決定粒子物理學未來的研究走向。如果你只想要繼續讀希格斯粒子的故事，大可跳過這一段沒關係，下一節再見。但是微中子的粉絲可千萬別錯過精彩好戲了！

——本文摘自《撞出上帝的粒子：深入史上最大實驗現場》，2022 年 12 月，貓頭鷹出版，未經同意請勿轉載。

文／郭君逸｜數學科普 Unimath 網站作者，國立台灣師範大學數學系助理教授、魔術方塊收藏家

這是一張從高鐵網站下載的票價表。眼前除了一堆數字之外，你還注意到哪些數學呢？

「矩陣！」

對的，你的觀察很正確。矩陣是大學線性代數這門課裡的主角，線性代數和微積分兩者並列為一窺高等數學的計算基礎，因此除了自然科學領域的學生強迫必修，甚至一些社會科學領域的學生也需要修讀，例如經濟、商管······等。聽起來或許有點恐怖，不過別緊張，撇開複雜的計算，單純矩陣表示法其實是生活中蠻常見實用的技巧，可以做為一群事物中兩兩彼此之間的關聯表格。像是上圖高鐵票價關係就是「起」「訖」點間的票價關係，還有各種比賽中選手或球隊彼此間的勝負關係。

這張圖右上半部是半價的優待票，以下討論我們只要看左下半部的全票即可。不知道讀者有沒有發現，「彰化→左營」的票價原本是 670 元，但「彰化→嘉義 250 元」加上「嘉義→左營 410 元」卻是 660 元，分開買居然可以省 10 元！？

是不是一直把票分段買，就可以越來越便宜呢？

其實並非如此！

例如「嘉義→左營」是 410 元，但改成「嘉義→台南 ＋ 台南→左營」兩段票的話，會變成 420 元，反而變貴了。

為什麼會有這種現象呢？

首先我們先來研究一下高鐵的票價訂法。政府每年會先用「消費者物價總指數（GICP）」來訂定每人的基本消費率，交通部把基本消費率乘以 1.2 當作高鐵的基本費率（2016 年）的基本費率是 4.386 元／人公里。（註：詳細計算方式請參閱：交通部高速鐵路工程局常見問答集或高鐵票價調整案說明專區）

而台北到左營站的距離為 339.284 公里，所以 4.386 * 339.284 = 1488.099 元/人，四捨五入到十位，所以才變成了 1490 元。問題就出在四捨五入的部分，1488 若拆成兩段 744 的話，四捨五入都變成 740，總合就是 1480 省了 10 元。相反地，如果 534 拆成兩個 267 的話，四捨五入後就會多出 10 元。

拆票的時機

那到底要什麼時候要拆票，什麼時候不拆呢？這是個很麻煩的問題，只能夠用暴力法，把所有情況都試過，才會知道。這時手算實在太累，我們要藉助電腦的幫忙了。但「暴力法」只是個大方向，實際要如何使用「暴力」，巧妙各有不同。

此類的問題，我們通常會用「動態規劃」（Dynamic Programming），這是一種「用空間換取時間」的概念來寫程式讓電腦幫我們解決問題的方法。當然這細節並非一時一刻可以講的清楚的。不過，教電腦如何解決問題就是數學！若我們可以把生活上遇到的難題（尤其是需要重複操作的動作），跟所學結合，很多都能夠迎刃而解。

筆者利用最短路徑演算法中的「無圈戴克斯特拉演算法」（Acyclic Dijkstra’s Algorithm），經過一些改進，並利用電腦計算出所有最便宜的票要如何購買，結果如下表：

此表要怎麼查呢？是這樣的，不管南下或北上，都先視為南下，例如要買嘉義到新竹的票，先視為「新竹→嘉義」，查上表得「苗, 780」這串字，代表要先拆票買「新竹→苗栗」，剩下「苗栗→嘉義」這段，再查表，得「640」，沒有國字在數字前面，表示直接買是最便宜的。因此嘉義到新竹，就可以拆成「嘉義苗栗」與「苗栗新竹」兩張票買，只有 780 元，比原票價的 790 省了 10 元。

若是「台北→左營」的話，查上表可知，買「台北、桃園、新竹、苗栗、彰化、嘉義、左營」拆成六段票，會是 1480元，也是省 10 元。但這樣買的話，可能屁股還沒坐熱，就又要起來換位置了，還蠻麻煩的。

比較實用的是自由座。我們先來看一下現在高鐵自由座票價：

自由座全票價計算規則是把標準全票打 95 折後取比較靠近的 5 的倍數，也是類似四捨五入，其最佳的拆票表如下：

上表可以看出自由座長途車票拆票的話，最多可以省到 20 元。而且坐上車後，不用換位置，可以坐到底，非常方便。自由座優惠票（半票）最佳拆票表如下，最多可以省到 25 元：

至於商務艙屬於特殊服務，票價並不受交通部規範，所以它的計算方式並沒有用到「四捨五入」，而是每一段直接疊加的，所以怎麼拆票價錢都是一樣的。

至於團體票、早鳥票，實用性不高，這裡就不列出了。若讀者真的有需要，或是想檢驗自己跑出的結果，都歡迎來信跟我索取。

從上面的例子，有個很重要很重要的現象：「誤差是會疊加的！」標準全票因為用到四捨五入，所以會有誤差，最多差到 10 元，自由座把標準全票乘以 0.95 後再四捨五入，最多可以差到 20 元，自由座半票又再乘以 0.5 後再四捨五入，所以最多可以差到 25 元。若自由座半票，直接是把標準全票的原始票價乘以 0.95，再乘以 0.5，最後再做四捨五入的話，這樣誤差就小很多了。

事實上，筆者也把台鐵的票價表做了計算，下表是西部幹線山線的拆票表：
（台鐵各列車票價請參考：台鐵自強號票價查詢；台鐵票價計算方式請參考：台鐵票價試算。）

因為台鐵票價是四捨五入到個位數，所以即使基隆到屏東最長的路線拆成了 13 段票，也只省了 2 元。我想應該沒有人會為了省 2 元，自找麻煩吧。

考考讀者，若所有票價計算，皆改成無條件捨去的話，那會如何呢？改成無條件進入呢？

數學就在你身邊！

由以上幾個分享的例子（以及文末推薦的延伸閱讀），可以了解到數線、平面坐標、極坐標的制定概念，其實早就存在生活中，只是數學家將它更嚴謹地用數學語言描述出來。另外，同餘概念、最優化、微積分、演算法，這些求學過程各階段中學到的數學，也都可以運用到生活上。

大多的知識，其實都有其演進堆疊的過程，而且生活上的事物，常常也可以跟所學連結。因此，多學總是有益無害的，但通常我們的學習環境，都是只有學習，卻不常訓練學生如何去應用，「培養數感」其實就是「培養數學時常能跟生活結合的感覺」，有了「數感」就會有學習動機，有了學習動機，學生就會主動學習。

前陣子爆紅的手機遊戲 Pokémon Go，社群網站上，就可以看到各種神人分享所學與遊戲結合的結果：

• 演算法熟悉的人，就分享怎麼安排行走路線會最省時省力；
• 熟悉統計與最優化的人，就會分享如何撒花比較划算，提升抓到怪的機率；
• 學組合數學的人，可以計算所有怪獸搜集完全所需要時間的期望值、同樣的怪要轉換（transfer）誰、怪的體質與屬性的相剋分析、預估升級時間；
• 學電子的人會設計一個雷達裝置放在身上，路上遇到怪就會發出通知、利用無人裝置孵蛋；
• 駭客就會攔截遊戲訊號，取得怪的隱藏數值（IV）······等。

每個主題都不是一時一刻可以講的清楚，但看到不同背景的人，無不使用渾身解術，把所學運用到生活中，著實為我們帶來了不少正能量。

UniMath，You need Math，本期刊就是希望能培養大眾的數感而生，雖然每個人的學習背景不同，但只要能夠時時抱持著自己的知識都能用在生活上的信念，相信一定能蹦出不少的火花。

後記

編按：這篇文章近期在各大新聞也有許多相關的討論（例如：「數學老師幫你算好了　高鐵票分段買最便宜」 /以及後續的「高鐵票分段買最便宜？高鐵：恐造成行程延誤」），原作者郭君逸老師也在PTT上針對這個主題撰寫的初衷和一些網友的提問做了回答。而這些回應也讓文章的討論更臻完整，於是泛科學以後記的方式在此將原本的回文進行增補。

拆票有可能變便宜，我想很多人很早就知道了；如許多鄉民所講，只要利用加法還有比較大小，就可以知道了。其實會這樣想的話，表示已經可以把數學用到生活中了。

不過再更進一步去想你可能會想問：

1. 有時拆票又會變貴，到底為什麼？是不是高鐵的Bug？
2. 又怎麼拆會最便宜？

不管答不答的出來，會這樣想的人就是有著數學思維，Unimath的目的其實就達到了。而這篇文章的重點其實就是為了幫大家回答這兩個問題：

1. 因為「誤差是會累加的」，高鐵票的計算方式是四捨五入到十元，有誤差，所以分越多段的誤差就會越大。
2. 但怎麼拆才會「最佳」，這就要靠電腦的幫忙了。（演算法用在哪？後面會講）

而記者把重點放錯了，都著重在省20元，或是去售票機買不會影響別人之類的。 而且下的標題還很聳動！（這當然不能怪記者，因為不聳動的標題，沒人要點進去看！但至少重點要放對啊……）其實還蠻高興大家對這個主題有興趣的， 若有什麼好的科普主題或文章，歡迎投稿Unimath，跟大家一起分享。

下面是一些比較 boring 的部份，也順便回答一些鄉民的問題：

1. 演算法用在哪？不是只要加法就可以了嗎？

會這樣問的人，應該是沒有碰過程式。知道怎麼拆票的話，當然是直接把每一段票價加起來即可，所以只用到加法。但問題就是不知道怎麼拆，有時拆了還會變貴。

一個簡單的想法是：如果A到F中間有B,C,D,E站的話，每個站要分不分，總共2^4種切法都去試，這樣就是一種演算法。但這樣的爆力法，效率很差（指數時間），高鐵站可能還好，但如果像台鐵當中間的站點一多，連電腦也會算不完。

那要怎麼省時間呢？我觀察到了中間有很多重複計算的部份，例如： 計算A到F站的話，在試切C點時，也會把AC與CF的最佳解都算過了，後來就不用再重複算。 所以我就採取空間換取時間的方法（Dynamic Programming）把算過的存起來就不用再重算， 這樣的演算法就會快很多，即時算台鐵的所有站的分票，也是按個Enter馬上就算完了。

整個演算法雖然是我自己想的，後來還是查了一下書， 發現在演算法書中，最短路徑一章就有很多類似的東西，然後我的演算法跟Dijkstra無迴圈的版本很像。 （其實還是有點不同只是原理相同， 有興趣的同學可以自己寫程式列出所有站點之間的分票方式，比較能體會其奧妙，程式其實很短。）

2. 誤差疊加很重要，求學時老師每次講，台下的我聽了都沒感覺。

明明多項式計算就代進去就好，為什麼還要改成巢狀計算； 矩陣就直接乘就好，為什麼還要對角化、Jordan Form……然後就會在台下說，學這個到底要幹嘛、多此一舉， 後來等到自己遇到麻煩了，才知道自己當時的無知。

3. 時間成本很重要，誰會省這20元。

這當然是這樣，現在比較忙時間都不夠用，我自己每次坐高鐵都坐直達的，誰想每站在那裡換位置！省錢只是文章的手段，讓讀者願意點進來看，但重點不在此，不要再被記者拉著走了。

4. 數學教授整天算一些沒用的東西。

其實有沒有用每個人都不同， 否則籃球員為什麼要一直把球丟到籃框裡？ 畫家為何要畫畫？攝影不就照起來，再用一些濾鏡就好了？ 這都是他們的工作、成果、興趣。 自然會有欣賞的人，自然也都有它的價值在。

5. 只要會加減乘除就可以活的好好的，為什麼要學這麼多？

這老生常談了。這就讓大家幫忙回答吧！ 連加減都不會，也是可以活的好好的。

• ［數學妙用］不會測速的測速相機，郭君逸，UniMath。
• 生活中的數學：交通篇(上)，郭君逸，UniMath。
• Pokémon Go 指南：如何用數學幫助你 Catch ’em all，賴以威、陳宏賓，UniMath。

本文轉載自 UniMath，《高鐵票分段買比較便宜?》

作者簡介：郭君逸 － 國立台灣師範大學數學系助理教授、魔術方塊收藏家。
主要研究興趣為組合、圖論、演算法。近年來致力於科普的推廣，喜愛玩各種數學遊戲、益智玩具以及各類型魔術方塊。目前為世界魔方聯盟(WCA)台灣地區認證員。曾開設整個學期的魔術方塊通識課程，跑遍全台進行魔術方塊系列演講。

關於 UniMath：UniMath (You Need Math)是一個 Online 數學媒體，我們的目的是成為一個線上平台，發表數學相關的科普文章及影音，使數學用更柔軟的姿態走入群眾，提升數學素養。歡迎加入 Facebook 粉絲團知道第一手訊息！

• 文／郭君逸 │國立臺灣師範大學數學系副教授

編按：說到乘法，我們很快都會想到國小的共同回憶「九九乘法表」。背誦它對我們來說可能是一位數相乘最快的解方，多位數我們就用直式乘法運算。但如果是超超超超超超超級多位數互相相乘呢？有沒有更快的方法？

對於人腦來說可能大位數的乘法已經沒有意義，但對於電腦來說，有新的乘法方式可是大大的不一樣！三月時有數學家發表了有史以來將大數字相乘最快的新乘法方式，讓我們一起來一探究竟吧！

從「九九加法表」與「九九乘法表」談起

我們在國小時的數學，一開始就會先學「數數」，要會數 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)的一位數加法，與 n² 次的一位數乘法。可見，乘法的運算次數是隨著位數的平方成長，所以計算乘法比較慢。

Karatsuba以加減法取代乘法，加快運算速度？

1960年，俄羅斯的大數學家 Andrey Kolmogorov 在一次研究討論中提出他的猜測（n 位數的乘法必須用到至少 n² 數量級的一位數乘法），例如 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 用一個加法與兩個減法取代了一個乘法。讀者這時可能會想說，拿一個一位數乘法去換三個加減法，又不是頭殼壞去，這樣不是反而慢嗎？

我們來看一下 4 位數的情況， 2531×1467 一樣先算 25×14 與 31×67，然後中間的 25×67+31×14 用 (25+31)×(14+67)-25×14-31×67 計算，最後加總起來。

如同前面的分析，此處一樣用到三個二位數乘法，而每個二位數乘法又用到三個一位數乘法，所以總共用到 3×3 =9 次一位數乘法。因此一般 n 位數的乘法，用這種技巧，可以只用到

3^log₂ n=n^log₂ 3=n^1.58

個一位數乘法。位數越高，用到的一位數乘法數就會越接近 n^1.58 的常數倍。對於人來說，因為把一個乘法換三個加減法，並沒有比較快，何況還要遞迴的操作；但是，對電腦而言就不是這樣了。

電腦運算的本質：二進位

電腦的本質上是二進位的系統 （哪有！我用電腦這麼多年，沒看到什麼二進位啊！那是現在電腦發展很快，事實上隨便顯示一張小圖、或一個字，背後都做了數百萬次的二進位運算。）而電腦的加法是用位元的邏輯運算來達成（也就是 AND、OR、XOR、NOT、Shift 這些東西來組成的），而位元邏輯運算超快，詳細我們就不說了，總之電腦的加法非常快。

那電腦的乘法，真的是用 Karatsuba 的方法嗎？其實也不是，我們先來看一下 8 位元的電腦怎麼做乘法好了。以 11 乘以 14 來說，化成二進位變成 00001011 與 00001110 （前面要補 0，因為 8 位元的電腦它就是用 8 個位元儲存數字。）

這不就是直式乘法嗎？這樣哪有比較快？有的。因為人類習慣十進位，所以要背「九九乘法表」；電腦用的是二進位，所以要背「一一乘法表」！！沒錯，所以等於不用背，二進位的直式乘法，其實只是被乘數的平移，然後加起來而已，換句話說，其實乘法，也是一堆位元邏輯運算而已，所以也是超快的。

那 Karatsuba 的方法用在哪呢？用在很大很大的數字相乘的時候。電腦的乘法雖快，但 8 位元電腦，最大就只能處理 2⁸－1＝255 以內的乘法，乘完後超過 255 的話就不能處理了，16位元電腦最大可以處理到 65535 以內的數，而現在的64位元電腦就可以處理到……一個非常大的數，呵呵。

那超過電腦能處理的數的話，到頭來，還是要用傳統的方法來處理，為了不要讓數字太大，我們以 8 位元的電腦為例，處理數字就會看成 256 進位來處理，533×499 就會變成

所以當數字大的時候，這時 Karatsuba 的方法就有用了。

值得一提的是，當電腦硬體從 8 位元升級到 16 位元時，軟體若沒有改成 65536 進位的話，而用 16 位元電腦來存 255 以內的數，前面就會補了更多的 0，處理起反而會浪費時間。而若軟體有跟著處理成 65536 進位的話，533×499 就會變只有位元邏輯運算而已，會超快。這就是為什麼電腦硬體剛進入 64 位元時代時，軟體沒有跟上的話，執行程式反而變慢的原因。

歷經三十年的演算法改進

OK，我們再回來乘法的問題。Karatsuba 的方法，在數字大的時候的確可以加快乘法，以一千位數的乘法來說，此法的速度大約是傳統乘法的 17 倍。

隔年，1963 年，A. L. Toom改進到了 ；後來 1966 年 Arnold Schönhage 用了新的方法推進到；1969 年 Knuth（沒錯，就大家所知道的Knuth），改進到。

後來 1971 年，Schönhage 捲土重來，與 Volker Strassen 利用快速傅立葉變換改進為 O(nlogn log logn)，此為有名的 Schönhage–Strassen algorithm，在差不多三萬位數以上的乘法，會比 Karatsuba 方法還要快。此法也是目前大數字乘法的主流，著名的梅森質數搜尋網（Great Internet Mersenne Prime Search，在 2018 年 12 月找到第 51 個）就是用 Schönhage–Strassen algorithm 來達到快速乘法。

隔了三十幾年，一直到了2007年，Martin Fürer一樣是用快速傅立葉變換，將複雜度下降到了O(n (log n) 16^log*n)，其中 log*n 就是 n 取幾次 log 會讓這個數小於 1，這是一個成長很慢的函數，基本上可以視它為常數了。

最後最後，David Harvey 與 Joris Van Der Hoeven 寫了幾篇的論文，把這個結果改成 O(n(logn)8^log*n)，然後 O(n(log n)4^log*n)，直到 2019 年，終於證明了 Schönhage 與 Strassen 的猜測 O(n log n)。

Volker Strassen 的大矩陣乘法

值得一提的是，Volker Strassen 除了是「大整數乘法」的始祖外，他也是「大矩陣乘法」的始祖（筆者寫到這裡，不自覺的跪了下來）。以 2×2 的矩陣來說，傳統計算

時，由於 x = ae + bg, y = af + bh, z=ce + dg, w=cf+dh，總共需要 8 次的乘法，但 1969 年，Strassen說，先計算下面 7 個值，

然後讀者可以自行驗證

因此只用了 7 個乘法就完成了。天啊！這是怎麼想到的！

一般 n×n 矩陣乘法，用 Strassen algorithm 只需要 O(n^log7) = O(n^2.8) 次乘法。從此大家才知道，原來矩陣乘法竟然可以比 n³ 還要快，矩陣乘法的改進也有相當精彩的發展歷史，詳細就不再一一介紹了，目前最好的結果是 2014 年 François Le Gall 的 O(n^2.3728639)。

演算法已經超越所需要的計算尺度啦

不管是大整數乘法，或大矩陣乘法，目前都是以 Schönhage–Strassen algorithm 與 Strassen algorithm 為主流，沒有採用後來看起來較好的方法主因是後來的方法太複雜，且要在很大很大很大的整數、矩陣執行效能才會比較好，已經超越了人類目前所需要的計算尺度。另一方面，電腦硬體的發展快速，會直接把這些演算法寫到晶片，變成指令集，讓程式直接呼叫，甚至是多條相同的指令可以平行處理，經由硬體的加速，乘法的速度已經超越了演算法改進的速度了（尤其是矩陣的乘法）。

不過只要還沒達到所謂的最佳解，相信數學家們都還是會繼續為數學理論極限而努力。

參考文獻

• Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281–292, 1971.
• 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.
• David Harvey, Joris Van Der Hoeven. Integer multiplication in time O(n log n). 2019. hal-02070778

學心算能幹嘛？

原本以為小時候學心算，只能在數學考試計算速度完勝隔壁同學，結帳的時候跟收銀機比快，殊不知在「算得快」之外，不知不覺中用心算培養出對數字本身的 sense，這份「數字感」加上好奇心還真讓我做了一件特別的事——不是數學系的卻發現也是發明了一個數學原理。

我對數字的好奇與狂熱是從國二時發現位數根（digital root）的規律開始。位數根是把一個正整數各個位數的數字加總直到加到不能再加，也就是最終的數字落在 1 到 9 之間，就好像大家在算生命靈數一樣。以 D(n) 表示整數 n 的位數根，D(9527) = D(9+5+2+7) = D(23) = D(2+3) = 5，5 即為 9527 的位數根。

而源自古印度的吠陀方形（Vedic square），就是將大家熟悉的九九乘法表中每一個數字進行位數根運算，其中位數根所在的位置組成的胚騰（pattern）構成了特定的幾何圖案。吠陀方形後來也影響了伊斯蘭文化，西元 770 年時穆斯林將吠陀方形併入他們的數學知識體系中[1]。

從二維平面到三維立體

風靡幾千年的吠陀方形和伊斯蘭幾何圖樣都讓我深深著迷，同時也很好奇，在這古老的數學概念中，是否有我不知道的東西？還有沒有新花樣可以玩？我開始翻閱許多與位數根、吠陀方形相關的學術論文，試圖從中找靈感。

靈感這種東西說來奇妙，有時候總是來自想像不到的地方。這次我的靈感來自一棟被數學元素和演算法啟發的建築，結構設計師塞西爾‧巴爾蒙德（Cecil Balmond）與伊東豊雄（Toyo Ito）設計蛇形藝廊 2002（Serpentine Gallery Pavilion 2002）。巴爾蒙德將簡單的平面正方形元素透過 1/2 → 1/3 的演算法，拓展成一個沒有柱子的盒型幾何建築。

我心想蛇形藝廊 2002 從二維平面到三維立體的過程太漂亮了，而且吠陀方形和伊斯蘭幾何藝術有間接關係也十分有趣。如果說吠陀方形也從平面變成立體會發生什麼事？我試著把九九乘法表向上加一個維度也就是 Z 軸，成為了 三個數字相乘的三維乘法表（9×9×9） 。

這個三維乘法矩陣為單位長度為 9 的立方體，如同吠陀方形為二維乘法表中每個數字進行位數根運算後的結果，我將它取名為「吠陀立方（Vedic cube）」，是整個立方體中各個座標點的數字進行位數根運算後的結果[2]。

為了知道吠陀立方中每一個座標點的數值，以函數 D(X, Y, Z) 代表吠陀立方中座標 (X, Y, Z) 該數字的位數根，實際運算時的數學式為 D(X×Y×Z)。例如座標點 (2, 3, 5)在吠陀立方中的數值即為 D(2×3×5) = D(30) = D(3) = 3，其他座標點的計算方式以此類推。

難想像的三維吠陀立方，就請電腦來幫忙吧！

由於吠陀方形構成許多有趣的幾何圖樣，所以我猜測吠陀立方也有類似的特性。為了了解位數根於三維空間中的分布情形，我利用 Matlab 軟體計算出吠陀立方各個座標點的位數根數值，並且繪出空間中特定位數根散布的情況。下圖為吠陀立方中位數根為 1（digit 1）的點在三維空間中的散布情形及位置，也就是 D(X, Y, Z) = 1 的集合。其他位數根的散布情形可以看我在《國際趣味數學雜誌》 （Recreational Mathematics Magazine）發表的一篇數學論文〈三維空間的位數根胚騰〉[2]。

由於三維空間中的圖形相當複雜，一時並不容易看出這些散布點在空間中的規律。接著是我所說的「數字感」發揮的時間了，我將以不同的方法簡化吠陀立方，試圖找出三維空間中吠陀立方裡頭可能出現的胚騰及其意義。

• 作者註：本文中的「圖樣」大多描述二維空間與吠陀方形的位數根圖樣，「胚騰」則是較為較為廣義，主要用來描述三維空間中吠陀立方中位數根的規律、模式、圖樣等。

把吠陀立方當做是一個 9 層樓高的立方體

除了 D(X×Y×Z) 的算法以外，也可以把吠陀立方當做是一個 9 層樓高類似建築物的立方體，其範圍為 Z = 1 至 Z = 9 的 X-Y 平面，並且以立方體中不同的 Z 軸高度作為「樓層」區別的原則，1 樓（第一層）就是吠陀方形。

1 樓（F1）至 9 樓（F9）的所有數值如下圖，看起來都是數字讓你害怕了嗎？別擔心我們一步一步來看。我們走上 2 樓（F2），這一層樓的數值是 1 樓的數字乘上 2 後再進行位數根運算，其他樓層也就分別是 1 樓的數字乘上樓層數，再算出位數根。

實際上吠陀立方中的 X, Y, Z 座標互相交換後，其數值仍為相同，就像是九九乘法表裡頭 X 乘上 Y 會等於 Y 乘上 X。為了方便起見，我僅以 Z 軸的高度（X-Y平面）作為區別的原則，但實際上以 Y-Z 平面或是 X-Z 平面為底結果相同。也就是吠陀立方從前看、側看、上看都會長得一樣，世界上長成這樣的東西並不多，可以讓我左看、右看、上看、下看，發現每個立面都不簡單。

我在此先簡單介紹吠陀立方中位數根的基本特性。當位數根為 1, 2, 4, 5, 7, 8 等六種數值時，會有相似的特性，我將以位數根 1 為例說明此六種數值的情況，以位數根 3 代表 3 與 6，最後將單獨說明位數根 9。

位數根 1 在 1, 2, 4, 5, 7, 8 樓這 6 層中，每一層會出現 6 個數字，因此在吠陀立方裡位數根 1 共有 36 個數字。而 1, 2, 4, 5, 7, 8 這 6 種位數根，在吠陀立方中共有 216 個。

位數根 3 在 1, 2, 4, 5, 7, 8 樓中各有 12 個數字，在 3 樓和 6 樓則各有 18 個，因此共有 108 個。位數根 3 和 6 在吠陀立方中加起來共 216 個數字。

位數根 9 則是在 1, 2, 4, 5, 7, 8 樓那 6 個樓層各有 21 個，3 樓和 6 樓有 45 個，在 9 樓有 81 個，共 297 個。

在吠陀立方中，全部的位數根數量加起來有 729 個，也就是總共的座標點數 9×9×9 。

吠陀立方是受到古印度數學吠陀方形、伊斯蘭幾何圖樣與倫敦蛇形藝廊 2002 的啟發，跨越數千年與東西方文化最終在台灣這個文化交融之地產生的數學。這一篇文章介紹了吠陀立方的定義與基本特性，至於吠陀立方還藏有什麼奧秘，像是每一層樓位數根圖樣的變換原理、以及位數根胚騰的空間幾何關係，留給下回再來分解。

參考資料

1. Jones, L. “Mathematics and Islamic art”, Mathematics in School, 18(4), 32–35, 1989.
2. Lin, C. Y. Digital Root Patterns of Three-Dimensional Space. Recreational Mathematics Magazine, 3（5）, 9–31, 2016.

此文作者本系列文章獲得臺北市政府文化局藝文補助