Loading [MathJax]/extensions/tex2jax.js

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

0

1
0

文字

分享

0
1
0
拆解邊緣AI熱潮:伺服器如何提供穩固的運算基石?
鳥苷三磷酸 (PanSci Promo)_96
・2025/05/21 ・5071字 ・閱讀時間約 10 分鐘

本文與 研華科技 合作,泛科學企劃執行。

每次 NVIDIA 執行長黃仁勳公開發言,總能牽動整個 AI 產業的神經。然而,我們不妨設想一個更深層的問題——如今的 AI 幾乎都倚賴網路連線,那如果哪天「網路斷了」,會發生什麼事?

想像你正在自駕車打個盹,系統突然警示:「網路連線中斷」,車輛開始偏離路線,而前方竟是萬丈深谷。又或者家庭機器人被駭,開始暴走跳舞,甚至舉起刀具向你走來。

這會是黃仁勳期待的未來嗎?當然不是!也因為如此,「邊緣 AI」成為業界關注重點。不靠雲端,AI 就能在現場即時反應,不只更安全、低延遲,還能讓數據當場變現,不再淪為沉沒成本。

什麼是邊緣 AI ?

邊緣 AI,乍聽之下,好像是「孤單站在角落的人工智慧」,但事實上,它正是我們身邊最可靠、最即時的親密數位夥伴呀。

當前,像是企業、醫院、學校內部的伺服器,個人電腦,甚至手機等裝置,都可以成為「邊緣節點」。當數據在這些邊緣節點進行運算,稱為邊緣運算;而在邊緣節點上運行 AI ,就被稱為邊緣 AI。簡單來說,就是將原本集中在遠端資料中心的運算能力,「搬家」到更靠近數據源頭的地方。

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

那麼,為什麼需要這樣做?資料放在雲端,集中管理不是更方便嗎?對,就是不好。

當數據在這些邊緣節點進行運算,稱為邊緣運算;而在邊緣節點上運行 AI ,就被稱為邊緣 AI。/ 圖片來源:MotionArray

第一個不好是物理限制:「延遲」。
即使光速已經非常快,數據從你家旁邊的路口傳到幾千公里外的雲端機房,再把分析結果傳回來,中間還要經過各種網路節點轉來轉去…這樣一來一回,就算只是幾十毫秒的延遲,對於需要「即刻反應」的 AI 應用,比如說工廠裡要精密控制的機械手臂、或者自駕車要判斷路況時,每一毫秒都攸關安全與精度,這點延遲都是無法接受的!這是物理距離與網路架構先天上的限制,無法繞過去。

第二個挑戰,是資訊科學跟工程上的考量:「頻寬」與「成本」。
你可以想像網路頻寬就像水管的粗細。隨著高解析影像與感測器數據不斷來回傳送,湧入的資料數據量就像超級大的水流,一下子就把水管塞爆!要避免流量爆炸,你就要一直擴充水管,也就是擴增頻寬,然而這樣的基礎建設成本是很驚人的。如果能在邊緣就先處理,把重要資訊「濃縮」過後再傳回雲端,是不是就能減輕頻寬負擔,也能節省大量費用呢?

第三個挑戰:系統「可靠性」與「韌性」。
如果所有運算都仰賴遠端的雲端時,一旦網路不穩、甚至斷線,那怎麼辦?很多關鍵應用,像是公共安全監控或是重要設備的預警系統,可不能這樣「看天吃飯」啊!邊緣處理讓系統更獨立,就算暫時斷線,本地的 AI 還是能繼續運作與即時反應,這在工程上是非常重要的考量。

所以你看,邊緣運算不是科學家們沒事找事做,它是順應數據特性和實際應用需求,一個非常合理的科學與工程上的最佳化選擇,是我們想要抓住即時數據價值,非走不可的一條路!

邊緣 AI 的實戰魅力:從工廠到倉儲,再到你的工作桌

知道要把 AI 算力搬到邊緣了,接下來的問題就是─邊緣 AI 究竟強在哪裡呢?它強就強在能夠做到「深度感知(Deep Perception)」!

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

所謂深度感知,並非僅僅是對數據進行簡單的加加減減,而是透過如深度神經網路這類複雜的 AI 模型,從原始數據裡面,去「理解」出更高層次、更具意義的資訊。

研華科技為例,旗下已有多項邊緣 AI 的實戰應用。以工業瑕疵檢測為例,利用物件偵測模型,快速將工業產品中的瑕疵挑出來,而且由於 AI 模型可以使用同一套參數去檢測,因此品管上能達到一致性,減少人為疏漏。尤其在高產能工廠中,檢測速度必須快、狠、準。研華這套 AI 系統每分鐘最高可處理 8,000 件產品,替工廠節省大量人力,同時確保品質穩定。這樣的效能來自於一台僅有膠囊咖啡機大小的邊緣設備—IPC-240。

這樣的效能來自於一台僅有膠囊咖啡機大小的邊緣設備—IPC-240。/ 圖片提供:研華科技

此外,在智慧倉儲場域,研華與威剛合作,研華與威剛聯手合作,在 MIC-732AO 伺服器上搭載輝達的 Nova Orin 開發平台,打造倉儲系統的 AMR(Autonomous Mobile Robot) 自走車。這跟過去在倉儲系統中使用的自動導引車 AGV 技術不一樣,AMR 不需要事先規劃好路線,靠著感測器偵測,就能輕鬆避開障礙物,識別路線,並且將貨物載到指定地點存放。

當然,還有語言模型的應用。例如結合檢索增強生成 ( RAG ) 跟上下文學習 ( in-context learning ),除了可以做備忘錄跟排程規劃以外,還能將實務上碰到的問題記錄下來,等到之後碰到類似的問題時,就能詢問 AI 並得到解答。

你或許會問,那為什麼不直接使用 ChatGPT 就好了?其實,對許多企業來說,內部資料往往具有高度機密性與商業價值,有些場域甚至連手機都禁止員工帶入,自然無法將資料上傳雲端。對於重視資安,又希望運用 AI 提升效率的企業與工廠而言,自行部署大型語言模型(self-hosted LLM)才是理想選擇。而這樣的應用,並不需要龐大的設備。研華的 SKY-602E3 塔式 GPU 伺服器,體積僅如後背包大小,卻能輕鬆支援語言模型的運作,實現高效又安全的 AI 解決方案。

但問題也接著浮現:要在這麼小的設備上跑大型 AI 模型,會不會太吃資源?這正是目前 AI 領域最前沿、最火熱的研究方向之一:如何幫 AI 模型進行「科學瘦身」,又不減智慧。接下來,我們就來看看科學家是怎麼幫 AI 減重的。

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

語言模型瘦身術之一:量化(Quantization)—用更精簡的數位方式來表示知識

當硬體資源有限,大模型卻越來越龐大,「幫模型減肥」就成了邊緣 AI 的重要課題。這其實跟圖片壓縮有點像:有些畫面細節我們肉眼根本看不出來,刪掉也不影響整體感覺,卻能大幅減少檔案大小。

模型量化的原理也是如此,只不過對象是模型裡面的參數。這些參數原先通常都是以「浮點數」表示,什麼是浮點數?其實就是你我都熟知的小數。舉例來說,圓周率是個無窮不循環小數,唸下去就會是3.141592653…但實際運算時,我們常常用 3.14 或甚至直接用 3,也能得到夠用的結果。降低模型參數中浮點數的精度就是這個意思! 

然而,量化並不是那麼容易的事情。而且實際上,降低精度多少還是會影響到模型表現的。因此在設計時,工程師會精密調整,確保效能在可接受範圍內,達成「瘦身不減智」的目標。

當硬體資源有限,大模型卻越來越龐大,「幫模型減肥」就成了邊緣 AI 的重要課題。/ 圖片來源:MotionArray

模型剪枝(Model Pruning)—基於重要性的結構精簡

建立一個 AI 模型,其實就是在搭建一整套類神經網路系統,並訓練類神經元中彼此關聯的參數。然而,在這麼多參數中,總會有一些參數明明佔了一個位置,卻對整體模型沒有貢獻。既然如此,不如果斷將這些「冗餘」移除。

這就像種植作物的時候,總會雜草叢生,但這些雜草並不是我們想要的作物,這時候我們就會動手清理雜草。在語言模型中也會有這樣的雜草存在,而動手去清理這些不需要的連結參數或神經元的技術,就稱為 AI 模型的模型剪枝(Model Pruning)。

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

模型剪枝的效果,大概能把100變成70這樣的程度,說多也不是太多。雖然這樣的縮減對於提升效率已具幫助,但若我們要的是一個更小幾個數量級的模型,僅靠剪枝仍不足以應對。最後還是需要從源頭著手,採取更治本的方法:一開始就打造一個很小的模型,並讓它去學習大模型的知識。這項技術被稱為「知識蒸餾」,是目前 AI 模型壓縮領域中最具潛力的方法之一。

知識蒸餾(Knowledge Distillation)—讓小模型學習大師的「精髓」

想像一下,一位經驗豐富、見多識廣的老師傅,就是那個龐大而強悍的 AI 模型。現在,他要培養一位年輕學徒—小型 AI 模型。與其只是告訴小型模型正確答案,老師傅 (大模型) 會更直接傳授他做判斷時的「思考過程」跟「眉角」,例如「為什麼我會這樣想?」、「其他選項的可能性有多少?」。這樣一來,小小的學徒模型,用它有限的「腦容量」,也能學到老師傅的「智慧精髓」,表現就能大幅提升!這是一種很高級的訓練技巧,跟遷移學習有關。

舉個例子,當大型語言模型在收到「晚餐:鳳梨」這組輸入時,它下一個會接的詞語跟機率分別為「炒飯:50%,蝦球:30%,披薩:15%,汁:5%」。在知識蒸餾的過程中,它可以把這套機率表一起教給小語言模型,讓小語言模型不必透過自己訓練,也能輕鬆得到這個推理過程。如今,許多高效的小型語言模型正是透過這項技術訓練而成,讓我們得以在資源有限的邊緣設備上,也能部署愈來愈強大的小模型 AI。

但是!即使模型經過了這些科學方法的優化,變得比較「苗條」了,要真正在邊緣環境中處理如潮水般湧現的資料,並且高速、即時、穩定地運作,仍然需要一個夠強的「引擎」來驅動它們。也就是說,要把這些經過科學千錘百鍊、但依然需要大量計算的 AI 模型,真正放到邊緣的現場去發揮作用,就需要一個強大的「硬體平台」來承載。

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

邊緣 AI 的強心臟:SKY-602E3 的三大關鍵

像研華的 SKY-602E3 塔式 GPU 伺服器,就是扮演「邊緣 AI 引擎」的關鍵角色!那麼,它到底厲害在哪?

一、核心算力
它最多可安裝 4 張雙寬度 GPU 顯示卡。為什麼 GPU 這麼重要?因為 GPU 的設計,天生就擅長做「平行計算」,這正好就是 AI 模型裡面那種海量數學運算最需要的!

你想想看,那麼多數據要同時處理,就像要請一大堆人同時算數學一樣,GPU 就是那個最有效率的工具人!而且,有多張 GPU,代表可以同時跑更多不同的 AI 任務,或者處理更大流量的數據。這是確保那些科學研究成果,在邊緣能真正「跑起來」、「跑得快」、而且「能同時做更多事」的物理基礎!

二、工程適應性——塔式設計。
邊緣環境通常不是那種恆溫恆濕的標準機房,有時是在工廠角落、辦公室一隅、或某個研究實驗室。這種塔式的機箱設計,體積相對緊湊,散熱空間也比較好(這對高功耗的 GPU 很重要!),部署起來比傳統機架式伺服器更有彈性。這就是把高性能計算,進行「工程化」,讓它能適應台灣多樣化的邊緣應用場景。

三、可靠性
SKY-602E3 用的是伺服器等級的主機板、ECC 糾錯記憶體、還有備援電源供應器等等。這些聽起來很硬的規格,背後代表的是嚴謹的工程可靠性設計。畢竟在邊緣現場,系統穩定壓倒一切!你總不希望 AI 分析跑到一半就掛掉吧?這些設計確保了部署在現場的 AI 系統,能夠長時間、穩定地運作,把實驗室裡的科學成果,可靠地轉化成實際的應用價值。

-----廣告,請繼續往下閱讀-----
研華的 SKY-602E3 塔式 GPU 伺服器,體積僅如後背包大小,卻能輕鬆支援語言模型的運作,實現高效又安全的 AI 解決方案。/ 圖片提供:研華科技

台灣製造 × 在地智慧:打造專屬的邊緣 AI 解決方案

研華科技攜手八維智能,能幫助企業或機構提供客製化的AI解決方案。他們的技術能力涵蓋了自然語言處理、電腦視覺、預測性大數據分析、全端軟體開發與部署,及AI軟硬體整合。

無論是大小型語言模型的微調、工業瑕疵檢測的模型訓練、大數據分析,還是其他 AI 相關的服務,都能交給研華與八維智能來協助完成。他們甚至提供 GPU 與伺服器的租借服務,讓企業在啟動 AI 專案前,大幅降低前期投入門檻,靈活又實用。

台灣有著獨特的產業結構,從精密製造、城市交通管理,到因應高齡化社會的智慧醫療與公共安全,都是邊緣 AI 的理想應用場域。更重要的是,這些情境中許多關鍵資訊都具有高度的「時效性」。像是產線上的一處異常、道路上的突發狀況、醫療設備的即刻警示,這些都需要分秒必爭的即時回應。

如果我們還需要將數據送上雲端分析、再等待回傳結果,往往已經錯失最佳反應時機。這也是為什麼邊緣 AI,不只是一項技術創新,更是一條把尖端 AI 科學落地、真正發揮產業生產力與社會價值的關鍵路徑。讓數據在生成的那一刻、在事件發生的現場,就能被有效的「理解」與「利用」,是將數據垃圾變成數據黃金的賢者之石!

👉 更多研華Edge AI解決方案
👉 立即申請Server租借

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

討論功能關閉中。

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
如果數學是藝術創作的繆思女神?來自全球的數學藝術展覽── Bridges 2018 研討會(上)
Sharkie Lin_96
・2018/12/27 ・3946字 ・閱讀時間約 8 分鐘 ・SR值 534 ・七年級

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

如果數學是藝術創作的繆思女神,世界上可是有一群人每年聚在一起,搶著分享和女神約會的心得,這個奇特的聚會就是 Bridges 全球數學藝術研討會!

Bridges 從 1998 年開始舉辦,是個一年一度以數學為主的大型全球聚會,結合藝術、音樂、建築、教育與文化,是國際間知名的跨領域會議,任何有趣的超展開都可能在此發生。

今年 (2018) 的 Bridges 在瑞典斯德哥爾摩的科技博物館 (Tekniska Museet) 展開,會議從 7/25 至 7/29 共為期五天,包含最後一天的郊遊日。Bridges 從 2001 年開始每年舉辦數學藝術展覽,是全球最大的盛會,今年總共展示了一百多件來自全球的作品,其中台灣有四位數學藝術家前去參展,撰寫這篇文章的我也是參展者之一。

Bridges 2018文宣。
圖/Bridges 2018

在諾貝爾獎演說地點開啟 Bridges

Bridges 2018 開幕選在諾貝爾獎得主演說的地點 ── 斯德哥爾摩大學的講堂  (Aula Magna of Stockholm University)[註 1],充滿設計感與科學意義的講堂讓人沉浸在知識與美的氛圍中。

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

第一位分享者正好是諾貝爾物理獎 2004 年得主弗朗克·韋爾切克 (Frank Wilczek) 談論科學與藝術的交集,另外兩場分享則分別是數學家考爾姆·穆爾卡 (Colm Mulcahy) 的紙牌魔術表演,以及由數學家桃樂絲·舒特內德 (Doris Schattschneider) 介紹家庭主婦瑪喬里·賴斯 (Marjorie Rice,1923–2017) 發現五邊形鋪磚型態的傳奇故事,正好也是科技博物館的遊樂場「數學花園」的迎賓廊道。(可見「瑞典科技博物館數學花園:融合數感、美感、體感設計的北歐遊樂場」一文。)

瑞典科技博物館「數學花園」概念圖。
圖/Tekniska Museet

這次會議地點在斯德哥爾摩的博物館公園,參加不同場次需要穿梭在各博物館,彷彿跨越知識間的藩籬,同時呼應 Bridges 的跨域精神,這樣的安排相較一般制式的固定地點讓人有著特別的感受。在會議期間,科技博物館、民族學博物館、表演藝術博物館、諾貝爾博物館也都有專門為 Bridges 參與者特別安排導覽解說與免費參觀時段,讓人體驗到主辦方的用心以及歐洲博物館的精緻內容。

跨界的不只是博物館,Bridges 本身就是以多元的論文展覽活動在國際間著名。會議期間每天都非常充實與豐富,從早到晚滿滿的數學藝術(詳細議程),可以看到數學與各類藝術甚至科技相互撞擊,遇到全球的數學藝術同好更是讓人覺得興奮!

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

來自台灣的數學藝術展覽

關注了 Bridges 好一陣子,今年我終於鼓起勇氣報名,非常幸運地通過徵選並且獲得國藝會贊助,因此能有機會 Bridges 2018 全球數學藝術展覽中展出。本屆展覽台灣四位參展藝術家皆安排在 General Exhibition Gallery(GE) 展出,除了作品本身,在 GE 展廳還可以展示相關的物件,因此我放置了〈對稱的鏡面〉的作品說明、原始論文與 3D 列印模型,希望讓觀眾可以完整了解創作緣由。

Symmetric Mirrors(對稱的鏡面),Shark Lin(林家妤)。
攝影/Shark Lin

〈對稱的鏡面〉是根據我發明 / 發現的吠陀立方數學原理製作而成,將立方體的六個對稱面以鏡面材料呈現(延伸閱讀:吠陀立方對稱面法:解不出的空間幾何問題就到廚房解決吧!),會隨著現場燈光而呈現不同的反射與錯視效果,觀眾還可以用雷射筆或其他物體與作品互動,觀察鏡中成像變化 [註 2]。

雷射光打在〈對稱的鏡面〉形成之反射。
攝影/Shark Lin

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

展覽期間有許多觀眾來看作品,甚至到撤展時段都還有一群瑞典青少年包圍展位;而作品本身也獲得許多不錯的評價,像是紐約數學博物館 (MoMath) 館長 Cindy Lawrence 覺得〈對稱的鏡面〉讓人十分驚艷。能夠在國際舞台讓世界看見台灣的作品,對第一次參加 Bridges 展覽的我來說更是別具意義。

今年 Bridges 數學藝術展覽中,台灣一共有四位來自不同領域的參展者與作品:分別是工程背景的我(林家妤,Shark Lin)、金必耀教授(Bih-Yaw Jin)團隊的化學串珠、陳明璋教授(Mingjang Chen)的碎形疊代畫作,以及施宣光教授(Shen-Guan Shih)的巧蝸積木 (SL blocks)。

Bead model for the Type I & II clathrate hydrates,左家靜與金必耀。
攝影/Shark Lin

Castle emerging above clouds,陳明璋。
攝影/Shark Lin

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

Break a symmetry,施宣光。
攝影/Shark Lin

我們創作的詳細介紹可見 Bridges 線上藝廊與論文集,以及李國偉教授科學人 2018 年 9 月號的專文「連結數學、藝術與教育的橋樑」一文,該期另有科普作家斯蒂芬·奧內斯 (Stephen Ornes)的專文「數的藝術品」。

Bridges 裡令人驚豔的作品

除了台灣的作品外,我也很想完整介紹全世界的數學藝術作品,不過 Bridges 2018 的參展作品就有一百多件,論文數量也破百篇,就算在天橋底下說書把這幾天的事情拆成九篇也說不完哪,只好精選幾件有趣的作品來介紹。

首先是首獎作品,來自荷蘭的兩位藝術家創作了一件能夠同時表現四個圖像的錯視創作,而他們選定的主題是全世界最有名的四張臉 ── 披頭四。他們利用 3D 列印印出截角八面體 (truncated octahedrons) 上圖像元素,搭配夾角 90 度的兩片鏡面相互反射,就可以用一個物體神奇地同時呈現出四個圖像。

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

值得一提的是,他們在 Bridges 2016 也是以三維錯視創作拿到首獎,分別以 Gödel, Escher, Bach: an Eternal Golden Braid(中文書名:哥德爾、艾舍爾、巴赫:集異璧之大成)這本書三位大師的頭像作為創作主題。

Four Fabulous Beatles Faces in a 3D Object,Walt van Ballegooijen and Hans Kuiper。
攝影/Shark Lin

艾雪式的鑲嵌圖樣向來深受藝術家與大眾喜愛,來自德國同時修習數學與平面設計的 Alexander Guerten,創作了動物造型的 3D 鑲嵌作品令人驚歎。前幾個月才在推特上看過,沒想到竟然能在 Bridges 的展覽會場見到,讓人驚喜連連!

KUHKUBUS,Alexander Guerten。
攝影/Shark Lin

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

在我展位隔壁的藝術家是來自瑞典的 Erik Åberg,他發展了 GHOSTKUBE 可轉動的方塊組,最近還上了 kickstarter 募資。

有天我在餐廳用餐時,看見隔壁東方面孔女性的幾何摺紙造型包包,似乎在哪裡看過卻又想不起來? 懷著好奇心就決定向對方搭訕交流。

ANTIPRISMS – Porcelain,Uyen Nguyen。
圖/WINWIN

對方拿出名片之後,我才發覺她就是奇美博物館摺紙大展《紙上奇蹟》策展人嬴嬴 (Uyen Nguyen),所以對這個摺紙造型包有印象。正好我之前寫的幾何藝術走春文章中,有推薦過這檔展覽(延伸閱讀:新年科青走春!全台幾何藝術景點大搜查),也讓我們聊了許久。最後一天在諾貝爾博物館參訪時,她還贈送我鑲嵌摺紙作品留作紀念。

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

左側為本文作者 Shark Lin,右側為奇美博物館《紙上奇蹟》策展人嬴嬴 (Uyen Nguyen) 與摺紙作品
圖/作者提供。

最讓我喜出望外的是,以錯視作品享譽全球的杉原厚吉(Kokichi Sugihara)教授也在Bridges 2018分享他的創作。我曾經在《錯視維度》展覽邀請他的作品〈Ambiguous Cylinder Illusion〉參展 [註 4],終於見到本人才發現這次來Bridges其實是來朝聖的!

杉原厚吉(Kokichi Sugihara)教授於Bridges 2018分享錯視創作與原理,圖中為〈Ambiguous Cylinder Illusion〉。
攝影/Shark Lin

與杉原厚吉教授合影,我們手中拿的是《錯視維度》酷卡。 圖/作者提供。

以上作品約略只佔了 Bridges 的 5%,若是想看所有作品下方有相關網站。這篇文章主要介紹數學藝術展覽,下回我要來聊聊 Bridges 裡頭更多數學的跨界想像力!

延伸閱讀

Bridges 2018相關網站

  1. 官方網站
  2. 線上藝廊
  3. 相關活動
  4. 論文集
  5. 詳細議程

註釋

  • 註 1:諾貝爾獎頒獎則是在斯德哥爾摩音樂廳 (Stockholm Concert Hall),晚宴則在市政廳 (Stockholm City Hall)。
  • 註 2:本次參展作品〈對稱的鏡面〉為吠陀立方系列創作,曾經在圓山花博《視覺混種 On Site, Visual》、2016 泛‧知識節《數學藝術互動體驗》、靜宜大學《IMAGINARY 超越無限‧數學印象特展》展示過,而今年在瑞典展出版本為鏡面全反射改良版本。
  • 註 3:Bridges 是一個以數學為基礎的展覽,因此作品投件時藝術家需要選擇分類與提供說明,以便評審委員審查,Bridges 的作品分類與徵選標準如下:
    (1) 2D 作品(如鑲嵌、不可能的圖形、對稱設計)
    (2) 3D 作品(多面體、摺紙)
    (3) 自然界中特別的數字與數學(費氏數列、黃金比例)
    (4) 拓樸學(莫比烏斯帶、最小能量表面、扭結、圖論等)
    (5) 演算藝術(奇異吸子、基於代數方程式的藝術、排列、魔方陣)
    (6) 碎形
    而徵選標準有以下五項標準,括弧裡的字為官方註解:
    (1) 數學內容(這裡有數學知識豐富的觀眾)
    (2) 美感(顯然這相當主觀)
    (3) 材質(多樣的材質會讓展覽更多元)
    (4) 工藝技術(可有效地傳達作品概念)
    (5) 創新與原創性(將數學藝術推往新方向)
  • 註 4:杉原厚吉教授於2018年10月受邀來台,並且於台灣大學主辦之「實 ‧ 幻:視覺錯覺之探索與應用 國際研討會」主講(Betwixt Reality and Illusion: International Symposium on the Exploration and Application of Visual Illusions);而我也在此研討會上分享〈對稱的鏡面〉作品中的錯視現象,以及《錯視維度》展覽內容與策展過程,相關報導可見此(連結)。

本次旅行獲得財團法人國家文化藝術基金會(國藝會)國際交流計畫補助。

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