——一种改进过的厄拉多塞筛法可加快电脑计算速度
Matias Loewy | 2016年9月24日
Harald Helfgott是一位秘鲁数学家，曾证明了弱哥德巴赫猜想（Goldbach’s weak conjecture）。
图片来源：Matías Loewy
秘鲁数学家Harald Helfgott在2013年得到了全世界的关注，因为当时他解决了一个已遗留271年的问题：弱哥德巴赫猜想——即每个大于5的奇数可以表示为三个素数的和，比如：2 + 3 + 5 = 11，19 + 13 + 3 = 35。
如今38岁的Helfgott正专注于更古老的研究对象：形成于大约公元前240年的厄拉多塞筛法（sieve of Eratosthenes）——一种寻找素数的常用方法。Helfgott通过改进这种方法，减少所需要的计算机内存空间，从而减少程序寻找素数的运行时间。
素数只能被1和自己整除，可被看作数学中的“原子”。鉴定素数可用厄拉多塞（Eratosthenes）提出的一种实用性方法:“筛法”。厄拉多塞是一名出生于希腊古利奈（Cyrene）的数学家、天文学家、地理学家，曾担任亚历山大图书馆（Library of Alexandria）馆长，以计算出地球周长而闻名。 “像许多其他孩子一样，我是在十岁读小学时，老师通过一张图表教会了我厄拉多塞筛法。”Helfgott说。Helfgott目前在国家科学研究中心（the National Center for Scientific Research ，CNRS）和哥廷根大学（University of G?ttingen）担任工作。
为了筛分出一定区间内（比如1和100之间）的所有素数，需要将数字按从小到大的顺序列出，再按规则划掉一些数字：首先划掉2的倍数(除了2)，然后划掉3的倍数（除了3），依次划掉下一个还没被划掉的数的倍数（除了它本身），最后留下的数字就是素数。该方法可以编写为一种电脑能快速运行的算法。
Helfgott在校正书籍（关于弱哥德巴赫猜想的彻底证明）时，开始思考：或许厄拉多塞筛法太耗时间了，尤其是它需要巨大的内存空间。“如今计算机运行速度非常快，也可以执行并行计算，但内存仍然有限。”Helfgott解释道。
同时就职于康奈尔大学（Cornell University）和洛杉矶安第斯大学（Los Andes University）的数学家Jean Carlos Cortissoz Iriarte表示，要知道一种算法的好坏，必须考虑两个因素：输入一个数值(例如100)时每一位的运算次数，以及在执行指令时存储的位数。“就每一位的运算次数而言，厄拉多塞筛法相对高效。同时，每一位的运算次数与区间大小成正比。但如果考虑到较大区间执行每一步算法需要的内存，厄拉多塞筛法就不再高效了。” Cortissoz说道。
通过结合有100年历史的解析方法——哈代-李特尔伍德圆法（Hardy-Littlewood circle method），Helfgott得以改进厄拉多塞筛法，使计算过程占用更少的物理存储空间。以数学术语表述：不再需要大小为N的内存，而仅仅需要N的立方根的内存量。“用改进后的厄拉多塞筛法计算一万亿以内的所有素数，需要的内存从原先的数十亿比特减少到了数百万比特。”Helfgott说道。该想法于今年7月在两处会议中提出：一个是在布宜诺斯艾利斯举行的“第二十一届拉丁美洲代数讨论会（the XXI Latin American Colloquium of Algebra）”，一个是由居住在欧洲巴黎的秘鲁科学家们举行的会议“Sinapsis 2016”。
为了便于理解这种改进筛法的优势，Cortissoz做了如下类比：“假装你是一台电脑，你需要使用纸张记录存储数据。如果计算1和1000000之间的素数，你需要200令纸(100000张)，而使用Helfgott提出的算法，你将只需要0.2令纸(约100张)。”
减少空间需求通常意味着运行速度会做出点“小小的”牺牲，但Helfgott相信，通过主要使用甚至完全使用高速缓冲存储器——比主存储器和随机存储器的体积更小、速度更快，可以在一定范围内使运行速度不变或更快。“运行速度与具体应用情况有关。” Helfgott表示。
除了厄拉多塞筛法，还有其他的筛法和不同类型的算法来识别素数。但Helfgott指出，厄拉多塞筛法非常独特，它不仅能找出素数，还能作用于其它的数学运算，比如因式分解——将任何一个数字分解为素数的乘积，这是安全编码信息所用加密算法的基础，应用于电子银行转帐、网上购物等方面。“因式分解已经成为现代文明不可或缺的一部分。”Helfgott说道。而这或许连厄拉多塞自己都永远不会想到。
翻译：何成自菁
审稿：林然
原文链接：
特别声明：本文转载仅仅是出于科普传播信息的需要，并不意味着代表本网站观点或证实其内容的真实性；如其他媒体、网站或个人从本网站转载使用，须保留本网站注明的“来源”，并自负版权等法律责任；作者如果不希望被转载或其它相关事宜，请与我们接洽。
