By Long Luo

PID 算法^[1] 是自动控制领域中很重要的算法。

Simple PID Controller

非常简单的 PID 算法在线互动式模拟器，传送门 → ：

之前这个是 PID v1.0 版本，最近重构了代码，增加了一些新功能：

1. 增加机器人速度 $v$ 及加速度 $a$ 显示；
2. 增加 2 个图表展示 PID X 轴方向及 Y 轴方向的 P、I、D $3$ 个分量随时间变化显示；
3. 之前代码将时间及速度固定了，但这不符合实际，增加随 $dt$ 变化积分和微分项；

By Long Luo

Kalman Filter^[1] 是贝叶斯滤波器的一种特殊实现。

Kalman Filter 1D | 一维卡尔曼滤波器

一维卡尔曼滤波器如下图所示：

在线动画展示：http://www.longluo.me/projects/kalman/

By Long Luo

在数学、物理学、工程和计算机领域中，泰勒公式^[1] 是一种广泛使用的分析方法，用来计算函数的近似值。在实践中，很多函数非常复杂，而且某些函数是不可积的，想求其某点的值，直接求无法实现。

泰勒公式可以将复杂的函数近似地表达为简单的多项式函数，用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)。注意在逼近的时候一定是从函数图像上的某个点展开。

下图所示就是不同项数的泰勒公式对 $\sin x$ 的逼近：

泰勒级数的定义为：

$$f(x) = \sum _{n=0}^{\infty}{\frac{f^{(n)}(a)}{n!}}(x-a)^{n} = f(a) + {\frac {f'(a)}{1!}}(x - a) + {\frac {f''(a)}{2!}}(x - a)^{2} + {\frac {f'''(a)}{3!}}(x - a)^{3} + \cdots$$

这里，$n!$ 表示 $n$ 的阶乘，而 $f^{(n)}(a)$ 表示函数 $f$ 在点 $a$ 处的 $n$ 阶导数。如果 $a = 0$ ，这个级数也被称为麦克劳林级数(Maclaurin series)^[2] 。

泰勒展开式有很多，那么如何记忆呢？首先我们需要明白，泰勒公式之间都是有相互关联的，我们可以通过推导来理解性记忆这些公式。泰勒公式的具体推导过程可以参考数学分析教材或者网络^[3] 。

下面我们就推导这些公式，以便更好的记忆^[4] ！

几何级数 Geometric series

对于 $-1 < x < 1$ 的情况，几何级数^[5] 由等比数列求和公式可得：

$$\frac{1}{1 - x} = \sum _{n=0}^{\infty}x^{n} = 1 + x + x^{2} + \cdots + x^{n}$$

用 $-x$ 代入 $x$ 上式，则：

$$\frac{1}{1 + x} = \sum _{n=0}^{\infty}(-1)^nx^{n} = 1 - x + x^{2} - x^3 + \cdots + (-1)^n x^{n}$$

用 $x^2$ 替代 $x$ , 由于 $\arctan x = \int_{0}^{x} \frac{1}{1 + x^2} \mathrm{d}x$ ，对于 $-1 \le x \le 1, x \neq \pm i$ ，

$$\arctan x = \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n + 1}}x^{2n + 1} = x - {\frac {x^3}{3}} + {\frac {x^5}{5}} - \cdots + \frac{(-1)^n}{2n + 1}x^{2n + 1}$$

因为 $\frac{1}{(1 - x)^2} = (\frac{1}{1 - x})'$ ，则：

$$\begin{aligned} \frac {1}{(1-x)^2} &= \sum _{n=1}^{\infty }n x^{n-1} \\ &= 1 + 2x + 3x^2 + \cdots + n x^{n-1} \end{aligned}$$

同 $\frac{1}{(1 - x)^3} = \frac{1}{2} (\frac{1}{(1 - x)^2})'$ ，则有：

$$\frac {1}{(1 - x)^3} = \sum _{n=2}^{\infty }{\frac {n(n - 1)}{2}}x^{n - 2}$$

指数函数 Exponent function

由于 $\frac{\mathrm{d} e^x}{\mathrm{d} x} = e^x$ ，$e^0 = 1$ 那么：

$$e^x = \sum _{n=0}^{\infty }{\frac{x^n}{n!}} = 1 + x + {\frac{x^2}{2!}} + {\frac {x^3}{3!}} + \cdots + {\frac{x^n}{n!}}$$

很明显：

$$\begin{aligned} (e^x)' &= (\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)' \\ e^x &= 0+1+\frac{x}{1}+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots \\ &= 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \end{aligned}$$

对于普通指数函数 $a^x$ , 由于 $a^x=e^{x\ln a}$ ，如果将 $x$ 换为 $x\ln a$ ，那么 $a^x$ 的泰勒展开式：

$$\begin{aligned} a^x &= e^{x \ln a} \\ &= 1 + x \ln a + \frac{(x \ln a)^2}{2!} + \frac{(x \ln a)^3}{3!} + \cdots + \frac{(x \ln a)^n}{n!} \\ \end{aligned}$$

By Long Luo

昨天在B站看到一个数学视频^[1]，比较 $2^{100!}$ 和 $2^{100}!$ 的大小。直观感受就是这2个数都非常非常大，但哪个更大无法一眼看出来。

虽然指数爆炸，但阶乘实际上增长的速度比指数更快，如下图1所示：

可以看出阶乘图像 $y = x!$ 实际上比指数 $y = e^x$ 要快很多，而 $y = x^x$ 是最快的。

但具体哪个更大呢？

这个问题有很多种方法，这里展示了4种方法。

对数放缩法 (Zoom)

由于对数^[2] 函数 $y = \log_{a}{b}$ 当 $a > 1$ 是单调递增函数，所以比较两个数大小时，可以通过比较两者对数值来实现大小比较。

两边同取对数 $\log_{2}{x}$ ，

左边：

$$A = \log_{2}{(2^{100!})} = 100!$$

右边：

$$B = \log_{2}{2^{100}!}= \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0$$

共有 $2^{100}$ 项，值从 $0$ 到 $\log_{2}{2^{100}} = 100$ ，所以

$$B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107}$$

综合上式，我们只需要比较 $100!$ 和 $2^{107}$ 的大小即可。

$100!$ 至少有 $(100 - 64 + 1) = 37$ 项是大于等于 $64 = 2^6$ ，也就是 $(2^6)^{37}=2^{222}$ 。

显然可得 $100! \gg 2^{222} \gg 2^{107}$ 。

故有虽然两个数都非常大，但 $2^{100!}$ 仍然远远大于 $2^{100}!$ 。

斯特林公式 (Stirling’s Approximation)

由于存在阶乘，我们可以使用斯特林公式(Stirling’s Approximation)^[3] 来估计。

$$n! \sim \sqrt{2 \pi n}(\frac{n}{e})^n = \sqrt{2 \pi} n^{\frac{n + 1}{2}}e^{-n}$$

两边同取对数：

$$\ln{n!} \sim \frac{1}{2} ln(2 \pi) + (n+\frac{1}{2}) ln(n) - n$$

根据上式，可见 $n$ 足够大时，斯特林公式可以近似为：

$$\ln(n!) \sim n(ln(n) - 1)$$

则有：

$$\begin{array}{l} A = ln(2^{100!}) = 100! ln(2) \\ B = ln(2^{100}!) \sim 2^{100}(ln(2^{100}) - 1) = 2^{100}(100 ln(2) - 1) \end{array}$$

由于 $2^{10} = 1024 \approx 10^3$ ，则有 $2^{100} \approx 10^{30}$ , 那么 $B \approx 10^{32} ln(2)$ 。

很明显 $100! \gg 10^{32}$ ，因此

$$2^{100!} \gg 2^{100}!$$

By Long Luo

袁哥在微博上发布了一道 数学挑战题 ：

计算 $(3+ \sqrt{5})^n$ 的整数末三位数，给出能口算或者可以用计算器计算的算法的第一个人，免费给一个价值 1000 元的 A9 投资分享群入群名额。

最开始看到这道题目时，我觉得很简单啊，于是给出了下面的解答：

令 $y = (3+ \sqrt{5})^n$ ，两边同取对数，$\log_{10}{y} = n \log_{10}{(3+\sqrt5)}$ ， $y = 10^{n\log_{10}{5.23607}}$ ，$lg5 \approx 0.7$ ，所以 $y \approx 10^{0.7n}$ 。

但问题没有这么简单，因为上述解答只在 $n = 1$ 是正确的，$n = 2$ , $y = 10^{1.4} = 25$ 就不对了，因为精度不够！

之外，根据评论中其他人给的思路，分析得出这个是周期性的，所以又提交了下面的答案：

但问题仍然没有这么简单，因为即使循环周期 $k = 100$ , $\log_{10}{(3+\sqrt5)}$ 取的位数再多仍然会出现精度不够的问题。

之后袁哥发布了 解答 ，图片太大，这里放 链接 。

袁哥的题解省略了很多东西，很多人可能看不太明白。我重新写了题解，重新整理了思路及缺失的步骤，外加证明，有高一数学水平即可看懂。

后来通过搜索，发现这道题是 Google CodeJam^[1] 编程竞赛题，原题如下：