从开方算法看数学和计算机思维的差异（一）——数学人怎么想问题

• 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乘法的性质等，把一个用特定进制数表达的数的运算用基本的个位数口诀和经验尝试这两种基本能力就能够解决，尤其是后者，可以不断提升速度。

这便是数学人思考问题的方法的一个例子，接口是怎么让人脑高效地解决问题，培养直觉，逻辑，智慧和美感，而计算机思维似乎又是另外一种套路，我们下回分解。