计算机程序设计艺术 第2卷 半数值算法（第3版）

　　[center][a href="#" onclick='winpop(7544);return false;'][img src=/computers/ebook/7544/cover.gif border=0][/a][/center]
　　
　　 本书是国内外业界广泛关注的7卷本《计算机程序设计艺术》第2卷的最新版。本卷对半数值算法领域做了全面介绍，分“随机数”和“算术”两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系，其中特别值得注意的是作者对随机数生成程序的重新处理和对形式幂级数计算的讨论。 本书附有大量习题和答案，标明了难易程度及数学概念的使用。 本书内容精辟，语言流畅，引人入胜，可供从事计算机科学、计算数学、计算技术诸方面的工作人员参考、研究和借鉴，也是相关专业高等院校的理想教材和教学参考书。 [a href="http://www.china-pub.com/computers/common/info.asp?id=7469" target="_blank"][b]
　　
　　 《计算机程序设计艺术（英文影印版）》（1-3卷精装全套） [/b][/a]
　　
　　 [strong][a href="http://www.china-pub.com/computers/bookinfo/hy.htm" target="_blank"]翻译《计算机程序设计艺术》经过的片断回忆苏运霖[/a][/strong]
　　

第3章 随机数
3．1 引言
3．2 生成一致随机数
3．2．l 线性同余法
3．2．l．1 模数的选择
3．2．1．2 乘数的选择
3．2．1．3 效能
3．2．2 其它方法
3．3 统计检验
3．3．l 研究随机数据的一般检验方法
3．3．2 经验检验
3．3．3 理论检验
3．3．4 谱检验
3．4 其它类型的随机量
3．4．l 数值分布
3．4．2 随机抽样和洗牌
3．5 什么是随机序列
3．6 小结
第4章算术
4．1 定位计数系统

　　 O dear Ophelia!
　　I am ill at these numbers:
　　I have not art to reckon my groans．
　　亲爱的奥菲利娅；
　　这些数真让人烦恼：
　　我可没有计算我的愁怀的技巧。
　　——Hamlet(Act ll，Scene 2，Line l20)
　　本书所讨论的算法直接地涉及数。但我相信把它们叫做半数值算法是适当的，因为它们处于数值和符号计算的边界线上；每个算法不仅计算数值问题所要求的答案，而且它也应与一台数字计算机的内部操作很好地融合。在许多情况下，人们都不可能充分品味某个算法的美，除非他也懂计算机机器语言；相应的机器程序的有效性是不能同算法本身分开的一个重要因素。问题是寻找出计算机处理数的最佳方法，这既要考虑数值，又要研究策略。因此本书的主题显然既是数值数学的一个部分，也是计算机科学的一个部分。
　　在数值分析的“高层次”上工作的某些人将把这里处理的课题当做是系统程序员的领域，而工作在系统程序设计“高层次”上的其他人将把这里处理的课题当做数值分析的领域。但我相信，还会剩下一些人，他们将愿意仔细地考察这些基本方法。尽管这些方法或许处于低层次上，但是它们却奠定了计算机在数值问题上的所有更强大应用的基础，因此了解它们就很重要了。在这里我们最关心的是数值数学和计算机程序设计之间的界面。
　　本书比起本丛书的其他卷来，其数学内容所占比例要显著地高得多。这是由于所处理的课题所致。大多数情况下，在这里所展开的必要的数学课题几乎都是从很皮毛的内容开始的(或者从第1卷证明的结果开始的)。但是在若干部分，显然仍需要读者具有一定的微积分学知识。
　　本卷是由整套丛书的第3章和第4章组成的。第3章涉及“随机数”：它不单单是对生成随机序列的各种方法的研究，它还研究随机性的统计检验，以及一致随机数与其它类型随机晕间的转换；后一课题说明在实践中如何使用随机数。本章还有一节包括了随机数本身的性质。第4章的意图是讲述经历了数百年的进步之后，人类对算术运算的有趣发现；它论述了表示数的各种系统，以及在这些系统之间如何进行转换；而且它还处理关于浮点数、高精度整数、有理数、多项式及幂级数的算术运算，也包括因子分解和求最大公因子等问题在内。
　　第3章和第4章均可作为从大学三年级到研究生层次的一学期课程的基础。尽管“随机数”和“算术”的程现在都不是许多大学课程表的一部分，但我相信，读者会发现这两章的学科内容本身是有实际教育价值的，非常适合于统一论述。我本人的经验是，这些课程是向大学生们介绍初等概率论和数论的很好的手段。通常，在这样的入门性课程中讨论的几乎所有课题都很自然地在同应用相关联中出现，而这些应用可以成为促进学生学习和鉴赏理论的重要因素。其次，每一章都给出一些更深入课题的提示，它们将激发许多学生进行进一步研究的兴趣。
　　本书的大部分内容都是自成体系的，除了偶尔涉及在第1卷中说明的MIX计算机的讨论外。附录B列出了本书所用的数学符号，其中一些符号与传统数学书中略有差别。
　　 第3版前言：
　　 本书的第2版完成于1980年，它实际上也是电子排版系统TEX和METAFONT的第一个重大的测试实例。现在我高兴地用她(正是为了她我萌发了开发电子排版系统的念头)的第3版庆祝TEX和METAFONT的全面开发成功。最终我将能以一致的格式拥有《计算机程序设计艺术》的所有各卷，而这将使它们很容易适应未来在印刷和显示技术上的变化。这些进展已经使我得以把长期以来一直想要做的数以千计的改进收到这些书中。
　　我逐字逐句地审阅了新版的所有文字，在或许加上一些更为深思熟虑的论述的同时，我试图保留原来句子的朝气；增添了几十道新习题，还对几十道旧的习题给出了新的和改进了的答案。变动随处可见，但最主要的是在3．5节(关于随机性的理论保证)，3．6节(关于可移植的随机数生成程序)，4．5．2小节(关于二进制的最大公因子算法，以及4．7节(关于幂级数的合成和迭代)。
　　然而，《计算机程序设计艺术》的写作仍然是进行中的工作。关于半数值算法的研究继续以非凡的速度在发展着。因此，本书的某些部分被冠以“正在施工”的图标，用于对该部分的内容还不是最新表示歉意。我的文件中已经挤满了许多重要的素材。我打算从现在开始用大约16年的时间，把这些素材包含在第2卷最后的辉煌的第4版中，但是，我必须首先完成第4卷和第5卷，而且除非绝对需要，我一刻也不想拖延它们的出版。
　　我要向在过去35年来帮助我搜集和改进这些素材的数百位人们致以最衷心的感谢
　　 关于习题的说明书：
　　 套书的习题既可用于自学，也可用于课堂练习。无论是谁，如果想纯粹地通过阅读，而不将所阅读的信息应用到特定问题上，并由此牵引思考先前阅读的内容，就想学到一门学问，纵然可能，那也是很困难的。其次，对于我们自己的发现，我们总是领会得最透。因此，习题形成了这一套书的一个重要部分：我着意使这些习题含有丰富的信息，而且也尽量选择既有趣又有启发性的习题。