0

0
0

文字

分享

0
0
0

數字感有什麼用?他把風靡千年的吠陀方形變立體了!

Sharkie Lin 林峽宇_96
・2016/12/31 ・2595字 ・閱讀時間約 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

0

0
0

文字

分享

0
0
0
為什麼越累越難睡?當大腦想下班,「腸道」卻還在加班!
鳥苷三磷酸 (PanSci Promo)_96
・2026/04/30 ・2519字 ・閱讀時間約 5 分鐘

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

本文與  益福生醫 合作,泛科學企劃執行

昨晚,你又在床上翻來覆去、無法入眠了嗎?這或許是現代社會最普遍的深夜共鳴。儘管換了昂貴的乳膠枕、拉上百分之百遮光的窗簾,甚至在腦海中數了幾百隻羊,大腦的那個「睡眠開關」卻彷彿生鏽般卡住。這種渴望休息卻睡不著的過程,讓失眠成了一場耗損身心的極限馬拉松 。

皮質醇:你體內那位「永不熄滅」的深夜警報器

要理解失眠,我們得先認識身體的一套精密防衛系統:下視丘-垂體-腎上腺軸(HPA axis) 。這套系統原本是演化給我們的禮物,讓我們在面對劍齒虎或突如其來的危險時,能迅速進入「戰鬥或快逃」的備戰狀態。當這套系統啟動,腎上腺就會分泌皮質醇 (壓力荷爾蒙),這種荷爾蒙能調動能量、提高警覺性,讓我們在危機中保持清醒 。

然而,現代人的「劍齒虎」不再是野獸,而是無止盡的專案進度、電子郵件與職場競爭。對於長期處於高壓或高強度工作環境的人們來說,身體的警報系統可能處於一種「切換不掉」的狀態。

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

在理想的狀態下,人類的生理時鐘像是一場精確的接力賽。入夜後,身體會進入「修復模式」,此時壓力荷爾蒙「皮質醇」的濃度應該降至最低點,讓「睡眠荷爾蒙」褪黑激素(Melatonin)接棒主導。褪黑激素不僅負責傳遞「天黑了」的訊號,它還能抑制腦中負責維持清醒的食慾素(Orexin)神經元,幫助大腦順利關閉覺醒開關。

對於長期處於高壓或高強度工作環境的人們來說,身體的警報系統可能處於一種「切換不掉」的狀態 / 圖片來源:envato

然而,當壓力介入時,這場接力賽就會變成跑不完的馬拉松賽。研究指出,長期的高壓環境會導致 HPA 軸過度活化,使得夜間皮質醇異常分泌。這不僅會抑制褪黑激素的分泌,更會讓食慾素在深夜裡持續活化,強迫大腦維持在「高覺醒狀態(Hyperarousal)」。 這種令人崩潰的狀態就是,明明你已經累到不行,但大腦卻像停不下來的發電機!

長期的睡眠不足會導致體內促發炎細胞激素上升,而發炎反應又會進一步活化 HPA 軸,分泌更多皮質醇來試圖消炎,高濃度的皮質醇會進一步干擾深層睡眠與快速動眼期(REM),導致睡眠品質變得低弱又破碎,最終形成「壓力-發炎-失眠」的惡行循環。也就是說,你不是在跟睡眠上的意志力作對,而是在跟失控的生理長期鬥爭。

從腸道重啟好眠開關:PS150 菌株如何調校你的生理時鐘

面對這種煞車失靈的失眠困局,科學家們將目光投向了人體內另一個繁榮的生態系:腸道。腸道與大腦之間存在著一條雙向通訊的高速公路,這就是「菌-腸-腦軸 (Microbiome-Gut-Brain Axis, MGBA)」,而某些特殊菌株不僅能幫助消化、排便,更能透過神經與內分泌途徑與大腦對話,直接參與調節我們的壓力調節與睡眠節律。這種菌株被科學家稱為「精神益生菌」(Psychobiotics)。

-----廣告,請繼續往下閱讀-----
腸道與大腦之間存在著一條雙向通訊的高速公路,這就是「菌-腸-腦軸 (Microbiome-Gut-Brain Axis, MGBA)」/圖片來源:益福生醫

在眾多研究菌株中,發酵乳桿菌 Limosilactobacillus fermentum PS150 的表現格外引人注目。PS150菌株源於亞洲益生菌權威「蔡英傑教授」團隊的專業研發,累積多年功能性菌株研發經驗的科學成果。針對臨床常見的「初夜效應」(First Night Effect, FNE),也就是現代人因出差、換床或環境改變導致的入睡困難,俗稱認床。科學家在進行實驗時發現,補充 PS150 菌株能顯著恢復非快速動眼期(NREM)的睡眠長度,且入睡更快,起床後也更容易清醒。更重要的是,不同於常見的藥物助眠手段(如抗組織胺藥物 DIPH)容易造成快速動眼期(REM)剝奪或導致睡眠破碎化,PS150 菌株展現出一種更為「溫和且自然」的調節力,它能有效縮短入睡所需的時間,並恢復睡眠中代表深層修復的「Delta 波」能量。

科學家發現,即便將 PS150 菌株經過特殊的熱處理(Heat-treated),轉化為不具活性但保有關鍵成分的「後生元」(Postbiotics),其生物活性依然能與活菌媲美 。HT-PS150 技術解決了益生菌在儲存與攝取過程中容易失去活性的痛點,讓這些腸道通訊員能更穩定地發揮作用 。

在臨床實驗中,科學家觀察到一個耐人尋味的現象:當詢問受試者的主觀感受時,往往會遇到強大的「安慰劑效應」,無論是服用 HT-PS150 還是安慰劑的人,主觀上大多表示睡眠變好了。這種「體感上的進步」有時會掩蓋真相,讓人分不清是心理作用還是真實效益。

然而,客觀的生理數據(Biomarkers)卻揭開了關鍵的差異。在排除主觀偏誤後,實驗數據顯示 HT-PS150 組有更高比例的人(84.6%)出現了夜間褪黑激素分泌增加,且壓力荷爾蒙(皮質醇)顯著下降,這證明了菌株確實啟動了體內的睡眠調控系統,而不僅僅是心理安慰。

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

最值得關注的是,對於那些失眠指數較高(ISI ≧ 8)的族群,這種「生理修復」與「主觀體感」終於達成了一致。這群人在補充 HT-PS150 後,不僅生理標記改善,連原本嚴重困擾的主觀睡眠效率、持續時間,以及焦慮感也出現了顯著的進步。

了解更多PS150助眠益生菌:https://lihi3.me/KQ4zi

重新定義深層睡眠:構建全方位的深夜修復計畫

睡眠從來就不只是單純的休息,而是一場生理功能的全面重整。想要重獲高品質的睡眠,關鍵在於為自己建立一個全方位的修復生態系。

這套系統的基石,始於良好的生活習慣。從減少睡前數位螢幕的干擾、優化室內環境,到作息調整。當我們透過規律作息來穩定神經系統,並輔以現代科學對於 PS150 菌株的調節力發現,身體便能更順暢地啟動睡眠開關,回歸自然的運作節律。

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

與其將失眠視為意志力的抗爭,不如將其看作是生理機能與腸道微生態的深度溝通。透過生活作息的調整與科學實證的支持,每個人都能擁有掌控睡眠的主動權。現在就從優化生活型態開始,為自己按下那個久違的、如嬰兒般香甜的關機鍵吧。

與其將失眠視為意志力的抗爭,不如將其看作是生理機能與腸道微生態的深度溝通 / 圖片來源 : envato

-----廣告,請繼續往下閱讀-----
文章難易度

討論功能關閉中。

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

0

0
0

文字

分享

0
0
0
肺部為何會「結疤」?揭開比癌症更致命的「菜瓜布肺」,科學家如何找到破解惡性循環的新契機
鳥苷三磷酸 (PanSci Promo)_96
・2026/05/08 ・2041字 ・閱讀時間約 4 分鐘

本文由 肺纖維化(菜瓜布肺)社團衛教 合作,泛科學撰文

在現代醫學的警示清單裡,乳癌、大腸癌這些疾病大家都不陌生;但有一個「隱蔽且致命」的威脅卻常被忽視,那就是「肺纖維化」。其中最常見的類型「特發性肺纖維化」(IPF),其預後往往不太樂觀,確診後的五年存活率甚至比許多常見的癌症還低。

首先,我們得先破解一個迷思:肺纖維化並不是單一疾病,而是許多種間質性肺病的共同表現。當我們聽到「肺纖維化」,腦中常浮現「菜瓜布肺」的形象,患者的肺部外觀充滿一個個空洞與疤痕,像極了乾燥的絲瓜。這精準描繪了肺部組織逐漸硬化、失去彈性的過程。

更重要的是,IPF 這類肺纖維化的威脅在於「不可逆」的特性,一旦形成就很難逆轉。這跟部分 COVID-19 康復者身上、仍有機會復原的肺纖維化,是兩種完全不同的概念。

-----廣告,請繼續往下閱讀-----
IPF 這類肺纖維化的威脅在於「不可逆」的特性,一旦形成就很難逆轉 / 圖示來源:shutterstock

肺部為何會變成「菜瓜布」?

為什麼好端端的肺會變成菜瓜布?這其實是一場身體修復機制失控的結果。

「纖維化」的組織,就是肺部間質組織(interstitium)的疤痕化。間質是圍繞在肺泡周圍,包含血管與支持肺部結構的結締組織。在正常情況下,肺部損傷後會啟動修復機制,並再生健康組織。但在肺纖維化的患者體內,這套修復機制卻「當機」了。

身體會不斷地發出訊號,導致負責修復工作的「纖維母細胞」(fibroblasts)被過度活化,進而失控地沉積膠原蛋白疤痕組織,最終在肺部形成永久性的纖維化。

科學家發現,這個過程之所以棘手,在於它是一個「惡性循環」,肺部同時存在著「發炎反應」與「纖維化」這兩條路徑 ,它們相互加乘,演變成難以阻斷的強大破壞力。

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

雖然特發性肺纖維化 (IPF) 的具體成因不明 ,但已知某些特定族群的風險更高。例如抽菸,特定年齡與性別(50歲以上男性)、長期暴露於粉塵環境的工作者(農業、畜牧業、採礦業…)、胃食道逆流者。此外,患有自體免疫疾病(如類風濕性關節炎、乾燥症、硬皮症、皮肌炎/多發性肌炎,)的患者,他們併發肺纖維化的機率遠高於一般人,必須特別警覺。

雖然特發性肺纖維化 (IPF) 的具體成因不明 ,但已知某些特定族群的風險更高。/ 圖示來源:shutterstock

打斷惡性循環的挑戰,為何只對抗「纖維化」還不夠?

面對這個不可逆的疾病,醫學界長年束手無策,直到 2014 年才迎來一道曙光。美國 FDA 批准了兩種機制不同的新藥:Nintedanib 和 Pirfenidone。這兩種藥物的出現是治療史上的分水嶺,首度被證實能夠「延緩」IPF 患者肺功能的惡化速度。

然而,這場戰役尚未結束。現有的治療雖然帶來了希望,卻也凸顯了「未被滿足的醫療需求」。從機制上來看,這些藥物主要抑制的是「纖維化路徑」。

這讓科學界開始思考這個未被滿足的棘手問題:既然疾病的本質是「發炎」與「纖維化」的雙重打擊,那麼,我們是否能找到「同時抑制」這兩條路徑的全新策略,從而更有效地打斷這個惡性循環?

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

找到同時調控「發炎」與「纖維化」的新靶點

為了解決難題,科學家將目光鎖定在一個細胞內的酵素:磷酸二酯酶 4B(PDE4B)

為什麼鎖定它?讓我們看看它的「雙重作用」機制:

  1. 關鍵位置: PDE4B 同時存在於免疫細胞(與發炎有關)與纖維母細胞(與纖維化有關)當中。
  2. 作用機制: PDE4B 的主要工作是降解細胞內一種叫 cAMP(環磷酸腺苷) 的訊號分子。cAMP 可以被視為細胞內的「穩定信號」。
  3. 雙重抑制: 當我們使用藥物抑制了 PDE4B 的活性,細胞內的 cAMP 就不會被分解,濃度會隨之升高。高濃度的 cAMP 能穩定免疫細胞和纖維母細胞,同時產生抗發炎抗纖維化的雙重效應。

簡單來說,鎖定並抑制 PDE4B,就像是同時抑制了免疫風暴與纖維化的工程,有望從雙從抑制打擊這個惡性循環。

全球臨床試驗帶來的新希望

近十年來,全球在肺纖維化領域投入了大量的臨床試驗,我們相信,在科學家逐步破解肺纖維化惡性循環的複雜難題後,期盼未來能為無數患者爭取到更安全、健康的生活與未來。

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

最後,我們必須再次提醒,特發性肺纖維化(IPF)與漸進性肺纖維化(PPF)是極具破壞性、且不可逆的疾病。面對這個比癌症更致命的對手,雖然現有的治療手段能延緩惡化,但無法逆轉已經形成的肺部疤痕組織,因此「早期診斷、早期治療」仍是對抗肺纖維化最重要的黃金時刻。

必須再次提醒,特發性肺纖維化(IPF)與漸進性肺纖維化(PPF)是極具破壞性、且不可逆的疾病。/ 圖示來源:


-----廣告,請繼續往下閱讀-----
文章難易度

討論功能關閉中。

鳥苷三磷酸 (PanSci Promo)_96
247 篇文章 ・ 319 位粉絲
充滿能量的泛科學品牌合作帳號!相關行銷合作請洽: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 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。