齐心协力筛选

作者:Stan Kelly-Bootle
All Hands to the Sieve

如果你想对计算机科学的“最先进水平”彻底感到沮丧,除了运行/崩溃的Windows之外,你应该查看 Peter Neumann 的 RISKS 报告和 SANS Institute 定期发布的“漏洞”列表。 无论是多么“成熟”的操作系统、内核、编译器、库、解析器或命令,似乎都无法幸免。 我的天啊,我们不仅仅是在谈论千亿(谁知道?)电子表格的缺陷或数十亿丢失的宇宙飞船(对某些人来说是好事),而是基于 C 数组的语法怪癖的普遍、必然、未捕获的异常,尽管有无尽的警告。

SANS 最近发布的 FLASH 警报揭示了潜藏在 MS Access、Word 2000 和 Internet Explorer 5.00+ 内部的危险。 SANS 正在为“快速”修复提供奖励,但这些错误是完全“专有的”。 让我们面对现实,微软拥有比他们应得的更多的、受过最新软件工程议程训练的专家程序员。 事实上,Microsoft Press 提供了许多关于如何开发可证明“健壮”应用程序的圣经。 然而,尽管有旨在检测“明显”错误(内存泄漏和数组溢出)的语言和开发工具,但 MS 程序员的这支优秀团队却放出了...呃...狗。

当然,认识论上无法回答的挑战是首先定义“错误”,然后定义“无错误”。 即使是斯蒂芬·霍金的“简史...”开放式、时间历史编纂也可能不允许我们测试我们精心设计的代码中所有 if-then-else 的每一条路径。 最终以“自然”语言表达的“匹配”规范又意味着什么? (当霍金的宇宙时间倒转到大挤压时,我们会看到我们的 GOTOs 被映射为 COMEFROMs 吗?)

开源方法的成功取决于代码对许多公正的程序员的批判性暴露,他们唯一的目标是真正的目标,而一个承担股份期权的内部“奴隶”可能不愿惹是生非。

尽管如此,Linux 内核中最近的 SUID 安全漏洞表明(更多沮丧)简单的代码错误可能会逃脱多次阅读。 从好的方面来看,我们有(i)及时、公开的确认和修复;(ii)无数的替罪羊(boucs emissaries)——举手,谁是 144,000 名残余人员中的罪魁祸首。 Peter Salus 将记录你的忏悔/贡献。

即将由 Prentice-Hall 出版,Bob Toxen 的真实世界 Linux 安全(见注 1)。

GIMPS

转到广泛开放计算的另一个方面,GIMPS 是伟大的互联网梅森素数搜索(见注 2)。 超过 8,000 名个人用户正在寻找越来越大的素数。 早在很久以前,欧几里得就证明了没有尽头,因为如果 P 是最大的素数,那么 P!+1 要么是一个更大的家伙,要么它必须有一个大于 P 的素数因子。 QED!(其中 P! 表示阶乘 P,不要与第二个“!”混淆,它表达了惊讶和解脱!)

他们说,如果你看不到这个证明的美(经过适当的改进),你永远不会成为一名数学家。

而且,对你的感性意识的可靠测试是这样的:埃拉托色尼筛选法(另一个死去的希腊人)提供了一种较慢的算法,用于按升序序列列出每个素数。 我自己的凯利筛选法用一个 for 循环列出复合数素数。

关键在于 P 和 P!+1 之间是否有素数——1999 年 6 月,GIMPS 团队的 Nayan Hajratwala 创造了一项新的(临时)世界纪录

2^6,972,593 - 1

我将饶你七英里的数字和逗号来printf()这个数字。

下个月:如何通过 SETI 协作计划在 http://www.setiathome.ssl.berkeley.edu/ 帮助寻找外星智能。 [加入Linux Journal小组!—Ed.] 有可能一些绿色的小数学家已经知道下一个最大的素数。

注释

Stan Kelly-Bootle (skb@atdial.net) 自 20 世纪 50 年代以来一直断断续续地使用他的 EDSAC I(英国剑桥大学)进行计算。 他在许多专栏(“不仅仅是厄芬帕特农神庙”——Meilir Page-Jones)和书籍中评论了永恒不变的 DP 场景,包括计算机矛盾词典(麻省理工学院出版社)和UNIX 完全(Sybex)。 Stan 每月在 http://www.sarcheck.com/http://www.unixreview.com/ 上撰写文章。

加载 Disqus 评论