计算机程序设计艺术.第2卷,半数值算法(英文版.第3版)（计算机大师高德纳权威著作，精装版）

　　《计算机程序设计艺术》系列被公认为计算机科学领域的权威之作，深入阐述了程序设计理论，对计算机领域的发展有着极为深远的影响。本书是该系列的第2 卷，讲解半数值算法，分“随机数”和“算术”两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。
　　本书适合从事计算机科学、计算数学等各方面工作的人员阅读，也适合高等院校相关专业的师生作为教学参考书，对于想深入理解计算机算法的读者，是一份必不可少的珍品。

chapter 3　random numbers　
3.1　introduction　
3.2　generating uniform random numbers　
3.3　statistical tests　
3.4　other types of random quantities　
3.5　what is a random sequence?　
3.6　summary　
chapter 4　arithmetic　
4.1　positional number systems　
4.2　floating point arithmetic
4.3　multiple precision arithmetic
4.4　radix conversion　
4.5　rational arithmetic　
4.6　polynomial arithmetic
*4.7　manipulation of power series　
answers to exercises　
appendix a　tables of numerical quantities　
1. fundamental constants (decimal)　
2. fundamental constants (octal)　
3. harmonic numbers, bernoulli numbers, fibonacci numbers　

　　亲爱的奥菲莉娅！
　　这些数很让我头疼：我不知道自己叹息多少次了。
　　——《 哈姆雷特》（第2 幕，第2 场，第120 行）
　　本书讨论的算法与数值直接相关。不过我认为把它们称为半数值算法也是恰如其分的，因为它们介于数值计算和符号计算之间。这些算法不仅仅计算了数值问题的答案，还试图很好地适应数字计算机的内部运算。读者如果对计算机的机器语言没有一定的了解，很多情况下就无法充分体会到算法之美——相应的机器程序的效率是至关重要的，与算法本身密不可分。为了寻求计算机处理数值的最佳方法，我们既要考虑数值也要研究策略。因而本书的内容无疑既属于计算数学，也属于计算机科学。
　　有些在“较高层次”上从事数值分析工作的人可能会认为本书讨论的是系统程序员做的事情，而那些在“较高层次”上从事系统编程工作的人又会认为这些问题是数值分析人员要去考虑的。但我希望还是会有一些人愿意认真研究本书中讲解的这些基本方法。虽然这些方法显得层次较低，但它们是用计算机解决强大的数值问题的基础，因此深入了解这些方法十分重要。本书着重考虑的是计算数学与计算机程序设计之间的接口，这两类技巧的结合使得本书充满了趣味性。
　　与这套书的其他各卷相比，本书所讨论的内容中数学内容所占的比例明显要大很多。多数情况下，书中数学知识的讨论几乎是从零开始（或者从第1 卷的结果开始）的，但有几个小节仍然需要读者具备一定的微积分知识。
　　本卷包含整套书中的第3 章和第4 章。第3 章讨论“随机数”，不仅研究了生成随机序列的各种方法，还研究了随机性的统计测试，以及一致随机数到其他类型随机量的转换——后者说明了如何在实践中使用随机数。此外，我还专门用一节内容介绍了随机性本身的特性。第4 章意在介绍经过数百年的发展之后，人们在算术运算上都有哪些美妙的发现。这一章讨论了多种数值表示系统以及它们之间的相互转换，还介绍了浮点数、高精度整数、有理分式、多项式及幂级数的算术运算，包括因式分解和计算最大公因子的问题。
　　可以以第3 章或第4 章的内容为基础为大学三年级到研究生层次的学生开设一学期的课程。目前许多学校都没有关于“随机数”和“算术”的课程，但我相信读者可以从这两章的内容中发现其实际教育价值。根据我自己的经验，这些课程可以很好地向大学生传授初等概率论和数论知识。这类导论性课程中涉及的内容几乎都与实际应用有着自然的关联，而这些实际应用对学习和理解相应的理论是非常重要的。此外，每章都给出了一些涉及更深入问题的提示，可以激发许多学生进一步从事数学研究的兴趣。除少数内容与第1 卷介绍的计算机有关之外，本书的大部分内容都是自成一体的。附录B 列出了本书用到的数学符号，有些与传统数学书中的符号略有不同。
　　第3 版前言
　　本书的第2 版完成于1980 年，它可以说是和这两个电子排版原型系统的第一个重要测试实例。上一版启发我开发和完善了这两个电子排版系统，现在第3 版又要问世了，我为这两个电子排版系统的成功感到由衷的高兴。最终我可以使《计算机程序设计艺术》的各卷内容保持一致的格式，并能够适应印刷技术和显示技术上的变化。新的设置使得我可以在文字上进行数千处的改进，这是我多年来一直想做的校正。
　　在这一新版本中，我对文字逐字进行了认真的审阅，力图在保持原有的蓬勃朝气的同时加入一些可能更成熟的论断。新版增加了几十道新的习题，并为原有的几十道习题给出了改进过的新答案。改动可谓无处不在，但最重要的改动集中在3.5节（关于随机性的理论保证）、3.6 节（关于可移植的随机数生成程序）、4.5.2 节（关于二进制最大公因子算法）和4.7 节（关于幂级数的复合与迭代）。
　　《计算机程序设计艺术》这套书尚未完稿，而有关半数值算法的研究也还在快速发展。因此书中有些部分还带有“建设中”的图标，以向读者致歉——这部分内容还不是最新的。我电脑中的文件里堆满了重要的材料，打算写进第2 卷最终的壮丽无比的第4 版中，或许从现在算起还需要16 年的时间。但我必须先完成第4 卷和第5 卷，非到万不得已，我不想拖延这两卷的出版时间。非常感谢在过去35 年中帮助我搜集素材和改进内容的数百人。准备这一新版本的大部分艰苦工作是由Silvio Levy 和Jeffrey Oldham 完成的，Silvio 十分专业地编辑了本书的电子文本，Jeffrey 则几乎把所有的插图都转换成了格式。
　　我修正了细心的读者在第2 版中发现的所有错误（以及读者未能察觉的一些错误），并尽量避免在新增内容中引入新的错误。但我想可能仍然有一些缺陷，我希望能尽快加以改正。因此，我很乐意向首先发现技术性错误、印刷错误或历史知识错误的人按每处错误2.56 美元支付报酬。下列网页上列出了所有已反馈给我的错误的最新
　　更正：http://www-cs-faculty.stanford.edu/~knuth/taocp.html。
　　高德纳（Donald E. Knuth）
　　1997 年7 月于加利福尼亚州斯坦福市
　　对于一本撰写时间长达8 年的书而言，
　　需要感谢的同事、打字员、学生、老师和朋友太多了。此外，我不想按常规做法免除他们对于书中错误的责任，他们应该帮我纠正这些错误！
　　有时候，他们甚至需要为一些将来被证明是错误的观点负责。
　　不管怎样，我要对这些共事的伙伴们表示感谢。

　　这一多卷本的鸿篇巨著被公认为对经典计算机科学的权威论述，数十年来，前3卷一直是广大学生、研究人员和业内人士学习程序设计理论和实践的无价之宝。
　　这是一部包含一切基础算法的宝典，是它教给了这一代软件开发人员关于计算机程序设计的绝大多数知识。
　　——Byte杂志1995年9月刊
　　无数的读者谈到过高德纳的著作对于自己的深刻影响。从事研究的人惊艳于他精美优雅的分析，而普通程序员则一直在卓有成效地利用书中提供的各种方案解决日常问题。这些书展现了作者的博观、清晰、精确和幽默，所有的人都钦佩不已。
　　我简直说不清楚这些书给我的学习和娱乐带来了多少欢乐时光。我在各种场合一有空就仔细研读，在车上，在餐馆，上班时，回到家里……甚至有次观看我儿子的球赛，趁他没上场的时候，我还拿出来看了一阵子。
　　——Charles Long
　　它本来是当参考书写的，但有些人却发现每一卷都可以兴致勃勃地从头读到尾。有位中国的程序员甚至把它比做读诗。
　　如果你自以为是一个很好的程序员，请去读读高德纳的《计算机程序设计艺术》吧……要是你真把它读下来了，就毫无疑问可以给我递简历了。——比尔·盖茨
　　不管你的背景如何，只要你想认真地编写计算机程序，都有很好的理由把这套书的每一卷抱回家，便于研究和工作时随时翻阅。
　　遇到问题需要把高德纳的著作请下书架，总是个令人愉悦的经历。我发现，只要翻一翻这些书，就会立竿见影地“镇住”计算机。
　　——Jonathan Laventhol