问题13 大数乘法三解
常用的程序设计语言中都提供算术表达式功能，直接使用即可。
【资料图】
发明计算机最初的目的，计算弹道，密码破译，都是为了高效的计算。
程序设计初学者往往认为算术运算是非常简单的事。但是，当计算的数很大（位数很多）时，就不是一件简单的事情了，需要结合计算方法和算法设计两方面的知识，才能让计算机高效的计算“大”数。
本章，作者针对求两个大整数的精确乘问题，介绍了三种风格迥异的方法。
第一种方法，利用字符串（存储大整数）和列表（存储中间结果和最后的乘积），让计算机直接模拟手工“长乘法”。这个算法理论上不受乘数大小的限制。
计算机执行一次乘法操作的时间远远大于加法操作的时间。如何减小大数乘法中乘法操作的次数，可以提高大数乘法的执行效率。
本章介绍的第二种方法是Karatsuba算法（书中的名字打错了）是一种快速乘法算法。算法采用了分治法的策略，使用三个较小数字的乘法来计算两个大数的乘积的公式（我第一次在算法书中看到时，大为震撼）。它将算法的复杂度从n的平方量级降到log23
本章介绍的第三种方法，称为“中国余数定理”（来源与《孙子算经》），把两个大的乘数分解到一些互素的模上，然后通过解同余方程组，就可得到相应的乘积。这种方法可以大幅度降低乘数的位数，从而提高执行效率。
【作者感受】
学计算机的人，都是数学还不错的，不过每次看到这样的章节，总觉得数学还学得不够，难怪，有人推荐，本科学数学，研究生再进入计算机领域。在计算机领域中混，数学不好真不行。
关键词：
