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

這個問題是我最近在公司內(nèi)部的代碼論壇上偶然看到的，下面列舉了很多的算法來解決以及各種復(fù)雜度分析和加速的方案。

不過我依稀記得，在我曾經(jīng)視為至寶的各種數(shù)學(xué)知識，技巧，公式中間，有一個叫“筆算開方”的玩意，應(yīng)該和這個問題有關(guān)。但由于日子實在太過久遠，根本無從回憶起是否真的昨日重現(xiàn)，還是僅僅有個類似的場景，像做夢一樣模糊不清。

Google了“筆算開方”四個字以后，第一條結(jié)果就看到了那映入眼簾的開方公式，頓時以點帶面，勾起了我對當(dāng)時學(xué)習(xí)這個內(nèi)容時場景的全部回憶：

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

“我只講一遍，沒學(xué)會的就算了?！?/span>

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

圖1 筆算開方示例

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

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

（我這里的數(shù)學(xué)，主要指初等，中等數(shù)學(xué)，以及簡單的高等數(shù)學(xué)等內(nèi)容，不包含離散數(shù)學(xué)，我一般把離散數(shù)學(xué)，直接歸為計算機科學(xué)的數(shù)學(xué)基礎(chǔ)那部分。）

我發(fā)現(xiàn)，以前我所習(xí)得的數(shù)學(xué)思維方式，和現(xiàn)在從事的計算機科學(xué)的思維方式，因為面對的場景和需求不同，有著截然不同的處理邏輯，特點，也有著各自獨立的美感。

數(shù)學(xué)關(guān)心證明，推導(dǎo)，理論的完備性；計算機不僅有這些，還關(guān)心效果，效率等實際應(yīng)用指標(biāo)。再總結(jié)一下就是：

數(shù)學(xué)美在結(jié)構(gòu)嚴謹，巧奪天工；計算機美在數(shù)學(xué)建模，經(jīng)世致用。

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

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

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

當(dāng)(d – 1)為偶數(shù)，則恰好變?yōu)?d – 1) / 2 + 1 = (d + 1) / 2位數(shù)；

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

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

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

豎式除法

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

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

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

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

(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)

根據(jù)前面的分析，這個結(jié)果的百位是3肯定沒錯，那么接下來，需要找的b0滿足的條件是最大的不超過原數(shù)105625的值，其中首2位10已經(jīng)用9減掉，剩余的其實是156，在括號內(nèi)外各提取一個10 ^ 1出來，得：

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

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

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

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

這便是數(shù)學(xué)人思考問題的方法的一個例子，接口是怎么讓人腦高效地解決問題，培養(yǎng)直覺，邏輯，智慧和美感，而計算機思維似乎又是另外一種套路，我們下回分解。

好了，今天數(shù)學(xué)魔術(shù)師的分享就到這里，希望各位客官喜歡，期待您的轉(zhuǎn)發(fā)和贊賞哦！