從開方算法看數學和計算機思維的差異（二）——計算機人怎麼想問題
- 2019 年 10 月 8 日
- 筆記
上回說到，以分析，代數，幾何，算術等為代表的的經典數學的思維方式和計算機科學背後的現代離散數學思維方式有着本質的區別。無論是從它們誕生的背景，為人所用的場景以及我們對它的理解方式，雖然都是數學，卻有着截然不同的文化。上一講我們以筆算開方的算法研究為例，談了談數學人的思維習慣和邏輯：
從開方算法看數學和計算機思維的差異（一）——數學人怎麼想問題
如果你還不太了解筆算開方算法或者想更好地全面吸收本系列文章的思想，建議先瀏覽一下上篇。
今天，我們來看看，面對同樣一個問題，計算機人，拿着強大的計算機工具，是如何進行思考，以及在某些方面降維打擊數學家，又在一些方面望塵莫及的。
再寫一遍問題：
如何計算一個大數平方根的近似值？
下面看下計算機人思考的角度。
開方算法的計算機思路
計算機人先要吐槽一把筆算開方的算法了，先不說背乘法口訣表對計算機來說太容易，以及這種經驗嘗試在計算機中不容易表達，這種豎式，估算，還有逐位計算的策略都入不得我們計算機人思考的法眼。我們會一開始就盡量把這個問題的數學部分解決掉，變成一個求值問題，具體來說，就是個求解二次方程根的問題。另一方面，計算機不需要考慮人方不方便計算的接口，對於大數的計算，速度飛快，輕而易舉，考慮速度和效率也是從時間空間複雜度這樣的角度來考慮的。而不是單次運算的時間，比如算12345 ^ 2和算10000 ^ 2在沒有特殊優化的情況下，一般的計算機接口耗時是一樣的（實際上可能因為位運算等方式的引入確實有所不同，這是編譯原理的細節了，暫不深入討論）。而人的話顯然不同，我們有一種神奇的找到式子滿足的公式性質並應用來化簡的能力，比如估算和試探需要的數感，似乎是人腦可訓練，又像是天生的。而計算機的符號計算，還真的很不智能，和人相差甚遠。而我們一般的數學考題，也就是要你看出這等性質，然後化簡，到了真的求值部分，難度會降低到乘法口訣表能解決的程度，這是數學的玩法，也是數學的局限，因為實際問題中可不像考試題目為了降低計算難度而設定一些好算的值。這時候計算機就要發揮作用了。計算機的接口，是看作常數時間的邏輯，四則運算這些東西，程序員不用去管內部的實現，天然就站在了巨人的肩膀上。
舉個例子，比如求斐波那契數列的第n項，n不大的情況下，直接O(n)時間複雜度算過去就好了。如果很大，計算機科學上上可以考慮加速的方法就不多了，而工程上則可以通過預計算，考慮記住n範圍內若干節點的值，遇到輸入先判斷大小，再從更接近的點遞推，或者在內存夠的情況下，存下問題的答案，或者在有限計算資源下尋求二者的折中。這是計算機人的思維方式，足夠熟悉存儲和計算資源的約束，在此基礎上去解決通用的一類問題，創造不可估量的價值。
正當計算機人忙得不可開交，然而數學人默默地寫下了特徵方程，求出了特徵根，寫出了第n項的通項公式……
（很久以前我還完全無法理解通過計算機處理問題的思路時，我面試時候交上去的思路就是這個，沒想到後來在《編程之美》這本書上看到，還真有我這個解法，但明顯是對計算機來說很不地道的方法。）
當然，一個優秀的計算機工程師應該是同時具備以上兩種素質的，在大多數情況下用計算機思維解決實際問題，而當遇到難題的時候，也期待能夠有數學的神來之筆，像RSA算法的計算，計算機起的作用就很小，相當於一個計算器，而主要是用的卻是數學性質了。
最後回到本題，按計算機人的思路，無奈用了一點點數學先轉化一下，這無非就是求函數f(x)= x ^ 2 = s這個一個函數方程的解，根據單調性和代數基本定理，只有正數一個根。於是我們可以直接採用二分法來不斷縮小解的範圍，進而求出近似解。或者，也可以用牛頓法加速收斂。但是，這些公式，在程序員看來，就是一個可以構造的迭代邏輯而已，這麼迭代且有人證明過，可以收斂到最優解，其複雜度如何等等這些信息而已。
比如牛頓法得到的迭代公式是：
xt+1 = xt + s / 2xt
或者更簡單點，二分法的迭代公式是：
[bt + 1, et + 1] = [(bt + et] / 2, et] if f((bt+ et] / 2) * f(et + 1) < 0 else [bt, (bt + et] / 2]
牛頓法求解平方根
來源：http://www.matrix67.com/blog/archives/361
往計算機里一敲，遞歸或者循環就完事了。至於x0的選取，估算得好，確實可以加速，但是，這對複雜度而言並沒有幫助，頂多是工程提升，而這麼簡單的問題又實在是不值得。所以，這些細節，數學家會覺得有研究價值，而要解決實際問題的程序員們，就趕緊算出答案來找下一個活幹了。
可見，在干這類計算的事情上，計算機人在工具的幫助下實現了對數學人的降維打擊，你計算速度不如計算機，象棋下不過計算機，圍棋，鬥地主，麻將，德州撲克都打不過計算機，那都是再正常不過的事情了，因為這都是計算機科學對人類的降維打擊，當然也不能否認中間數學的作用，但是你要看到，強大的算力，存儲的支持是贏得勝利的重要因素，只有數學而不會用計算機，就像一個光桿司令，還是大不了仗的。
所以我有時候和同事討論後達成一致意見，數學更多的就是一種藝術般的語言，並不直接創造生產價值，是藝術價值和對人思維訓練的價值。而計算機的目的自始至終都是為了解決實際問題，哪怕中間用到的數學也是這樣。能否用好計算機工具來解決問題是評估其好壞的標準，而數學則自己美美的就可以了，至於能否有用，萬一有用皆大歡喜，哪怕沒用，也決不影響它的清高自傲。
最後提一下，這個開平方的計算在遊戲開發中，經常涉及求取照明和投影的波動角度與反射效果的計算機圖形學操作，更常見需要使用的是平方倒數的計算，在這個特殊的場景下，曾有大牛專門定製了一個魔術般的算法：
#include <math.h> float InvSqrt(float x) { float xhalf = 0.5f*x; int i = *(int*)&x; // get bits for floating VALUE i = 0x5f375a86- (i>>1); // gives initial guess y0 x = *(float*)&i; // convert bits BACK to float x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy return x; } int main() { printf("%lf",1/InvSqrt(3)); return 0; ｝
其中出現的數0x5f375a86也是魔法一般的存在，其作用是在該特殊場景下僅用移位和常數的差以及類型轉換就近似了答案到很高的程度，使得再用牛頓迭代也不需要太多次就能達到需要的精度。具體解釋大家可以搜索《FAST INVERSE SQUARE ROOT》這篇文章得到，本篇暫時不贅述，如果有機會我從中又發現一些值得分析的點，會再寫出來和大家討論。
從數學到計算機，我在工作和研究中，一點一點領悟着這兩個學科定位不同帶來的差異，通過這些比較，也對他們的認識越來越深。最後總結一下：
- 數學關心證明和邏輯嚴謹，計算機關心效率和效果；
- 數學只要理論完備就很優秀，計算機只有解決問題才是關鍵；
- 數學以本身的美為目標，計算機以問題導向，用什麼方案都行；
希望你看完有所收穫。
