Question

【C++】大整数除法的算法

求比较简单的算法
如果有用到什么比较少见的函数说明一下

Answer 1

你首先需要实现大整数的减法。这个从低到高位减即可。

还需要实现大整数乘以一个个位数的算法。从低位向高位乘即可。

剩下的步骤我用一个例子来表示，如图所示

Answer 2

　　第一种方法是求倒数，根据牛顿迭代法，设序列{Xn}，递推公式为X(n+1)=2X(n)-aX(n)²，a为常数且为正，则当X0∈(0,1]时有lim<n→∞>(Xn)=1/a，且精度随着迭代次数指数增长。故方法一为根据递推公式求除数的倒数（因为被除数大于1，倒数一定小于1，可以用定点数表示），然后乘以被除数即得到原来的商。迭代次数为logN，每次迭代中需要进行一次移位和两次大整数乘法，定点数乘法还要额外加一次移位，总时间复杂度为O(logN * (N + NlogN + NlogN)) = O(Nlog²N)；

第二种方法是第一种方法的改进版，设被除数为a，除数为b，则写成分式为a/b，分式具有分子分母同时乘以非零数值不变的性质，首先将分子分母乘以一常数X，使得bX∈(0,1]，然后将分子分母同时乘以(2-分母)，不断进行迭代直至分母足够接近1，此时分子即是所求的商。与方法一相比，方法二不需要估算X0，每次迭代仍然需要两次乘法两次移位，因此时间复杂度仍然是 O(Nlog²N)。部分AMD处理器的浮点除法采用此方法进行；

第三种方法即是常用的试商法。分为按位试商和按双字试商两种。按位试商只要逐一移位比较即可，时间复杂度O(N²)。按双字试商则由于试商存在误差，必须在试商之后用试商乘以除数与被除数作比较，由于是双字乘以大整数时间为线性，总体时间复杂度为O(N+(N-1)+(N-2)+(N-3)+...+1)=O(N(N+1)/2)=O(N²)。总之试商法的时间复杂度是O(N²)。

那么问题来了，方法一和方法二的共同特点是，每次迭代都必须进行两次至少N位的乘法，因此浪费了大量时间。实测即使是数万位数的除法（尤其是被除数远远长于除数的情况下，为了降低定点数误差就必须将被除数和除数左移位相当长的距离）方法二的时间依然是方法三的时间的数十倍甚至上百倍。而且方法三可以同时获得商和余数，方法一和方法二都做不到。