从欧几里得开始（三）

前篇小结

上篇文章用java完成了下面这幅算法流程图的实现，这个算法是判断一个整数\(a\)是不是一个自然数\(N\)是不是一个自然数的约数。

我们再次看一下这幅图：

好了，又回顾了一下。

注意到，这幅图里面起点和终点都被我矩形表示出来了，一个算法需要一个起点和至少一个终点，中间可能加一些判定过程，迭代过程。

思考方向

在分析一些算法问题的时候，最近我在一本叫《算法》的书上，看到了一个有意思的步骤，这个叫做科学方法，分成四步，大概是这样：

1，算法的实现和调试（implement，debugging）；

2，算法的基本性质（这句话不好理解，但实际过程中就是算法的稳定性，有什么特点，比如面对随机输入会怎么样子，这些性质也可以说影响着算法的性能表现。）

3，算法的性能表现（performance）；

4，算法的测试用例；（test-case）‘

我用java完成了一份实现，算是完成了第一步。我比较感兴趣的还是第三步，分析一个算法的性能。

就拿我这副算法流程图来说，我们需要分析它的性能表现，要从哪里开始入手。所谓的性能表现，就是对于输入，这个过程会多快产出结果。我们知道了，一个算法，就是一个输入口，中间循环时夹着许多判定过程，有时候，还会涉及数据操作。

所以这个分析简单的来说就是：数数（Counting），因为判定过程，数据操作都是有限的，只要把这个算法运行时，这些过程的具体数字数清楚，那么最后，做总和的时候，比如判定过程一共执行了a次，数据操作b次。

现在假如我们有一台机器，它进行一次判定过程需要消费时间\(t_1\)(单位判定时间)；它进行一次数据操作需要消费时间\(t_2\)（单位数据操作时间）。

那么这台机器用到的总时间就是：\(at_1+bt_2\) ，这是一个十分简单的和。而且现在性能强大的计算机，在进行判定过程，数据操作这两项动作用的时间都是十分微小的，你说等同起来也行。所以，进一步来说，去统计 \(a+b\)这个值更加便捷，也就是直接数数就行。

正如我们上篇文章里面说到的，在我用到的算法流程图里面，

判断过程有4个：

1,\(a=N?\)

2,\(a\le \lfloor \frac{N}{2} \rfloor\)?

3,\(ak=N?\)

4,\(k=\lfloor \frac{N}{a} \rfloor?\)

这四个过程对于每一次特定的输入，必然会产生一个确定的结果值。

比如对于\(a=1,n=28\), \(a=N\)?必定先判断一次;然后才考虑\(a\le \lfloor \frac{N}{2} \rfloor\)? 这个也判断一次；接下来才进入循环;

\(a=2,n=28\), \(a=N\)?判断一次;然后才考虑\(a\le \lfloor \frac{N}{2} \rfloor\)? 这个也判断一次;接下来才进入循环;

\(a=17,n=28 ,a=N\)?判断一次;后才考虑\(a\le \lfloor \frac{N}{2} \rfloor\)? 这个也判断一次, 这时候也完结了；

\(a=28,n=28\),\(a=N\)?判断一次;然后这个流程走完了，没有接下来的事情了；

所以实际上产生废时间的是在接下来的循环里面的判断，对于任意的\(a，N\)组合来说真正需要考虑时间耗费的是在

$1\le a \le \lfloor \frac{N}{2} \rfloor $时，只有这个范围才进入到循环里面，才会积累时间的消耗。

\(a\)是在这个区间之内的情况

这个的输入的组合有：

\((1,N),(2,N),(3,N)...( \lfloor\frac{N}{2} \rfloor,N)\)一共是$\lfloor \frac{N}{2} \rfloor $种组合。

这个就是说一共有这么多种输入的组合，然后我们知道，这里每一种组合，来跑一遍这个算法，需要进行的判定流程

\(ak=N?\)的数目是不一样的，但是可以被数出来。\(k=\lfloor \frac{N}{a} \rfloor?\)的数目和\(ak=N?\)的数目只会差1个，这两个判断是连在一起的，只要一个完结，另外一个也会完结，但是总数会相差1，我觉得不需要进行如此细致地分辨。

在统计上，我们只统计其中一个就行了。

下面举个例子：

对于（1，N) 这个组合，我们需要进行N次判断；（这是一个这个算法缺陷，因为我们知道1是任何自然数的约数，这里实际执行却还需要进行N次判断，所以这又找到了一个改进的地方）

对于（2，N）这个组合，我们需要进行$ \lfloor\frac{N}{2} \rfloor$次判断；

对于（3，N) 这个组合，需要进行$ \lfloor\frac{N}{3} \rfloor$次判断；

....

那么对于\((a,N)\)这个组合，需要进行\(\lfloor\frac{N}{a} \rfloor\)次判断；

对于$ \lfloor\frac{N}{a} \rfloor$这个魔法一般的数字怎么来的，你会感到困扰吗？但是实际上它出现在算法中迭代的结束判定里面，这个就是边界，超出边界，算法就终止，得出结果，如果没有结束，算法自然在运行，累计来超过这个边界。

实际中，也可以考虑具体的数字，比如（5,28）作为输入，那么一步一步地走，你发现还是$ \lfloor\frac{28}{5} \rfloor=5$次内结束，得到false值。

现在实际上这个算法已经分析完了，结论就是这条：对于\((a,N)\)这个组合，需要进行$ \lfloor\frac{N}{a} \rfloor$次判断，然后计算机消费进行这么多判断的时间。

但是这个算法有多快呢？这个是一个统计问题了，比如我任意给一个自然数N，然后我要找出所有的约数。

那么自然我们只要把这种组合加起来得到一个总的次数S：

\[S=\lfloor\frac{N}{1} \rfloor+ \lfloor\frac{N}{2} \rfloor + \lfloor\frac{N}{3} \rfloor.. + \lfloor\frac{N}{a} \rfloor+... \lfloor\frac{N}{\lfloor \frac{N}{2} \rfloor} \rfloor \]

这是用这个算法去找自然数N的所有约数需要进行的总的判断次数，这个和式可以通过一些推理进行化简：

\[\begin{align*} S=&\lfloor\frac{N}{1} \rfloor+ \lfloor\frac{N}{2} \rfloor + \lfloor\frac{N}{3} \rfloor.. + \lfloor\frac{N}{a} \rfloor+... \lfloor \frac{N}{\lfloor \frac{N}{2} \rfloor} \rfloor\\ = & \sum_{1\le a \le \lfloor \frac{N}{2} \rfloor}{\lfloor \frac{N}{a} \rfloor} \\ = & \sum_{a}{[1\le a \le \lfloor \frac{N}{2} \rfloor]\lfloor \frac{N}{a} \rfloor} \end{align*} \]

从第二步到第三步，需要一个用到一个断言函数：记号就是一对方括号[],

就是说\([1\le a \le \lfloor \frac{N}{2} \rfloor]\) 表示\(1\le a \le \lfloor \frac{N}{2} \rfloor\) 这个条件成立的时候，这个函数取值是1，不成立取值是0，这就是像是一个人在决断一样，被决断的就是 方括号里面的内容。

这个函数的好处是，解放\(a\)，让\(a\)从限定在 \(1\le a \le \lfloor \frac{N}{2} \rfloor\)里面解放出来，因为不在这个范围内的被这个函数用0值干掉了，只有在这个方位内的和式统计。

现在需要处理的部分是\(\lfloor \frac{N}{a} \rfloor\);

\[\lfloor \frac{N}{a} \rfloor=\sum_{j}[1 \le aj \le N] \]

这个可能一眼看不到这个，但是仔细想一下，不超过N除以a的最大整数，这个整数怎么形成的，就是用一个一个的a从N里面减掉，最多能够减多少次。那么反过来，我用一次一次的a加起来，每一次加起来后，只要不超过N，这个情况统计1次，那么最大整数就是在不超过N下这些情况的积累，也就是上面那么式子。

\[\begin{align*} S=&\lfloor\frac{N}{1} \rfloor+ \lfloor\frac{N}{2} \rfloor + \lfloor\frac{N}{3} \rfloor.. + \lfloor\frac{N}{a} \rfloor+... \lfloor \frac{N}{\lfloor \frac{N}{2} \rfloor} \rfloor\\ = & \sum_{1\le a \le \lfloor \frac{N}{2} \rfloor}{\lfloor \frac{N}{a} \rfloor} \\ = & \sum_{a}{[1\le a \le \lfloor \frac{N}{2} \rfloor]\lfloor \frac{N}{a} \rfloor}\\ = & \sum_{a}{[1\le a \le \lfloor \frac{N}{2} \rfloor] }\sum_{j}[1 \le aj \le N] \\ = & \sum_{a,j}{[1\le a \le \lfloor \frac{N}{2} \rfloor] }[1 \le aj \le N] \end{align*} \]

最后这一步就是分配律：

$ a(b+c)= ab+ac$

所以最后

$ S = \sum_{a,j}{[1\le a \le \lfloor \frac{N}{2} \rfloor] }[1 \le aj \le N]$

这个形式就是我想要的结果，首先变量\(a，j\)两个都被解放了，从限定范围解放了，当然\(a，j\)都还是整数啊，因为所有的情况都是一个一个去统计，而不是用连续变量在描述问题，一定要给个名称，\(a，j\)都是离散变量，而且是离散整数变量。

那么对于所有a，j的组合，就是一个二维坐标轴中的整点，就是说这个坐标系被栅格化，只有整数点。

这样看的话，\(S=\sum_{a,j}{[1\le a \le \lfloor \frac{N}{2} \rfloor] }[1 \le aj \le N]\)这个式子意味着什么呢？

如果一不习惯a，j做变量，那么你把a换成x，j换成y；

\(S=\sum_{x,y}{[1\le x \le \lfloor \frac{N}{2} \rfloor] }[1 \le xy\le N]\)

我们有两个断言，整数x在1到$ \lfloor \frac{N}{2} \rfloor $之间，整数y满足xy在1，N之间；

画出一个整点坐标系，用x作为横轴，y作为纵轴；

红色这些是这个整点坐标里面实际的点，然后两个断言告诉我们，我们只要去数加载两根蓝色曲线，以及两根蓝色竖线之间的所有红色点的数目，这就是我们的和S。

恩，这是一个精确的做法，但是我们希望忽视一些，那么我们可以这么做，把没有红色的点用一个单位面积为1的小的正方形代替那么所有在图中蓝色框内的红色点的数目，近似用一个锯齿状的图形的面积替代，锯齿状图形的面积可以用微积分估算的，把这条曲线这个上移1个单位，得到 \(xy=N+1\)这条曲线，这是为了考虑整数点刚好落曲线上，这些点的变成面积为1的正方形后不会被\(xy=N\)截取太多。那么尽管这么做之后，还是有误差。

如果接受这样的近似，那么用\(xy=N+1\) 和\(xy=1\)这两条曲线，$$x=1，x=\lfloor \frac{N}{2} \rfloor+1$$这两条直线围成的曲面图形的面积与我们的和S是十分接近的。

我们来计算一下这个积分：

\[\begin{align*} &\int_{1}^{\lfloor \frac{N}{2} \rfloor+1} (\frac {N+1}{x}-\frac {1}{x})dx\\ =&N\int_{1}^{\lfloor \frac{N}{2} \rfloor+1} \frac {1}{x}dx \\ =&N \ln(\lfloor \frac{N}{2} \rfloor+1) \end{align*} \]

这个结果就是我们稍微有些误差的S，而且不是一个整数，这说明这就是一个精确的近似值。但是我们可以用来估算，这个值的意义就是，用这个算法去找N的所有约数，总共需要实行这么多次判断过程，当然，可能有更好的计算方法和近似方法。

到这里，我对于一个自然数约数的说明就到一个段落了，然后可以开始就说一下欧几里得对于公约数是怎么计算的了。