從開方演算法看數學和電腦思維的差異（一）——數學人怎麼想問題

• 2019 年 10 月 8 日
• 筆記

如何計算一個大數平方根的近似值？

面對這樣一道題，以你的知識背景，會怎麼想？從哪裡入手？有什麼思路？

這個問題是我最近在公司內部的程式碼論壇上偶然看到的，下面列舉了很多的演算法來解決以及各種複雜度分析和加速的方案。

不過我依稀記得，在我曾經視為至寶的各種數學知識，技巧，公式中間，有一個叫「筆算開方」的玩意，應該和這個問題有關。但由於日子實在太過久遠，根本無從回憶起是否真的昨日重現，還是僅僅有個類似的場景，像做夢一樣模糊不清。

Google了「筆算開方」四個字以後，第一條結果就看到了那映入眼帘的開方公式，頓時以點帶面，勾起了我對當時學習這個內容時場景的全部回憶：

記不清是小學還是初中了，那時候每周五上英語補習，周日上奧數，給我的感覺就是周五下一次地獄，周日上一次天堂。只有過了周五英語老師各種要求背課文，點名回答問題這些關以後，才能好好享受一回數學課的爽快。這個筆算開方的方法，當時應該還沒怎麼學過代數，所以自己是理解不了為什麼成立的，教的時候也是當作超綱內容，記得教課的蔡老師還很不捨得地說：

「我只講一遍，沒學會的就算了。」

哈哈，這麼牛逼又神奇的東西我怎麼可能會忘？豎起耳朵打起12分精神，記下了所有步驟，然後回家沒事就隨便寫個很大的數開方玩，玩的不亦樂乎！

圖1 筆算開方示例

來源：https://blog.csdn.net/czg13548930186/article/details/70182997

好了，兒時的追憶到此為止，現在我們來想想，現在我們該怎麼思考這樣一個問題？思考中又有什麼可以借鑒之處？

（我這裡的數學，主要指初等，中等數學，以及簡單的高等數學等內容，不包含離散數學，我一般把離散數學，直接歸為電腦科學的數學基礎那部分。）

我發現，以前我所習得的數學思維方式，和現在從事的電腦科學的思維方式，因為面對的場景和需求不同，有著截然不同的處理邏輯，特點，也有著各自獨立的美感。

數學關心證明，推導，理論的完備性；電腦不僅有這些，還關心效果，效率等實際應用指標。再總結一下就是：

數學美在結構嚴謹，巧奪天工；電腦美在數學建模，經世致用。

我們從這道題，分別來簡單說明。

開方演算法的數學思路

要給一個可能不是完全平方數的數開平方，這件事在數學家眼裡看來其實是意義本身不大的，因為這純粹是一個計算問題，費時費力，計算問題直接給那些程式設計師同學去算就好了，不關我們的事。但是，如果涉及到比如，證明是否存在這樣的方法，或者能否給出一個簡便方案來寫出結果這種證明或是一些特殊性質的挖掘，他們是樂意的。因此，這個問題對他們的價值就是，能否想一些用少量計算就能解決的思路，最好還能用上一些公式定理，筆算就能解決，這樣才好體現學數學人的價值。

第一步想的是估算，至少要知道結果是幾位數。我們知道a ^ 2n開方即為a ^ n，把a看成進位的話，那麼可以看出，一個d位數（無論什麼進位，設為a），最高位對應值為b * a ^ (d – 1), b < a。那麼，

當(d – 1)為偶數，則恰好變為(d – 1) / 2 + 1 = (d + 1) / 2位數；

如果為奇數，為(d –1 – 1) / 2 + 1 = d / 2，因此數位變化結果為[(d + 1] / 2]。

直觀來看，就是，從末尾開始看，每兩位一個計算單元，若僅有奇數位，則前面補0。

這個結果非常好，開方涉及的數位變化是很有規律的，大家應該還記得豎式除法和因式分解的話，就能想到應該能參照類似的方法進行了。比如，豎式除法的模式可以見下圖：

豎式除法

豎式除法的基本思想是，從高位開始，依次確定每一位的值，並不斷把問題歸約（reduction）到等價的更小的規模，而對同類問題僅規模減小的歸約就是遞歸（recursion）了。這樣一直進行下去，直到一定的精確度或者完全整除。當然，當年小學時候我應該是用循環（circulation）來理解的，不過因為這裡迭代次數固定，這種線性而非自相似的邏輯結構也足夠用了。

乘方是乘法的簡便運算，開方也是除法的高層級運算。筆算開方是不是也可以用豎式除法類似的思路來解呢？

有些類似也有區別，相同在於，都是進位位不斷減小的循環/遞歸，而不同在於其計算單元從1位變成2位，以及每次遞歸時候需要剔除的值的大小似乎也更難算些。

比如圖1的105625的開方，第一位是10，直接3 ^ 2 = 9，是能夠開下來的最大數，即答案必然是個百位數而且百位數字為3。但是，接下來不是像除法那樣餘1了，我們在百位上寫了個3，實際的意思是，把我們要算的平方數，拆成了已經確定的一個300和剩餘部分，要完成這個遞歸，得要知道接下來的要計算的內容才是，除法的話當然就直接減去完事了，但這裡，我們用完全平方公式一展開，也就一目了然了：

(a + b) ^ 2 = a ^ 2 + 2ab + b ^ 2 = a ^ 2 +b(2a + b)

帶入本題，即：

(a0 * 10 ^ 2 + b) ^ 2 =(a0 * 10 ^ 2) ^ 2 +2a0 * 10 ^ 2 * b + b ^ 2 = a ^ 2 + b(2a + b)

a0 = 3，得：

(300 + b) ^ 2 = 300 ^ 2 + b (2 * 300 + b)

即：

(300 + b0 * 10 ^ 1) ^ 2 = 300 ^ 2 + b0 ^ 10^ 1 (2 * 300 + b0 * 10 ^ 1)

根據前面的分析，這個結果的百位是3肯定沒錯，那麼接下來，需要找的b0滿足的條件是最大的不超過原數105625的值，其中首2位10已經用9減掉，剩餘的其實是156，在括弧內外各提取一個10 ^ 1出來，得：

(300 + b0 * 10 ^ 1) ^ 2 = 300 ^ 2 + b0 (2 *30 + b0) * 10 ^ 2

所以相當於找最大的b0，使得b0 (2 * 30 + b0)最接近156，到這裡其實就又可以口算了，取b0 = 2，然後再繼續往下遞歸，如果整除，結束運算，不整除的話可精確到小數點後指定位數。

按電腦的說法，這本質就是遞歸了。但是我學這玩意的時候壓根不知道有這種思想，更覺得這是一個完全平方公式的神奇應用，驚嘆於數學計算化簡的美妙，把開方這樣一個計算困難的問題硬是化簡成了一個背下來乘法口訣表就能夠處理的問題，實在妙哉！

而我們在學習這些初等的數學性質的時候，其實也著重用的就是這些對人本身去執行這些計算非常有利方案，比如豎式的乘除法，10進位化二進位，分解質因數和求取最大公約數，最小公倍數的豎式方法，還有同頭尾合十，99和11乘法的性質等，把一個用特定進位數表達的數的運算用基本的個位數口訣和經驗嘗試這兩種基本能力就能夠解決，尤其是後者，可以不斷提升速度。

這便是數學人思考問題的方法的一個例子，介面是怎麼讓人腦高效地解決問題，培養直覺，邏輯，智慧和美感，而電腦思維似乎又是另外一種套路，我們下回分解。