4.5　求余及求商算法

由于0这一概念在数学中得到广泛运用的过程特别漫长，因此直到多个世纪之后才有人意识到：原来线段的长度也可以是0。这指的就是那种同时以某个点A为起点和终点的线段AA。

引入了长度为0的线段后，阿基米德公理就不再成立了，因为即便把无数个长度为0的线段加起来，其总长度也依然超不过一条长度非0的线段，因此，现在必须重新思考GCM及求余函数。我们可以允许第一个参数a为0，但是要确保第二个参数b不会是0。此外，还要把余数的范围从原来的[1，n]变为现在的[0，n-1]。这样修改对于后面将要提到的模运算以及其他一些推导过程来说相当重要。下面给出修改之后的代码：

我们只是修改了代码中的判断条件。原来需要判断a<=b的地方，现在都改为判断a＜b。

接下来，需要想办法把递归去掉。由于每次向下一层递归的时候，b的值都会翻倍，因此，若想把递归改为迭代，则需提前计算出b经过多次翻倍之后所具备的最终值。于是，我们通过下面这个函数来反复地给b加倍，直到其超过a-b为止：

然后，我们按照迭代的方式来实现与递归版本相同的运算。执行递归版本的函数时，每当最近的那一次递归调用结束后，变量b都会恢复到进行该次调用之前的那个取值（也就是说，它会从翻倍之后的值恢复到翻倍之前的值），因此，在将其改为迭代函数时就需要在相关的变量上面反复地撤销这种翻倍效果，这可以通过调用half函数来实现。请注意，迭代版本的函数所使用的操作依然要局限在尺规作图的能力范围之内，然而由于欧氏几何中，已经有了通过尺规来对线段进行“减半”的方法 ，因此，我们是可以使用half函数的。下面给出迭代版本的求余函数：

此函数的第一部分用来寻找原除数经过进行多次翻倍之后的最终值，这一部分相当于递归版本在向下递归的过程中所执行的操作。而该函数的第二部分则是把递归版本的函数在向上返回时所执行的那些操作模拟了一遍。我们仍然以45除以6为例来演示新版求余函数的运算过程：

大家可以看到，迭代版本里面的变量c，在每一轮迭代中所取的值，都与递归版本里面的变量b，在每一轮递归中所取的值相同。此外，把上述过程与4.2节末尾所演示的那个递归算法相对比，我们就会发现，该过程的第一部分所得到的结果（也就是c=24且a=21），正好就是原来最内层的递归所算出的数值。

这种算法的效率是很高的，它几乎与当前通过处理器所实现的硬件求余算法差不多。

***

如果要计算的不是余数，而是商，那应该怎么办呢？其实只需要对源代码稍加修改就可以了（下面用粗体标出修改后的部分）：

两条线段之商，就是前者能够包容后者的次数，因此，我们可以用integer类型来表示这个值。求商算法，是要计算线段a中可以容纳多少份线段b。如果a＜b，那说明线段a连一份b也容纳不下，因此直接返回0；若a≥b，则将计数器初始化为1，然后逐次对c减半，并给计数器加倍，如果某一轮的a可以容纳下当时的c，那就再给计数器在当前这一轮的值加1。下面我们还是用45与6来演示，只不过这次求的是商，而不是余数。

这个过程实际上是埃及乘法算法的逆过程。就莱因德纸草书来看，其抄写员阿姆士（Ahmes）当时已经知道了该算法的一种原始版本，古希腊人将它称为埃及除法（Egyptian division）。 cRaZnZacXHgcJiBnUkUQKephmJa+lsy5HEAxtFiSJTw2tFrWoK9/6kDilJgDPuCR