大力出奇跡:當古代數學難題遇到計算機

近年來,人工智能的春風不知吹動了多少資本的浪潮,從決勝棋壇的阿爾法狗,到遍地開花的無人車,AI成為經濟寒冬裡熊熊燃燒的火種,不知多少投資客捧著鈔票前赴後繼。科幻電影中,像人類一樣思考、決策、學習的強人工智能何時能問世,目前還是個未解之謎。當前市面上一切AI產品的基礎,仍然是傳統的電子計算機。

我們知道,計算機科學中有一個“摩爾定律”: 單位面積集成電路上可容納的元器件的數目,大約每18個月便會增加一倍,其性能也將提升一倍。計算機指數式增長的運算能力,支撐了越來越複雜的應用場景。以棋類運動而言,上世紀末的計算機已經能戰勝最優秀的人類國際象棋棋手;而隨著計算機硬件的發展、運算能力的提升,比國際象棋計算量更大、場景更復雜的圍棋也最終失守。

也就是說,大多數情況下,用計算機解決人類問題的標準思路,都是用計算機強大的運算能力,來強行攻克人類思維範疇裡很難通過計算解決的問題。換言之,計算機擅長大力出奇跡。

當這一思路遭遇古代數學難題,又能碰撞出怎樣的火花?

大力出奇跡:當古代數學難題遇到計算機

1、百雞問題

今有雞翁一,值錢伍;雞母一,值錢三;雞雛三,值錢一。凡百錢買雞百隻,問雞翁、母、雛各幾何?

這個問題其實是一個不定方程求整數解的問題,相當於列方程+枚舉討論。具體而言,可以設公雞數量為x,母雞數量為y,小雞數量為z。有:

x + y + z = 100

5x + 3y + z/3 = 100

枚舉討論的技巧也很簡單,可以先消去一個未知數,然後根據正整數性質,利用整除特性進行枚舉。

顯而易見計算機最擅於求解這種枚舉類的問題,甚至用暴力枚舉(除基本條件外,不加分析和簡化)也花不了多少時間。比如從0開始枚舉上述的公雞數,最多不會超過20只,否則總價格會超出百錢;在此基礎上開始枚舉母雞,母雞最多不會超過33只,否則總價會超出百錢;然後再在已數公雞、母雞的基礎上開始枚舉小雞,挑出精確滿足百雞、百錢的組合。

貼一下python代碼與計算答案。如果你對編程或python感興趣的話,完全可以搜索一些在線的教程來學習,這是一門十分簡單、適合初學者入門的編程語言,如果有一些英語和數學基礎,更能十分輕易地學會。可以看出,在0.2s時間內,該程序利用暴力枚舉的手段,給出了百雞問題的全部四組解。

大力出奇跡:當古代數學難題遇到計算機

大力出奇跡:當古代數學難題遇到計算機

2、求圓周率 中國古代對圓周率的計算有很長的歷史。

早在漢初的《周髀算經》裡就提到過“徑一週三”的說法,給出了圓周率的近似值3。漢代張衡給出近似值3.16,而劉徽創立割圓術,“割之彌細,所失彌少,割之又割,以至於不可割,則與圓周合體而無所失矣”,我個人認為可以被當做數學領域極限及微積分的起源,最終他得到3.1416的近似值。南朝祖沖之發揚光大,不割不快,得到了3.1415926~3.1415927的近似範圍,比西方國家不知早到哪裡去了。

當然我們今天不用割圓術。不是不能用,而是割圓術不太容易展現計算機的運算優勢,以及大力出奇跡的計算思想。我們採用一種樸素的概率方法。設想有一個正方形,邊長為1。我們可以用該正方形兩條相鄰的邊作為半徑,畫一個四分之一圓弧。現在想象我們往這個正方形裡隨機地撒豆子(天知道我們怎樣保證隨機,大概就是閉著眼睛抓著豆子胡亂撒吧)。假如豆子足夠小,足夠多,最終這個正方形裡密密麻麻到處是豆子。接下來我們開始數豆子,數出所有正方形裡的豆子數目,N;同時也數出,落在圓弧圈出的扇形區域裡的豆子數目,n。有了這兩個值,就可以用來估計π。

大力出奇跡:當古代數學難題遇到計算機

直觀而言,n與N的比值,應當近似等於扇形(也就是四分之一圓)面積與正方形面積的比值。而在計算扇形面積的時候,顯然是需要用到π值的,這裡的四分之一圓面積為π/4。也就是說存在近似關係:

n : N ≈ π/4 : 1

從而可以得到,π≈ 4n/N。

同樣編寫一個python程序。可以看出,隨機撒下的豆子越多,最終的模擬結果越精確。提到“模擬”,這一方法也就是大名鼎鼎的蒙特卡洛模擬,可以用來近似解決眾多難以計算的數學問題。

考慮到時間問題,此處不再做更高精度的計算。

大力出奇跡:當古代數學難題遇到計算機

大力出奇跡:當古代數學難題遇到計算機

3、根號2。 畢達哥拉斯學派的理論根基是萬物皆數。這裡的數指的是整數,和可以用整數相除表達的分數。他們認為自然界中的一切,都可以用整數和分數來表達。

然而恰恰是學派中的一名晚輩,希帕索斯,對這個觀點提出了質疑。希帕索斯正是利用到老師歸納的畢達哥拉斯定理(也就是西方人的勾股定理),提出:如果說萬物皆數,那麼等腰直角三角形的斜邊,如何用整數或分數來表達呢?

畢達哥拉斯學派從此陷入了恐慌。一大群學者開始試圖計算、測量這個斜邊值,想要找到它的整數或分數表達形式,可是卻怎麼也求不出這個值。最終,這群人惱羞成怒,竟然把希帕索斯推入了大海。

我們現在知道,這個三角形的斜邊值是一個無理數,無法用分數形式表達。假如直角邊長為1的話,斜邊長則稱為根號二,其數值大約為1.414。那麼如何計算這一數值呢?

計算機解決的方案有很多。這裡採用最樸素的二分法。考慮函數f(x),要求其任一零點(也就是f(x)=0的點)附近,函數的值分別處於正負兩側。所謂二分法,簡單來說,是在求解此零點時,先找到零點左、右兩個端點,從這兩點出發,取區間的中點,並根據零點的位置,用新得到的中點取代某一個端點,然後不斷地逼近零點。

大力出奇跡:當古代數學難題遇到計算機

比如y = x^2 – 2在正軸的零點,顯然處在1和2之間。以這兩點為端點,取區間中點,為1.5,1.5的函數值為正,則接下來取1和1.5為端點……重複這個過程,直到某一步恰好求出了精確解(比如零點是個整數或分數),或者達到了精度要求(比如零點是個無理數),則停止迭代。這裡就以0.00001為精度標準,用二分法求解根號2。可以看出,在0.2s,15輪二分迭代後,得到了4位精度的結果。

事實上這道題我在一次算法工程師求職的面試中遇到過。不過我當時寫了一個運算效率更高的牛頓迭代法。當然,這就是另一個故事了。

大力出奇跡:當古代數學難題遇到計算機

大力出奇跡:當古代數學難題遇到計算機

今天展示了一些最基礎的計算方法,旨在理解用計算機求解複雜問題的思路(當然這些問題實際上也並不複雜)。那些困擾前人數十年數百年的問題,在計算機強大的運算能力面前,會顯得容易得多。這,就是計算機的核心能力。

在我個人的理解裡,計算機相比於人類的最大優勢,就是上述的計算能力,也就是計算速度,也就是大力出奇跡。以當前席捲互聯網行業的深度學習方法為例,事實上深度學習所依賴的神經網絡結構,在20世紀70年代美國的“人工智能熱潮”中就已經有許許多多的雛形,只不過因為當時計算機算力的限制而沒能早早登上歷史舞臺。而現在的各類深度學習AI算法,其實本質上也還是站在前人的肩膀上摘果子,這些年在圖像、語音領域取得的一些成果,本質是仍然蹭了計算機硬件能力爆炸式提升的紅利。對於算法本身,更多的仍是試探性結構設計。

在我看來,未來的人工智能之路,其實面臨著重大的分歧。一條路是走現在的老路,繼續堆硬件,加運算能力,期待量變到質變,也許當計算能力強大到某一個閾值的時候,弱AI與理論上的強AI就不會有太清晰的界限了。另一條就是另闢蹊徑,從仿生學的角度重新尋找AI的實現方法。究竟是揚長避短,算力為王,還是革故鼎新,開天闢地呢?

我們拭目以待。

相關推薦

推薦中...