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

上回说到，以分析，代数，几何，算术等为代表的的经典数学的思维方式和计算机科学背后的现代离散数学思维方式有着本质的区别。无论是从它们诞生的背景，为人所用的场景以及我们对它的理解方式，虽然都是数学，却有着截然不同的文化。上一讲我们以笔算开方的算法研究为例，谈了谈数学人的思维习惯和逻辑：

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

如果你还不太了解笔算开方算法或者想更好地全面吸收本系列文章的思想，建议先浏览一下上篇。

今天，我们来看看，面对同样一个问题，计算机人，拿着强大的计算机工具，是如何进行思考，以及在某些方面降维打击数学家，又在一些方面望尘莫及的。

再写一遍问题：

如何计算一个大数平方根的近似值？

下面看下计算机人思考的角度。

开方算法的计算机思路

计算机人先要吐槽一把笔算开方的算法了，先不说背乘法口诀表对计算机来说太容易，以及这种经验尝试在计算机中不容易表达，这种竖式，估算，还有逐位计算的策略都入不得我们计算机人思考的法眼。我们会一开始就尽量把这个问题的数学部分解决掉，变成一个求值问题，具体来说，就是个求解二次方程根的问题。另一方面，计算机不需要考虑人方不方便计算的接口，对于大数的计算，速度飞快，轻而易举，考虑速度和效率也是从时间空间复杂度这样的角度来考虑的。而不是单次运算的时间，比如算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》这篇文章得到，本篇暂时不赘述，如果有机会我从中又发现一些值得分析的点，会再写出来和大家讨论。

从数学到计算机，我在工作和研究中，一点一点领悟着这两个学科定位不同带来的差异，通过这些比较，也对他们的认识越来越深。最后总结一下：

1. 数学关心证明和逻辑严谨，计算机关心效率和效果；
2. 数学只要理论完备就很优秀，计算机只有解决问题才是关键；
3. 数学以本身的美为目标，计算机以问题导向，用什么方案都行；

希望你看完有所收获。