↖  计算机程序设计艺术（卷2）：半数值算法..

[編按： 轉載于 圖靈社區ituring.com.cn, 2015-10-01. 以下為樣例章節，請試讀后購買正版授權全部内容。]

前言

亲爱的奥菲莉娅！这些数很让我头疼：我不知道自己叹息多少次了．

——《哈姆雷特》（第2 幕，第2 场，第120 行）

本书讨论的算法与数值直接相关．不过我认为把它们称为半数值算法也是恰如其分的，因为它们介于数值计算和符号计算之间．这些算法不仅仅计算了数值问题的答案，还试图很好地适应数字计算机的内部运算．

读者如果对计算机的机器语言没有一定的了解，很多情况下就无法充分体会到算法之美——相应的机器程序的效率是至关重要的，与算法本身密不可分．为了寻求计算机处理数值的最佳方法，我们既要考虑数值也要研究策略．因而本书的内容无疑既属于计算数学，也属于计算机科学．

有些在“较高层次”上从事数值分析工作的人可能会认为本书讨论的是系统程序员做的事情，而那些在“较高层次”上从事系统编程工作的人又会认为这些问题是数值分析人员要去考虑的．

但我希望还是会有一些人愿意认真研究本书中讲解的这些基本方法．虽然这些方法显得层次较低，但它们是用计算机解决强大的数值问题的基础，因此深入了解这些方法十分重要．

本书着重考虑的是计算数学与计算机程序设计之间的接口，这两类技巧的结合使得本书充满了趣味性．

与这套书的其他各卷相比，本书所讨论的内容中，数学内容所占的比例明显要大很多．多数情况下，书中数学知识的讨论几乎是从零开始的（或者从第1 卷的结果开始），但有几个小节仍然需要读者具备一定的微积分知识．

本卷包含整套书中的第3 章和第4 章．第3 章讨论“随机数”，不仅研究了生成随机序列的各种方法，而且还研究了随机性的统计测试，以及一致随机数到其他类型随机量的转换——后者说明了如何在实践中使用随机数．此外，我还专门用一节内容介绍了随机性本身的特性．

第4 章意在介绍经过数百年的发展之后，人们在算术运算上都有哪些美妙的发现．这一章(第四章)讨论了多种数值表示系统以及它们之间的相互转换，还介绍了浮点数、高精度整数、有理分式、多项式及幂级数的算术运算，包括因式分解和计算最大公因子的问题．

可以以第3 章或第4 章的内容为基础，为大学三年级到研究生层次的学生开设一学期的课程．目前许多学校都没有关于“随机数”和“算术”的课程，但我相信读者可以从这两章的内容中发现其实际教育价值．根据我自己的经验，这些课程可以很好地向大学生传授初等概率论和数论知识．

这类导论性课程中涉及的内容几乎都与实际应用有着自然的关联，而这些实际应用对学习和理解相应的理论是非常重要的．此外，每章都给出了一些涉及更深入问题的提示，可以激发学生进一步从事数学研究的兴趣．

除少数内容与第1 卷介绍的MIX 计算机有关之外，本书的大部分内容都是自成一体的．附录B 列出了本书用到的数学符号，有些与传统数学书中的符号略有不同．

第3 版前言

本书的第2 版完成于1980 年，它可以说是TEX 和METAFONT 这两个电子排版原型系统的第一个重要测试实例．上一版启发我开发和完善了这两个电子排版系统，现在第3 版又要问世了，我为这两个电子排版系统的成功感到由衷的高兴．

最终我可以使《计算机程序设计艺术》的各卷内容保持一致的格式，并能够适应印刷技术和显示技术上的变化．新的设置使得我可以在文字上进行数千处的改进，这是我多年来一直想做的校正．

我对新版的文字逐字进行了认真的审阅，力图在保持原有的蓬勃朝气的同时，加入一些可能更成熟的论断．新版增加了几十道新的习题，并为原有的几十道习题给出了改进的新答案．改动可谓无处不在，但最重要的改动集中在3.5 节（关于随机性的理论保证）、3.6 节（关于可移植的随机数生成程序）、4.5.2 节（关于二进制最大公因数算法）和4.7 节（关于幂级数的复合与迭代）．

《计算机程序设计艺术》丛书尚未完稿，而有关半数值算法的研究也还在快速发展．因此书中有些部分还带有“建设中”的图标，以向读者致歉——这部分内容还不是最新的．我电脑中的文件里堆满了重要的材料，打算写进第2 卷最后壮丽无比的第4 版中，或许从现在算起还需要16 年的时间．但我必须先完成第4 卷和第5 卷，非到万不得已，我不想拖延这两卷的出版时间．

非常感谢在过去35 年中帮助我搜集素材和改进内容的数百人．准备这一新版本的大部分艰苦工作是由西尔维奥•利维和杰弗里•奥尔德姆完成的，利维十分专业地编辑了本书的电子文本，奥尔德姆则几乎把所有的插图都转换成了METAPOST 格式．我修正了细心的读者在第2版中发现的所有错误（还有读者未能察觉的一些错误），并尽量避免在新增内容中引入新的错误．但我猜测可能仍然有一些缺陷，我希望能尽快加以改正．因此，我很乐意向首先发现技术性错误、印刷错误或历史知识错误的人按每处支付$2.56．下列网页上列出了所有已反馈给我的最新勘误：http://www-cs-faculty.stanford.edu/~knuth/taocp.html．

高德纳

加利福尼亚州斯坦福市

1997 年7 月

对于一本撰写时间长达8 年的书而言，需要感谢的同事、打字员、学生、老师和朋友太多了．此外，我不想按常规做法免除他们对于书中错误的责任，他们应该帮我纠正这些错误！有时候，他们甚至需要为一些将来被证明是错误的观点负责．不管怎样，我要对这些共事的伙伴们表示感谢．

——爱德华•坎贝尔（小）（1975）

“Defendit numerus”（数值是安全的）是傻瓜的格言；

“Deperdit numerus”（数值有毁灭性）是智者的格言．

——查尔斯•科尔顿（1820）

本页Url