在讨论具体讨论第四题之前，我想先和大家讨论一下大数运算的问题，算是做一点科普铺垫呵呵。
一般我们把超出计算机能直接运算范围的数，都叫做大数。
为了讨论方便，我把在计算机直接运算范围内的数称为，常规数。（重要申明：这是我的定义，非官方正式名称）
大数运算，我们指的是有大数参与的运算。这是个统称，它又可以分为两类：大数与常规数的运算、大数与大数的运算。
在对大数进行运算前，首先要解决的问题是大数的存储问题。用数组存储是必然的，这几乎是句废话，如果单个变量就能存储那还叫大数么。关键是怎么用数组存储。
大数的存储方式是与它的操作方式相辅相成的。数据结构学的是什么？就是分析问题模型如何在计算机里存储，以及在这种存储方式下如何操作。
以大整数为例，我们一般用一个字节表示大整数的一个十进制位，至于数组的第0个元素表示大整数的最高位还是最低位，这要看应用的需求。一般大数运算应用以加法和乘法居多，在这两种计算中，结果的位数都有增大的趋势。这时如果选数组低位对应大数高位，则需要对数组做移位操作，这显然不如数组低位对应大数低位的操作（将进位值直接添再数组后面）来的简单。总之这种“小端”（类比多字节变量的存储）的存储方式在很多方面具有操作优势，但这并不意味着“大端”方式就一无是处，事实上，在下面的黄金分割数计算中我采用的就是“大端”方式。
在一些特定的运算中，我们会改变数组元素所表示的范围来加快运算，比如用一个字节表示两个十进制位，或四个字节（32位整型）表示5到9个十进制位等等。
这里我们说的都是十进制位，使用这个进位制的主要原因是为了结果显示的方便。而就计算效率来说，当然是二进制更优。
解决了大数的存储问题，我们才能谈论建立在这种存储格式上的计算问题。
对常规数有多少种计算，对大数就有多少种计算。我们不可能一一讨论，这里只谈“加减乘除”这四种最基本的运算，而且将讨论的重点放在“除法”运算上。而且我们主要以整数的运算为例，小数的运算是以整数运算为基础的，最后会提到。
我们以单字节表示大整数的一个十进制位，低位元素表示大整数低位，这样的数据格式为例分别谈谈各种运算方式。
加法运算：对应位与对应位相加，再加上进位，模10的部分为该位相加后的结果，除10的部分是该位向下一位的进位。我们一直是这么计算的，没有多解释的必要。这其实是大整数与大整数进行加法运算的法则。大整数与常规数的加法只需要将最低与常规数相加，之后是进位与其它位的和。这与大数与大数的加法本质是相同的，之所以提出来这想强调一下进位的数值不一定只能小于10（在现在的计算方式下）。
减法运算：完全是加法的逆运算。几乎将上面描述中的“加”全改成“减”就可以了，不再赘述。
乘法运算：也可以类比加法运算。关于大数乘法我看过一个分治法提高计算效率的算法，事实它通过因式变换，用加法代替乘法，减少其中乘法的运算次数。我记得他的化简结果中少了一次乘法运算，但多了七次加法运算。为此我当时特意查了86系列指令的执行时间来检查这种算法的可行性。在不同寻址方式下，加法指令需要约3~20个时钟周期，而乘法指令需要约70~140个时钟周期，总体上加法指令的执行速度要比乘法指令快数十倍，在这种芯片上运行这个算法确实可以提高运算效率。但对于现代的处理器我不知道是否还是这样。总之，对于这一算法的通用性我一直持保留意见。
除法运算：这是我们要讲的重点。关于除法运算我们也分两种。一是大数除以常规数，二是大数除以大数。
对于大数除以常规数，41楼罗庇鹏已经给了一个很好的示例。事实上这是将大数分解为常规数的作法。相当于(A+B)/C = A/C + B/C这个变换过程。这种作法利用了计算机对常规数的除法来运算，很方便，但无法将它应用到大数除以大数的过程中。
对于大数除以大数，这相当于(A+B)/(C+D)。这个除数的化解成了一个很难逾越的障碍。如果哪位成功逾越了它，请一定告诉我。
在自认为高级的方向行不通后，我开始回忆小学时的除法计算方法——长除法。
从被除数的最高位算起，寻找一个最大的整数使得它乘以除数后小于等于被除数的计算部分，这个最大的整数即是这一位的商数。余数乘10后加上被除数的下一位作为新了计算部分重复上述步骤。
这就是我们小学时的除法计算方法。我就不再强调十进制的事了。
我们要模拟这个计算过程，关键在于如何确定这个商数。小学时（其实现在也是）我们采用的方法是试商法，用一个数乘以除数看它与被除数的计算部分的大小。对于计算机，也没有一下子就找到商数的好方法（至少我没有）。我们可以一个一个的试，选一个数用它乘以除数然后与被除数计算部分作比较。上面已经讲过大数的乘法运算，所以这种做法是可行的。
未完，待续......
[
本帖最后由 beyondyf 于 2013-5-11 22:15 编辑 ]
2013-05-10 14:54
