1

0
2

文字

分享

1
0
2

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

UniMath_96
・2019/05/30 ・3729字 ・閱讀時間約 7 分鐘 ・SR值 484 ・五年級

-----廣告,請繼續往下閱讀-----

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

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

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

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

我們在國小時的數學,一開始就會先學「數數」,要會數 1、2、3、⋯接下來才能學加法,例如:8+5 就是 8 往後數 5 個…9, 10, 11, 12, 13,所以 8+5=13。但每次都這樣做建構式的加法太慢,成不了大事,於是大家就背了「九九加法表」(雖然老師沒提這個表,但事實上大家的確都背了!)來快速處理一位數的加法,後來再學直式加法搭配進位,就能夠計算多位數的加法。

source:李家同臉書網誌

學習乘法也是差不多的歷程。正整數的乘法其實本質就是「重複做很多次加法」,例如 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 次的一位數乘法。可見,乘法的運算次數是隨著位數的平方成長,所以計算乘法比較慢。

數學家Andrey Kolmogorov。圖/wikipedia

Karatsuba以加減法取代乘法,加快運算速度?

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 用一個加法與兩個減法取代了一個乘法。讀者這時可能會想說,拿一個一位數乘法去換三個加減法,又不是頭殼壞去,這樣不是反而慢嗎?

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

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

3logn=nlog3=n1.58

-----廣告,請繼續往下閱讀-----

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

電腦的本質上是二進位的系統。圖/pixabay

電腦運算的本質:二進位

電腦的本質上是二進位的系統 (哪有!我用電腦這麼多年,沒看到什麼二進位啊!那是現在電腦發展很快,事實上隨便顯示一張小圖、或一個字,背後都做了數百萬次的二進位運算。)而電腦的加法是用位元的邏輯運算來達成(也就是 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) 16log*n),其中 log*就是 n 取幾次 log 會讓這個數小於 1,這是一個成長很慢的函數,基本上可以視它為常數了。

-----廣告,請繼續往下閱讀-----

最後最後,David Harvey 與 Joris Van Der Hoeven 寫了幾篇的論文,把這個結果改成 O(n(logn)8log*n),然後 O(n(log n)4log*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(nlog7) = O(n2.8) 次乘法。從此大家才知道,原來矩陣乘法竟然可以比 n³ 還要快,矩陣乘法的改進也有相當精彩的發展歷史,詳細就不再一一介紹了,目前最好的結果是 2014 年 François Le Gall 的 O(n2.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
文章難易度
所有討論 1
UniMath_96
9 篇文章 ・ 209 位粉絲
UniMath (You Need Math) 是一個 Online 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。

0

3
0

文字

分享

0
3
0
強核力與弱核力理論核心:非阿貝爾理論——《撞出上帝的粒子》
貓頭鷹出版社_96
・2023/01/28 ・1733字 ・閱讀時間約 3 分鐘

-----廣告,請繼續往下閱讀-----

非阿貝爾理論

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

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

如果隨便拿兩個數字 A 和 B,用 A 乘 B 的結果永遠會和用 B 乘 A 一樣。圖/pixabay

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

條條大路通數學

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

-----廣告,請繼續往下閱讀-----

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

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

慢動作躲子彈鏡頭。圖/giphy

我來舉個例子。

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

-----廣告,請繼續往下閱讀-----

數學和真實世界密不可分

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

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

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

One of the Daya Bay detectors.圖/wikipedia

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

-----廣告,請繼續往下閱讀-----

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

貓頭鷹出版社_96
62 篇文章 ・ 26 位粉絲
貓頭鷹自 1992 年創立,初期以單卷式主題工具書為出版重心,逐步成為各類知識的展演舞台,尤其著力於科學科技、歷史人文與整理台灣物種等非虛構主題。以下分四項簡介:一、引介國際知名經典作品如西蒙.德.波娃《第二性》(法文譯家邱瑞鑾全文翻譯)、達爾文傳世經典《物種源始》、國際科技趨勢大師KK凱文.凱利《科技想要什麼》《必然》與《釋控》、法國史學大師巴森《從黎明到衰頹》、瑞典漢學家林西莉《漢字的故事》等。二、開發優秀中文創作品如腦科學家謝伯讓《大腦簡史》、羅一鈞《心之谷》、張隆志組織新生代未來史家撰寫《跨越世紀的信號》大系、婦運先驅顧燕翎《女性主義經典選讀》、翁佳音暨曹銘宗合著《吃的台灣史》等。三、也售出版權及翻譯稿至全世界。四、同時長期投入資源整理台灣物種,並以圖鑑形式陸續出版,如《台灣原生植物全圖鑑》計八卷九巨冊、《台灣蛇類圖鑑》、《台灣行道樹圖鑑》等,叫好又叫座。冀望讀者在愉悅中閱讀並感受知識的美好是貓頭鷹永續經營的宗旨。

0

1
0

文字

分享

0
1
0
高鐵票分段買比較便宜?重點是你有沒有用心觀察身邊的數學!
UniMath_96
・2017/08/07 ・5002字 ・閱讀時間約 10 分鐘 ・SR值 496 ・六年級

-----廣告,請繼續往下閱讀-----

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

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

圖/載自台灣高鐵

「矩陣!」

-----廣告,請繼續往下閱讀-----

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

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

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

其實並非如此!

-----廣告,請繼續往下閱讀-----

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

為什麼會有這種現象呢?

分段買就會便宜?錯!那不一定。圖/By Formosa Wandering @ flickr, CC BY-NC 2.0

首先我們先來研究一下高鐵的票價訂法。政府每年會先用「消費者物價總指數(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),經過一些改進,並利用電腦計算出所有最便宜的票要如何購買,結果如下表:

-----廣告,請繼續往下閱讀-----

圖/UniMath 提供

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

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

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

-----廣告,請繼續往下閱讀-----

圖/載自台灣高鐵

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

圖/UniMath 提供

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

-----廣告,請繼續往下閱讀-----

圖/UniMath 提供

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

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

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

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

圖/UniMath 提供

因為台鐵票價是四捨五入到個位數,所以即使基隆到屏東最長的路線拆成了 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,《高鐵票分段買比較便宜?

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

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

UniMath_96
9 篇文章 ・ 209 位粉絲
UniMath (You Need Math) 是一個 Online 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。

1

0
2

文字

分享

1
0
2
地表最速乘法傳說!碰到大得要命的數字,這是最快的乘法方式
UniMath_96
・2019/05/30 ・3729字 ・閱讀時間約 7 分鐘 ・SR值 484 ・五年級

-----廣告,請繼續往下閱讀-----

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

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

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

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

我們在國小時的數學,一開始就會先學「數數」,要會數 1、2、3、⋯接下來才能學加法,例如:8+5 就是 8 往後數 5 個…9, 10, 11, 12, 13,所以 8+5=13。但每次都這樣做建構式的加法太慢,成不了大事,於是大家就背了「九九加法表」(雖然老師沒提這個表,但事實上大家的確都背了!)來快速處理一位數的加法,後來再學直式加法搭配進位,就能夠計算多位數的加法。

source:李家同臉書網誌

學習乘法也是差不多的歷程。正整數的乘法其實本質就是「重複做很多次加法」,例如 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 次的一位數乘法。可見,乘法的運算次數是隨著位數的平方成長,所以計算乘法比較慢。

-----廣告,請繼續往下閱讀-----

數學家Andrey Kolmogorov。圖/wikipedia

Karatsuba以加減法取代乘法,加快運算速度?

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 用一個加法與兩個減法取代了一個乘法。讀者這時可能會想說,拿一個一位數乘法去換三個加減法,又不是頭殼壞去,這樣不是反而慢嗎?

-----廣告,請繼續往下閱讀-----

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

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

3logn=nlog3=n1.58

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

-----廣告,請繼續往下閱讀-----

電腦的本質上是二進位的系統。圖/pixabay

電腦運算的本質:二進位

電腦的本質上是二進位的系統 (哪有!我用電腦這麼多年,沒看到什麼二進位啊!那是現在電腦發展很快,事實上隨便顯示一張小圖、或一個字,背後都做了數百萬次的二進位運算。)而電腦的加法是用位元的邏輯運算來達成(也就是 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) 16log*n),其中 log*就是 n 取幾次 log 會讓這個數小於 1,這是一個成長很慢的函數,基本上可以視它為常數了。

-----廣告,請繼續往下閱讀-----

最後最後,David Harvey 與 Joris Van Der Hoeven 寫了幾篇的論文,把這個結果改成 O(n(logn)8log*n),然後 O(n(log n)4log*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(nlog7) = O(n2.8) 次乘法。從此大家才知道,原來矩陣乘法竟然可以比 n³ 還要快,矩陣乘法的改進也有相當精彩的發展歷史,詳細就不再一一介紹了,目前最好的結果是 2014 年 François Le Gall 的 O(n2.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
文章難易度
所有討論 1
UniMath_96
9 篇文章 ・ 209 位粉絲
UniMath (You Need Math) 是一個 Online 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。

0

0
0

文字

分享

0
0
0
數字感有什麼用?他把風靡千年的吠陀方形變立體了!
Sharkie Lin_96
・2016/12/31 ・2593字 ・閱讀時間約 5 分鐘 ・SR值 536 ・七年級

-----廣告,請繼續往下閱讀-----

學心算能幹嘛?

原本以為小時候學心算,只能在數學考試計算速度完勝隔壁同學,結帳的時候跟收銀機比快,殊不知在「算得快」之外,不知不覺中用心算培養出對數字本身的 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]。

九九乘法表
九九乘法表

-----廣告,請繼續往下閱讀-----

吠陀方形中的位數根胚騰[6]
吠陀方形中的位數根胚騰,D1 中灰色是表示位數根為 1 的格子,D2~D9 以此類推。

從二維平面到三維立體

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

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

倫敦蛇形藝廊 2002 建築物內觀。圖/Balmond Studio 授權使用
倫敦蛇形藝廊 2002 建築物內觀。圖/Balmond Studio 授權使用

-----廣告,請繼續往下閱讀-----

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

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

999

為了知道吠陀立方中每一個座標點的數值,以函數 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]。

-----廣告,請繼續往下閱讀-----

吠陀立方中位數根為 1 的點散布情形及位置。此胚騰散布的情況相當複雜,一時難以看出這些座標點在空間構成的意義。
吠陀立方中位數根為 1 的點散布情形及位置。此胚騰散布的情況相當複雜,一時難以看出這些座標點在空間構成的意義。

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

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

把吠陀立方當做是一個 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 平面為底結果相同。也就是吠陀立方從前看、側看、上看都會長得一樣,世界上長成這樣的東西並不多,可以讓我左看、右看、上看、下看,發現每個立面都不簡單。

999_19
吠陀立方 1 樓至 9 樓的所有數值。

我在此先簡單介紹吠陀立方中位數根的基本特性。當位數根為 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.

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

Sharkie Lin_96
24 篇文章 ・ 6 位粉絲
在國二無聊的早自習意外發現數學的趣味,因此近來體驗到數學研究、藝術創作、採訪寫作、展覽策劃、資優教育等工作。不是念數學也不是學藝術,但樂於從多元視角聊聊數學的各種姿態,以及進行數學藝術創作,希望能為世界帶來一點樂趣。科普部落格〈鯊奇事務所〉https://medium.com/sharkie-studio,聯絡信箱 sharkgallium@gmail.com

1

0
2

文字

分享

1
0
2
地表最速乘法傳說!碰到大得要命的數字,這是最快的乘法方式
UniMath_96
・2019/05/30 ・3729字 ・閱讀時間約 7 分鐘 ・SR值 484 ・五年級

-----廣告,請繼續往下閱讀-----

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

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

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

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

我們在國小時的數學,一開始就會先學「數數」,要會數 1、2、3、⋯接下來才能學加法,例如:8+5 就是 8 往後數 5 個…9, 10, 11, 12, 13,所以 8+5=13。但每次都這樣做建構式的加法太慢,成不了大事,於是大家就背了「九九加法表」(雖然老師沒提這個表,但事實上大家的確都背了!)來快速處理一位數的加法,後來再學直式加法搭配進位,就能夠計算多位數的加法。

source:李家同臉書網誌

學習乘法也是差不多的歷程。正整數的乘法其實本質就是「重複做很多次加法」,例如 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 次的一位數乘法。可見,乘法的運算次數是隨著位數的平方成長,所以計算乘法比較慢。

-----廣告,請繼續往下閱讀-----

數學家Andrey Kolmogorov。圖/wikipedia

Karatsuba以加減法取代乘法,加快運算速度?

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 用一個加法與兩個減法取代了一個乘法。讀者這時可能會想說,拿一個一位數乘法去換三個加減法,又不是頭殼壞去,這樣不是反而慢嗎?

-----廣告,請繼續往下閱讀-----

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

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

3logn=nlog3=n1.58

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

-----廣告,請繼續往下閱讀-----

電腦的本質上是二進位的系統。圖/pixabay

電腦運算的本質:二進位

電腦的本質上是二進位的系統 (哪有!我用電腦這麼多年,沒看到什麼二進位啊!那是現在電腦發展很快,事實上隨便顯示一張小圖、或一個字,背後都做了數百萬次的二進位運算。)而電腦的加法是用位元的邏輯運算來達成(也就是 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) 16log*n),其中 log*就是 n 取幾次 log 會讓這個數小於 1,這是一個成長很慢的函數,基本上可以視它為常數了。

-----廣告,請繼續往下閱讀-----

最後最後,David Harvey 與 Joris Van Der Hoeven 寫了幾篇的論文,把這個結果改成 O(n(logn)8log*n),然後 O(n(log n)4log*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(nlog7) = O(n2.8) 次乘法。從此大家才知道,原來矩陣乘法竟然可以比 n³ 還要快,矩陣乘法的改進也有相當精彩的發展歷史,詳細就不再一一介紹了,目前最好的結果是 2014 年 François Le Gall 的 O(n2.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
文章難易度
所有討論 1
UniMath_96
9 篇文章 ・ 209 位粉絲
UniMath (You Need Math) 是一個 Online 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。