前言

由于计算机编程语言数据类型存储的限制，无法使用内置的数据类型来进行任意位数字的计算，其中任意位整数四则运算中的除法最难处理。

因此，大整数除法成了很多高校数据结构课程中的课程设计作业。今天为大家带来一个 Java 实现的基于二分法和乘法运算反向求解大整数除法的奇葩算法。

二分法

二分法是一些数学运算和众多数据结构算法的基础，在介绍算法基本思路之前先简单回顾下二分法的概念。在数学中，二分法是指函数区间两端点通过逐步逼近函数零点求得近似值。在数据结构算法中一般还被称为二分查找，其是指在有序列表中通过折半的方式来搜索指定元素。

二分法示意图

算法思路

1. 数据存储与基本流程

计算机程序需要考虑的两大方面就是算法和数据存储，其中数据存储形式会影响到算法的设计，因此根据需求合理设计数据存储结构非常重要。在本次程序设计中，我们选择双向链表来存储大整数数据。

上图示例中展示了双向链表存储数据的优势，这种数据结构既可以满足大整数输出显示的需求，又可以方便进行计算。在Java实现中我们使用LinkedList来存储大整数数据。

有了大整数存储数据结构之后，需要设计算法流程，基本流程如下所示：

2. 初始化商

有了数据结构和基本流程就可以开始实现大整数除法算法了。在进行运算之前，为了节省时间成本，我们可以合理的初始化商。以十进制大整数除法运算为例，假设计算 A / B 的结果R，则R的最大位数如下所示：

在确定R的最大位数之后，设置大整数R各存储节点为节点最大值。以四位数节点为例，其初始化值为9999。这里为了演示方便，我们设置节点为一位数节点，即最大值为9。则初始化商结果如下：

3. 迭代求值

迭代求值的过程是从初始化商的高位节点开始用二分法的方式设置临时商，然后通过将临时商与除数相乘得出的结果同被除数进行比较从而判断是否终止迭代或在下一次迭代中采取二分法增还是二分法减来调整商。

处理顺序是从临时商的高位到临时商的低位，从而保证迭代求值的速度。因为高位数值的变动相比于低位数值的变动会有更大波动，从而能够快速收敛。

在迭代求值过程中有一点非常重要，那就是判断何时应该停止迭代。停止迭代求值的条件之一就是二分法进逼求值过程中右值和左值的绝对差已经小于等于1，即二分法当前值的波动已经停止。另一个重要条件分为两种可能，一是上一次迭代的临时商大于结果，另一种情况是二分法当前值在两次迭代中不发生改变。

当以上两条件同时满足并且无低位节点需要处理时则迭代终止。当最后一次试商比较结果为当前商大于真实结果时，则最终结果需要减一。

节点粒度为1，即节点最大值为9的程序执行结果如下图所示：

节点粒度为4，即节点最大值为9999的计算示例结果：

优化

通过对结果进行初始化，能够保证初始化结果的位数与实际结果位数近似，减少不必要的迭代。虽然通过二分法能够很大程度上节省时间，但在时间复杂度上仍然有很大的提升空间。

比如前面提到试商比较可以合并为一步来提高时间效率，在乘法运算过程中从高位节点开始进行运算，能够在乘法运算完成前提前返回比较结果，从而节省时间。

这种乘法运算过程好比一条拉链，也可以叫它拉链式乘法。高位运算如下图所示：

低位运算如下图所示：

以上运算示意图只是一个简单的演示，实际的拉链式乘法运算要比图中展示的复杂的多。同样的，从高位向低位运算的目的是为了在运算过程中快速的比较结果以提高时间效率。

在乘法运算过程中，临时乘积同被除数的比较只能判断临时乘积是否大于被除数。当临时乘积大于被除数时，也就意味着当前临时商大于实际结果。

待改进

当被除数与除数位数接近时，节点粒度即位数较大时，该算法运行效率会高于Java的BigInteger。但是当位数相差较大时，运行效率会比BigInteger差很多，而已知的耗时较大的部分仍然是试商比较。

另外，在选择节点粒度时，为了避免节点数值溢出，设置节点最大值为9999。这虽然使得在任何情况下都不会发生溢出，但仍然浪费一些数据存储的空间。该算法还存在着一些不足，运行效率不如BigInteger那样稳定，还有待改进。

结语

今天介绍了奇葩的大整数除法，在算法中也使用和熟悉了常见的数据结构。在算法的设计过程中，也能看到与官方算法存在的差距。虽然我们自己设计的算法不会应用于生产项目中，但在此过程中也能够收获编码的快乐。

可在Github中搜索bluesky-algorithm下载源代码，也可以点击下方了解更多在线查看。大家对于此算法有什么改进意见可以在评论区留言，期待你们的反馈。《奇葩算法》系列下一期再见。