Street-Fighting Mathematics(街头数学)
这本书 是从MIT OCW上找到的，实际上一门 课程，主要讲如何对数学公式做猜测和估算等。这些猜测和估算可能没有办法 进入教科书，却都是非常实用的东西。书里面有不少问题我没有看懂，有一些问题是很早就知道的，这里只挑三个问题记录写。
对积分进行估计。思路都是将曲线覆盖面积转换成为矩形，矩形的高采用MaxValue, 而宽则有两种办法：
- the 1/e heuristic (Section 3.2.1) and
- the full width at half maximum (FWHM) heuristic (Section 3.2.2)
第一种办法是计算1/e * MaxValue对应的x值，第二种办法是计算1/2 * MaxValue对应的x值
以e^(-t) * dt(t=0->inf)积分为例，曲线如下图：
MaxValue=1(t=0), 然后宽度的话我们可以计算e^-t = 1/e，那么t=1. 所以我们估计这个积分是1 * 1 = 1. 实际上这个误差为0。
以e^(-x^2) * dx(x=-inf->inf)积分为例，曲线如下图：
MaxValue=1(t=0), 宽度的话我们计算e^(-x^2) = 1/e, 那么x=-1,+1, 所以我们估计这个积分是1 * 2 = 2. 而实际上这个值是sqrt(pi) ~=1.77, 误差在13%，还是蛮大的。
如果使用FWHM这个办法来估算的话，曲线如下图：
MaxValue=1(t=0), 宽度的话我们计算e^(-x^2) = 1/2, 那么x = sqrt(ln2), 所以我们估计这个积分是 2 * sqrt(ln2) ~= 1.665, 误差在6%，这个就非常好了。
斯特林积分近似 斯特灵公式 - 维基百科，自由的百科全书
假设我们知道n!的积分形式是 t^n * e^(-t) * dt (t=0->inf)的话，如何估计这个积分的值。我们这里还是使用上面的两种估计积分的办法。
首先我们要确定这个积分曲线的最高点在哪里，这个可以通过一阶导数得到t=n.
然后确定这个矩阵的宽度是多少，这个不太好计算。比如我们使用FWHM的话，我们要计算 t^n * e^(-t) = (n/e)^n * 1/2, 比较困难.
既然这个形式不太好求解，我们可以近一步估算。将积分函数使用泰勒级数展开，因为在n上一阶导数是0，那么我们只看二阶导数，估算出这个矩形的宽度。我这里直接粘贴书里面的结果。这个结果和斯特林公式偏差很小 n!~=(n/e)^n * sqrt(2*pi*n), 误差分别是13%和6%.
最后这个问题还是和斯特灵公式相关的，我们从头推导斯特林公式
- n! = 1 * 2 * … n
- log(n!) = log1 + log2 + .. logn = ∑{k=1..n}(logk)
- 如果我们改成积分形式来计算的话，那么log(n!) = lnk * dk(k=1..n) = nlogn - n + 1
- 所以 n! = (n/e) ^ n * e
- 而正确的计算形式是 n!~=(n/e)^n * sqrt(2*pi*n), 其中最关键的sqrt(n)丢失了，这是为什么呢？
为了方便分析，我们把前面3步做成图
可以看到实际上我们转变成为积分的过程中，上面那些近似的三角形丢失了，并且这些三角形组成的面积似乎不是常数。如果仔细观察，这些三角形面积虽然单个比较难计算，但是之和却容易计算，是logn / 2.
所以实际积分上还需要增加logn/2这么一项。增加上了之后结果就是 n! = (n/e)^n * e * sqrt(n), 和正确形式差别在 e和sqrt(2*pi)，这个误差大约8%.