0

0
1

文字

分享

0
0
1

這個九九乘法表你小學沒背過!吠陀方形的千年奧秘

Sharkie Lin_96
・2016/12/06 ・3369字 ・閱讀時間約 7 分鐘 ・SR值 502 ・六年級

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

我們從小學二年級就開始學習九九乘法表,但是上大學以後大家就開始正大光明地使用計算機,九九乘法表和心算能力就只剩下買東西的時候算錢可以比較快,那小時候學心算到底要做什麼呢?沒法馬上回答只好先來轉移一下話題,九九乘法表其實沒有你想像的那麼簡單,裡面有著你不知道的數學奧秘,且讓我們繼續看下去。

8492235227_358128050c_z
小學二年級開始我們就學九九乘法表,好像背出來就對了,也覺得熟練後就輕鬆簡單,但是它真的就這麼淺這麼簡單嗎?圖 / By Global Partnership for Education – GPE @ flickr, CC BY-NC-ND 2.0

算過生命靈數就懂的數學:位數根

不知道大家還記不記得,以前在檢查一個正整數是不是 3 或 9 的倍數,我們會將正整數的每個位數數字相加,看加總的數字是不是 3 或 9 的倍數來判斷。或者大家可能也算過號稱可解析命格的「生命靈數」,將自己的出生年月日中每個數字加總,超過 9 就再重覆這個計算過程,直到加到不能在加之後得出一個屬於自己的「生命靈數」。這樣的作法其實你已經運用了一個正整數的性質——「位數根」。

到底什麼是位數根?它可以叫做數根、數字根,英文是 digital root 或 digit sum,就是把一個正整數各個位數的數字加總,若其和大於 9,則再將所得數的數字再加總一次,如此反覆這個步驟直到所得新數介於 1 至 9之間,稱此新數為原數的位數根。在此 D (n) 表示整數 n 的位數根,例如:9527 的位數根運算為 D (9527) = D (9+5+2+7) = D (23) = D (2+3) = D (5) = 5,5 即為 9527 的位數根。

如果用位數根來看九九乘法表…

講了這麼多,數學奧秘到底在哪?先來看一下下圖的九九乘法表吧!不過,這個表和我們小時候背的不太一樣,它是一個 9×9 的表格,裡頭的數字是上方第一列的數字與左方第一欄的數字相乘的結果。

-----廣告,請繼續往下閱讀-----
九九乘法表
圖 1:九九乘法表

如果把這個九九乘法表的每一個數字都進行位數根運算,會出現什麼樣的結果?你可以自己試試看,也可以直接看圖 2 的結果。

將九九乘法表中每個數字進行位數根的運算,會得到新的一個表,而這個表稱為「吠陀方形」(Vedic square)。
圖 2:將九九乘法表中每個數字進行位數根的運算,會得到新的一個表,而這個表稱為「吠陀方形」(Vedic square)。

經過位數根運算後,九九乘法表就轉換成了著名的「吠陀方形」(Vedic square)。Vedic 這個英文字是從印度文 Vedas 來的,中文翻譯的「吠陀」常讓人聯想到精油或瑜珈,但在古印度文中它的意思是知識,所以可以把吠陀方形想像成是一個帶有知識的正方形。嗯?怎麼聽起來很像《平面國》這本書的故事情節呢 [1]。

《平面國》的主角是一位活在平面國的正方形男性,在一個偶然的機會下,一位「球體天使」帶他「向上」離開了平面國並遊歷了立體國,使得他成為最具知識的一號人物。回到平面國以後,主角迫不及待地想告訴大家「向上,而非向北」的體驗與真理,但先知總是孤獨的,平面國的人民會相信一個自稱掌握立體知識的正方形嗎?

吠陀方形可能早在佛陀之前就出現了

話說吠陀方形被發現的確切年代已經不可考,只知道數個世紀之前北印度的人們就已充分了解吠陀方形的性質,屬於古印度數學 [2]。古印度歷史有段時間叫做吠陀時期(Vedic period),大約是西元前 1500 年至西元前 500 年。如果說吠陀方形是在吠陀時期被發現的,那就是佛陀的年代甚至更早以前,真的很深很遠很古典哎。

-----廣告,請繼續往下閱讀-----
906px-north_gateway_-_rear_side_-_stupa_1_-_sanchi_hill_2013-02-21_4480-4481
如果說吠陀方形是在吠陀時期被發現的,那就是佛陀的年代甚至更早以前,真的很深很遠很古典!圖 / By Biswarup Ganguly, CC BY 3.0, wikimedia commons

吠陀方形後來也影響了伊斯蘭文化,西元 770 年時穆斯林將吠陀方形併入他們的數學知識體系中。事實上早期伊斯蘭文化的數學知識是比西方還要先進的,而且當時無論在技術與哲學上都非常強盛。伊斯蘭世界的數學到底有多厲害呢,可以從傳統伊斯蘭幾何圖樣(Islamic pattern)的藝術性裝飾看見,例如西班牙的阿罕布拉宮。由於可蘭經禁止具象化的偶像崇拜,因此伊斯蘭藝術中並沒有描繪人或是動物的圖畫,而是運用大量對稱且看似繁複的幾何圖樣,這些圖樣有專文與專書探討 [3,4]。

這瓶來自西班牙的紅酒,酒瓶上的貼紙包裝即為伊斯蘭幾何圖樣。西班牙留有許多伊斯蘭文化的遺產,我猜酒廠/酒商也認為這是個值得驕傲的文化象徵才當做是貼紙。圖/作者拍攝
這瓶來自西班牙的紅酒,酒瓶上的貼紙包裝即為伊斯蘭幾何圖樣。西班牙留有許多伊斯蘭文化的遺產,我猜酒廠/酒商也認為這是個值得驕傲的文化象徵才當做是貼紙。圖/作者拍攝

吠陀方形中藏著秘密圖形

吠陀方形與位數根胚騰(digital root patterns)密不可分,胚騰又是個什麼東西?胚騰就是 pattern,可以代表圖樣、規律、模式,甚至是一切有跡可循的事物 [5]。而數學是一種胚騰的科學(the science of pattern),尤其是在現今資料科學蓬勃發展的時代尋找胚騰與關聯更是重要無比,單單數字計算並不是數學。從未知中探究與發現規律與胚騰,是數學研究中最讓人目眩神迷的地方,位數根的研究與發現正屬於這類的驚奇。

講了這些少為人知的歷史和名詞以後讓我們再次回到圖 2,裡頭也有許多隱藏的圖樣,建議讀到這裡先暫停花幾分鐘觀察一下吠陀方形,避免破壞大家的樂趣。

2

好,剛剛提到的位數根胚騰呢?那是由位數根所在的位置組成的胚騰,意思是說,代數和幾何扯上關係了!

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

吠陀方形的行列數字組成與特定數字構成的胚騰,有著許多對稱性與互補性。位數根的分布也呈現有趣的幾何圖樣。下面的圖3中 D1 至 D9 分別為位數根 1 至 9 在吠陀方形中構成的圖樣 [6],裡面的圖樣看起來有六邊形、長方形,還有多邊形等。

吠陀方形中的位數根胚騰[6]
圖 3:吠陀方形中的位數根胚騰[6]

若是構成兩個圖樣的位數根總和為 9,這兩個圖樣將沿著鉛直線相互鏡射。像是數字 1 與數字 8 的位置構成的幾何圖案,是沿著鉛直線鏡射對稱的,或者是旋轉 90 度也可以得到。而數字 2 與數字 7、數字 3 與數字 6、數字 4 與數字 5 為另外三組以數字構成的對稱圖樣,由此可見數字 9 在位數根的世界中是個重要的數字,有發現一個整數加了 9 的倍數以後位數根不變嗎?數字 9 的胚騰比較特別,沒有和其他的數字構成互補圖樣自成一個世界,所以就暫時先不探討它。

D1~D9 吠陀方形中的對稱軸 X=Y。
D1~D9 吠陀方形中的對稱軸 X=Y。
D1~D8 吠陀方形中的另一條 對稱軸X+Y=9。
D1~D8 吠陀方形中的另一條 對稱軸 X+Y=9。

仔細觀察一下會發現 D1 至 D8 這 8 個胚騰有兩條對稱軸,其中一條是 X=Y,另一條是 X+Y=9,他們的交點是 (4.5, 4.5)。裡面的點都會照著這兩條對稱軸相互對稱與鏡射,可以從代數上解釋,也可以直接看圖找規律。X=Y 這條對稱軸代表的意思是一個座標點 (X,Y) 的 X、Y 值可以互換變成 (Y, X),其位數根不變,像是 (4,7) 和 (7,4) 的位數根都是 1。X+Y=9 這條對稱軸可以藉由 (X,Y) 這個點找到 (9-Y, 9-X) 這個點,也就是可以從 (4,7) 找到 (2,5) 這個點,如此一來就可以用少數的座標點找到其他點簡化問題。

沒想到小時候背的九九乘法表,居然藏著這麼多數學奧秘!數千年前的位數根胚騰和吠陀方形,讓世界為之瘋狂稱為 Magic。

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

 

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

參考資料

  1. 愛德溫.A.艾勃特,平面國:向上,而非向北!,新北市:魔酒出版,2014
  2. Jones, L. “Mathematics and Islamic art”, Mathematics in School, 18(4), 32–35, 1989.
  3. 塞伊德.蔣.阿巴斯和阿默.夏克爾.薩爾曼,伊斯蘭的幾何藝術,台北縣新店市:左岸文化,2004。
  4. Lu, P. J., Steinhardt, P. J. “Decagonal and Quasi-Crystalline Tilings in Medieval Islamic Architecture”, Science, 315(5815), 1106–1110, 2007.
  5. 曹亮吉,從生活學數學(第二版),臺北市:遠見出版,2009。
  6. Lin, C. Y. Digital Root Patterns of Three-Dimensional Space. Recreational Mathematics Magazine, 3(5), 931, 2016.
文章難易度
Sharkie Lin_96
24 篇文章 ・ 6 位粉絲
在國二無聊的早自習意外發現數學的趣味,因此近來體驗到數學研究、藝術創作、採訪寫作、展覽策劃、資優教育等工作。不是念數學也不是學藝術,但樂於從多元視角聊聊數學的各種姿態,以及進行數學藝術創作,希望能為世界帶來一點樂趣。科普部落格〈鯊奇事務所〉https://medium.com/sharkie-studio,聯絡信箱 sharkgallium@gmail.com

0

8
2

文字

分享

0
8
2
快!還要更快!讓國家級地震警報更好用的「都會區強震預警精進計畫」
鳥苷三磷酸 (PanSci Promo)_96
・2024/01/21 ・2584字 ・閱讀時間約 5 分鐘

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

本文由 交通部中央氣象署 委託,泛科學企劃執行。

  • 文/陳儀珈

從地震儀感應到地震的震動,到我們的手機響起國家級警報,大約需要多少時間?

臺灣從 1991 年開始大量增建地震測站;1999 年臺灣爆發了 921 大地震,當時的地震速報系統約在震後 102 秒完成地震定位;2014 年正式對公眾推播強震即時警報;到了 2020 年 4 月,隨著技術不斷革新,當時交通部中央氣象局地震測報中心(以下簡稱為地震中心)僅需 10 秒,就可以發出地震預警訊息!

然而,地震中心並未因此而自滿,而是持續擴建地震觀測網,開發新技術。近年來,地震中心執行前瞻基礎建設 2.0「都會區強震預警精進計畫」,預計讓臺灣的地震預警系統邁入下一個新紀元!

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

連上網路吧!用建設與技術,換取獲得地震資料的時間

「都會區強震預警精進計畫」起源於「民生公共物聯網數據應用及產業開展計畫」,該計畫致力於跨部會、跨單位合作,由 11 個執行單位共同策畫,致力於優化我國環境與防災治理,並建置資料開放平台。

看到這裡,或許你還沒反應過來地震預警系統跟物聯網(Internet of Things,IoT)有什麼關係,嘿嘿,那可大有關係啦!

當我們將各種實體物品透過網路連結起來,建立彼此與裝置的通訊後,成為了所謂的物聯網。在我國的地震預警系統中,即是透過將地震儀的資料即時傳輸到聯網系統,並進行運算,實現了對地震活動的即時監測和預警。

地震中心在臺灣架設了 700 多個強震監測站,但能夠和地震中心即時連線的,只有其中 500 個,藉由這項計畫,地震中心將致力增加可連線的強震監測站數量,並優化原有強震監測站的聯網品質。

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

在地震中心的評估中,可以連線的強震監測站大約可在 113 年時,從原有的 500 個增加至 600 個,並且更新現有監測站的軟體與硬體設備,藉此提升地震預警系統的效能。

由此可知,倘若地震儀沒有了聯網的功能,我們也形同完全失去了地震預警系統的一切。

把地震儀放到井下後,有什麼好處?

除了加強地震儀的聯網功能外,把地震儀「放到地下」,也是提升地震預警系統效能的關鍵做法。

為什麼要把地震儀放到地底下?用日常生活來比喻的話,就像是買屋子時,要選擇鬧中取靜的社區,才不會讓吵雜的環境影響自己在房間聆聽優美的音樂;看星星時,要選擇光害比較不嚴重的山區,才能看清楚一閃又一閃的美麗星空。

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

地表有太多、太多的環境雜訊了,因此當地震儀被安裝在地表時,想要從混亂的「噪音」之中找出關鍵的地震波,就像是在搖滾演唱會裡聽電話一樣困難,無論是電腦或研究人員,都需要花費比較多的時間,才能判讀來自地震的波形。

這些環境雜訊都是從哪裡來的?基本上,只要是你想得到的人為震動,對地震儀來說,都有可能是「噪音」!

當地震儀靠近工地或馬路時,一輛輛大卡車框啷、框啷地經過測站,是噪音;大稻埕夏日節放起絢麗的煙火,隨著煙花在天空上一個一個的炸開,也是噪音;台北捷運行經軌道的摩擦與震動,那也是噪音;有好奇的路人經過測站,推了推踢了下測站時,那也是不可忽視的噪音。

因此,井下地震儀(Borehole seismometer)的主要目的,就是盡量讓地震儀「遠離塵囂」,記錄到更清楚、雜訊更少的地震波!​無論是微震、強震,還是來自遠方的地震,井下地震儀都能提供遠比地表地震儀更高品質的訊號。

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

地震中心於 2008 年展開建置井下地震儀觀測站的行動,根據不同測站底下的地質條件,​將井下地震儀放置在深達 30~500 公尺的乾井深處。​除了地震儀外,站房內也會備有資料收錄器、網路傳輸設備、不斷電設備與電池,讓測站可以儲存、傳送資料。

既然井下地震儀這麼強大,為什麼無法大規模建造測站呢?簡單來說,這一切可以歸咎於技術和成本問題。

安裝井下地震儀需要鑽井,然而鑽井的深度、難度均會提高時間、技術與金錢成本,因此,即使井下地震儀的訊號再好,若非有國家建設計畫的支援,也難以大量建置。

人口聚集,震災好嚴重?建立「客製化」的地震預警系統!

臺灣人口主要聚集於西半部,然而此區的震源深度較淺,再加上密集的人口與建築,容易造成相當重大的災害。

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

許多都會區的建築老舊且密集,當屋齡超過 50 歲時,它很有可能是在沒有耐震規範的背景下建造而成的的,若是超過 25 年左右的房屋,也有可能不符合最新的耐震規範,並未具備現今標準下足夠的耐震能力。 

延伸閱讀:

在地震界有句名言「地震不會殺人,但建築物會」,因此,若建築物的結構不符合地震規範,地震發生時,在同一面積下越密集的老屋,有可能造成越多的傷亡。

因此,對於發生在都會區的直下型地震,預警時間的要求更高,需求也更迫切。

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

地震中心著手於人口密集之都會區開發「客製化」的強震預警系統,目標針對都會區直下型淺層地震,可以在「震後 7 秒內」發布地震警報,將地震預警盲區縮小為 25 公里。

111 年起,地震中心已先後完成大臺北地區、桃園市客製化作業模組,並開始上線測試,當前正致力於臺南市的模組,未來的目標為高雄市與臺中市。

永不停歇的防災宣導行動、地震預警技術研發

地震預警系統僅能在地震來臨時警示民眾避難,無法主動保護民眾的生命安全,若人民沒有搭配正確的防震防災觀念,即使地震警報再快,也無法達到有效的防災效果。

因此除了不斷革新地震預警系統的技術,地震中心也積極投入於地震的宣導活動和教育管道,經營 Facebook 粉絲專頁「報地震 – 中央氣象署」、跨部會舉辦《地震島大冒險》特展、《震守家園 — 民生公共物聯網主題展》,讓民眾了解正確的避難行為與應變作為,充分發揮地震警報的效果。

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

此外,雖然地震中心預計於 114 年將都會區的預警費時縮減為 7 秒,研發新技術的腳步不會停止;未來,他們將應用 AI 技術,持續強化地震預警系統的效能,降低地震對臺灣人民的威脅程度,保障你我生命財產安全。

文章難易度

討論功能關閉中。

鳥苷三磷酸 (PanSci Promo)_96
196 篇文章 ・ 300 位粉絲
充滿能量的泛科學品牌合作帳號!相關行銷合作請洽:contact@pansci.asia

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

1
2

文字

分享

0
1
2
吠陀立方對稱面法:解不出的空間幾何問題就到廚房解決吧!
Sharkie Lin_96
・2017/05/20 ・3626字 ・閱讀時間約 7 分鐘 ・SR值 533 ・七年級

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

到目前為止,吠陀立方系列文章已經介紹過流傳千年的古印度數學-吠陀方形(Vedic square),我運用數字感把它加上一個維度定義了吠陀立方(Vedic cube),再以樓層法去解析位數根胚騰(Digital root patterns)層層之間的關係[1],這回來介紹吠陀立方對稱面法

吠陀立方:將吠陀方形從平面延伸成立體

吠陀方形就是將大家熟悉的九九乘法表中每一個數字進行位數根(digital root)運算,例如說 4 乘上 8 會得到 32,把  3 加上 2 得到 5,這個 5 即為 32 的位數根,也是吠陀方形裡座標點(4, 8)的數值。吠陀方形在西元 770 年被穆斯林納入伊斯蘭文化的數學知識體系之中[2]。

圖1|吠陀方形(Vedic square)

其中位數根所在的位置互相連結後組成的胚騰(pattern)構成了特定的幾何圖案如下圖:

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

圖2|吠陀方形中的位數根胚騰

吠陀立方則是將吠陀方形從平面延伸成立體,也就是三個數字相乘的三維乘法表(9×9×9),是整個立方體中各個座標點的數字進行位數根運算後的結果,可以用函數 D(X, Y, Z) 代表吠陀立方中座標 (X, Y, Z) 該數字的位數根,實際運算時的數學式為 D(X×Y×Z)。例如座標點 (2, 4, 7)在吠陀立方中的數值即為 D(2×4×7) = D(56) = D(11) = D(2) = 2。

之前提到以程式繪出吠陀立方中的位數根胚騰,其散布情況相當複雜(可見此篇),難以看出這些座標點在空間中構成的意義。用樓層法解析吠陀立方,能夠觀察出位數根胚騰在各層本身的性質,甚至可從二維的吠陀方形推算不同樓層之間的變換。只是樓層法是把三維空間轉化成許多二維平面,較少探討位數根胚騰在三維空間中彼此的相關性,這時又該如何是好呢?

解構吠陀立方

回到數學或科學研究的基本方法,觀察、觀察、再觀察。

吠陀方形中,位數根 1 至位數根 8 位置構成的八個圖樣會沿著兩條對角線 X=Y 與 X+Y=9 對稱,兩條對角線為對稱軸,不僅在 X-Y 平面可以成立,在 Y-Z 平面、X-Z 平面同樣成立。從二維拓展至三維的過程中,對角線就變成了對角面同時也是對稱面,因此吠陀立方共有六個對稱面。

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

圖3

為了找到空間中最小不可分割的塊體,也就是不重複的基本元素(element),以及內部對應的座標點,希望能探討位數根胚騰在三維空間中的關係,所以我將沿著對稱面群切割與解構吠陀立方。

吠陀立方的對稱面群分為兩組,一組叫做主對稱面群(main symmetry planes, MSP),為 X=Y, Y=Z, X=Z,這三個對稱面都有通過原點,如圖 4;另一組則為副對稱面群(secondary symmetry planes, SSP),為 X+Y=9, Y+Z=9, X+Z=9,如圖 5。

圖4

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

圖5

圖 4 和圖 5 的每一塊灰色塊體,都可藉由一次鏡射後得到完整的吠陀立方。至於分析的塊體取對稱面群兩邊任何一塊皆可,並沒有限制要取對稱面群的哪一邊。除此之外,可以選擇先在 X-Y, Y-Z, X-Z 平面沿著主副對稱面群切割,得到的塊體將是三角柱體,其底面為 1/4 正方形面積的等腰直角三角形。

沿著主對稱面群分割吠陀立方的結果如圖 6,得到 6 個 MSP 四面體(MSP unit tetrahedron),值得注意的是這 6 個四面體為雙直角四面體(birectangular tetrahedron),顧名思義此四面體包含兩個直角,在數學上也稱為 Schläfli orthoscheme。此雙直角四面體的底面為 1/2 正方形面積的等腰直角三角形,高為立方體的邊長,因此體積為吠陀立方的1/6。

每一個 MSP 四面體可沿著 X=Y, Y=Z, X=Z 共鏡射三次得到吠陀立方。主對稱面群的交集為一條線,也就是吠陀立方的對角線 X=Y=Z,因此會將吠陀立方分成 6 塊。

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

圖6|六個塊體對應的邊界條件為 (a) X≥Y, Y≤Z, X≥Z;(b) X≥Y, Y≥Z, X≤Z;(c) X≥Y, Y≥Z, X≥Z;(d) X≤Y, Y≥Z, X≥Z;(e) X≤Y, Y≤Z, X≥Z;(f) X≤Y, Y≥Z, X≥Z

副對稱面群分割後的結果為 8 個塊體如圖 7,包括 2 個 SSP 六面體(SSP unit hexahedron),體積各佔吠陀立方的 1/4;以及 6 個 SSP 四面體(SSP unit tetrahedron),其底面為 1/2 正方形面積的等腰直角三角形,高為吠陀立方邊長的 1/2,體積各佔吠陀立方的 1/12。副對稱面群的交集為一個點,為吠陀立方的中心 (4.5, 4.5, 4.5),因此會將立方體分成 8 塊,而這 8 塊的體積並不完全相同。

圖7|八個塊體對應的邊界條件為 (a)X+Y≤9, Y+Z≤9, X+Z≤9;(b)X+Y≤9, Y+Z≤9, X+Z≥9;(c)X+Y≤9, Y+Z≥9, X+Z≤9;(d)X+Y≤9, Y+Z≥9, X+Z≥9;(e)X+Y≥9, Y+Z≥9, X+Z≥9;(f)X+Y≥9, Y+Z≥9, X+Z≤9;(g)X+Y≥9, Y+Z≤9, X+Z≥9;(h)X+Y≥9, Y+Z≤9, X+Z≤9.

把幾何問題從書桌搬到餐桌!

切豆腐情境圖,非作者本人。source:Robert Couse-Baker

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

在思考副對稱面群分割問題時,為了驗證自己的想法,在愛爾蘭的聖誕假期,我把所有的研究材料從書桌搬到了餐桌,以做菜來輔助研究,餓的話馬上補充體力。

平常雖然沒有那麼喜歡豆腐,但豆腐不僅好切、還能增進空間幾何的思考,更可以照顧到五臟廟,在廚房實作數學效果意外倍增!老實說,這麼可愛的幾何豆腐還真讓人有點捨不得吃掉呢。

圖8/作者提供

切完豆腐和著其他食材煮湯飽食一頓以後,問題也快解完了。最後的步驟是沿著另一個對稱面群繼續分割,即使副對稱面群分割出的塊體並不全然相同,但最終結果為一單位四面體,其底面為 1/4 正方形面積的等腰直角三角形,高為立方體邊長的 1/2,體積各佔吠陀立方的 1/24,如圖 9。

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

原先主對稱面群分割的 MSP 四面體(1/6 立方體體積)會被副對稱面群的邊界條件分為形狀相等的 4 小塊;而副對稱面群分割出的塊體則有二種情況,第一種為 SSP 六面體(1/4 立方體體積)將會被主對稱面群的邊界條件分為形狀相等的 6 小塊,第二種情況則是 SSP 四面體(1/12 立方體體積)將被分為形狀相等的 2 小塊。

圖9|主對稱面群(MSP)與副對稱面群(SSP)共六個對稱面的分割結果。(a)主對稱面群分割後為 1/6 立方體體積的 MSP 四面體,與圖 6e 相同;(b) 副對稱面群的交集為兩種類型的塊體,第一種為體積 1/4 的 SSP 六面體,與圖 7a 相同;(c) 則為三個副對稱面群的第二種交集類型,為體積 1/12 的 SSP 四面體,與圖 7d 相同;(d) 為 a 與 b圖的聯集;(e) 則是 a 與 b圖的交集;(f) 為 a 與 c 圖的聯集;(g) 則為 a 與 c 圖的交集部分。最後的分割結果為 24 個全等的四面體,e 與 g 為其中的二個。

無論由主對稱面群或是從副對稱面群開始分割,得到的結果相同,為 24 塊全等的四面體如圖 10,稱之為吠陀立方單位四面體(unit tetrahedron of Vedic cube, UTVC),為三直角四面體(trirectangular tetrahedron),表示其中一個頂角包含三個直角。任一個 UTVC 已是最小不重複的基本元素,可沿著對稱面群鏡射六次得到原先的吠陀立方。

圖10/作者提供

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

也就是說,我們只要列出 UTVC 裡面的位數根 1、2、3、4 座標點位(可藉由旋轉分別得到位數根 8、7、6、5,如吠陀方形的位數根胚騰),就可以將原先複雜的座標點位分布,簡化成不能再簡化的胚騰。

表1列出了位數根 1、2、3、4 在 4 個 UTVC 中的座標點位。表中的點包含了邊界條件上的點,這些點會被數個 UTVC 同時共用。UTVC 中的位數根座標點沿著對稱面群確實能鏡射出其他位數根座標點,而每個 UTVC 中座標點構成的向量也相同。

  • 表1|位數根 1、2、3、4 在 4 個 UTVC 中的座標點。

從二維平面至三維空間,吠陀立方的更多應用

吠陀立方的發展是從二維平面至三維空間,其簡化是了解三維空間的位數根胚騰性質的重要步驟。從對稱面群解構的方法可大幅簡化吠陀立方的複雜度,也可找出三維空間的基本元素,不再限於吠陀方形於二維平面隱含的圖樣與規律(樓層法)。

位數根於吠陀立方散布的胚騰,是大自然本身形成的奧妙形態,除了純數學研究或是建構演算規則外,也許能和分子晶體、空間、藝術或是建築等相關領域結合應用。像是行為藝術教母瑪莉娜·阿布拉莫維奇(Marina Abramović)與她的夥伴曾在Nightsea Crossing的作品中,根據吠陀方形而決定各自所穿的衣服顏色。

%e5%80%ab%e6%95%a6%e8%9b%87%e5%bd%a2%e8%97%9d%e5%bb%8a2002%e5%bb%ba%e7%af%89%e7%89%a9%e5%a4%96%e8%a7%80
倫敦蛇形藝廊 2002 建築物外觀。圖/Balmond Studio 授權使用

吠陀立方是受到古印度數學吠陀方形、伊斯蘭幾何圖樣、倫敦蛇形藝廊 2002 的啟發,跨越數千年與東西方文化最終在台灣這個文化交融之地產生的數學。我身為吠陀立方的發明與發現者,特別期待未來有人能受到啟發,將吠陀立方的概念運用於建築設計或藝術創作,就像是塞西爾.巴爾蒙德(Cecil Balmond)運用演算法把正方形轉化成蛇形藝廊 2002 那樣令人驚艷。

對我來說,數學與藝術是兩面鏡子,可以一直相互映射彼此的光亮;而東方和西方,也能夠不斷跨越邊界彼此對話與啟發。

後續,我們再來聊聊如何將吠陀立方轉化成數學藝術創作。

參考資料

  1. Lin, C. Y. Digital Root Patterns of Three-Dimensional Space. Recreational Mathematics Magazine, 3(5), 9–31, 2016.
  2. Jones, L. “Mathematics and Islamic art”, Mathematics in School, 18(4), 32–35, 1989.
Sharkie Lin_96
24 篇文章 ・ 6 位粉絲
在國二無聊的早自習意外發現數學的趣味,因此近來體驗到數學研究、藝術創作、採訪寫作、展覽策劃、資優教育等工作。不是念數學也不是學藝術,但樂於從多元視角聊聊數學的各種姿態,以及進行數學藝術創作,希望能為世界帶來一點樂趣。科普部落格〈鯊奇事務所〉https://medium.com/sharkie-studio,聯絡信箱 sharkgallium@gmail.com