计算机程序设计艺术 第2卷 半数值算法（第3版）（英文影印版）
点击看大图基本信息
内容简介回到顶部↑
[center][a href="#" onclick='winpop(7469);return false;'][img src=/computers/ebook/7469/cover.gif border=0][/a][/center]
第2卷对半数值算法领域做了全面介绍，分“随机数”和“算术”两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。第3版中特别值得注意的是knuth对随机数生成程序的重新处理和对形式幂级数计算的讨论。
第2卷对半数值算法领域做了全面介绍，分“随机数”和“算术”两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。第3版中特别值得注意的是knuth对随机数生成程序的重新处理和对形式幂级数计算的讨论。
作译者回到顶部↑
本书提供作译者介绍
Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在1962年他还是加利福尼亚理工学院的研究生时就开始了。Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金.. << 查看详细
目录回到顶部↑
chapter 3 random numbers.
introduction.
generating uniform random numbers.
the linear congruential method.
other methods.
statistical tests.
general test procedures for studying random data.
empirical tests.
theoretical tests.
the spectral test.
other types of random quantities.
numerical distributions.
random sampling and shuffling.
what is a random sequence?
summary.
chapter 4 arithmetic.
positional number systems.
floating point arithmetic.
single-precision calculations.
introduction.
generating uniform random numbers.
the linear congruential method.
other methods.
statistical tests.
general test procedures for studying random data.
empirical tests.
theoretical tests.
the spectral test.
other types of random quantities.
numerical distributions.
random sampling and shuffling.
what is a random sequence?
summary.
chapter 4 arithmetic.
positional number systems.
floating point arithmetic.
single-precision calculations.
前言回到顶部↑
THE ALGORITHMS discussed in this book deal directly with numbers; yet I believe they are properly called seminumerical, because they lie on the borderline between numeric and symbolic calculation. Eacli algorithm not only computes the desired answers to a numerical problem, it also is intended to blend well with the internal operations of a digital computer. In many cases people are not able to appreciate the full beauty of such an algorithm unless they also have some knowledge of a computer's machine language; the efficiency of the corresponding machine program is a vital factor that cannot be divorced from the algorithm itself. The problem is to find the best ways to make computers deal with numbers, and this involves tactical as well as numerical considerations. Therefore the subject matter of this book is unmistakably a part of computer science, as well as of numerical mathematics.
Some people working in "higher levels" of numerical analysis will regard the topics treated here as the domain of system programmers. Other people working in "higher levels" of system programming will regard the topics treated here as the domain of numerical analysts. But I hope that there are a few people left who will want to look carefully at these basic methods. Although the methods reside perhaps on a low level, they underlie all of the more grandiose applications of computers to numerical problems, so it is importat to know them well. We are concerned here with the iaterface between numerical mathematics and compoter programming, and it is the mating of both types of skills that makes the subject so interesting.
There is a noticeably higher percentage of mathematical material in this book than in other volumes of this series, because of the nature of the subjects treated. In most cases the necessary mathematical topics are developed here stating almost from scratch (or from results proved in Volume 1), bat in several easily recognizable sections a knowledge of calculus has been assumed.
This volume comprises Chapters 3 and 4 of the complete series. Chapter 3 is concerned with"random numbers": It is not only a study of various ways to generate random sequences, it also investigates statistical tests for randomness, as well as the transformation of uniform random numbers inio other types of random quantities; the latter subject illustrates how random numbers are used in practice. I have also included a section about the nature of randomness itself. Chapter 4 is my attempt to tell the fascinating story of what people have discovered about the processes of arithmetic, after centuries of progress. It discusses various Systems for representing numbers, and how to convert between them; and it treats arithmetic on floating point numbers, high--precision integers, rational fractions, polynomials, and power series, including the questions of factoring and finding greatest common divisors.
Each of Chapters 3 and 4 can be used as the basis of a one--semester college course at the junior to graduate level. Although courses on "Random Numbers" and on "Arithmetic" are not presently a part of mally college curricula, I believe the reader will find that the subject matter of these chapters lends itself nicely to a unified treatment of material that has real educational value. My own experience has been that these courses are a good means of introducing
elementary probability theory and number theory to college students. Nearly all of the topics usually treated in such introductory courses arise naturally in connection with applications, and the presence of these aPpIications can be an important motivation that helps the student to learn and to appreciate the theory Furthermore, each chapter gives a few hints of more advanced topics that will whet the appetite of many students for further mathematical study.
For the most part this book is self contained, except for occasional discussions relating to the MIX computer explained in Volume l. Appendix B contains a summary of the mathematical notations used, some of which are a little different from those found in traditional mathematics books.
Preface to the Third Edition
When the second edition of this book was completed in l980, it represented the first major test case for prototype systems of electronic publishing called TEX and METRFONT. I am now pleased to celebrate the full development of those systems by returning to the book that inspired and shaped them. At last I am able to have all volumes of The Art of Computer Programming in a consistent format that will make them readily adaptable to future changes in printing and
display technology. The new setup has allowed me to make many thousands of improvements that I have been wanting to incorporate for a long time.
In this new edition I have gone over every word of the text, trying to retain the youthful exuberance of my original sentences while perhaps adding some more mature judgment. Dozens of new exercises have been added; dozens of old exercises have been given new and improved answers. Changes appear everywhere, but most significantly in Sections 3.5 (about theoretical guarantees of randomness), 3.6 (about portable random--number generators), 4.5.2 (about the binary gcd algorithm), and 4.7 (about composition and iteration of power series).
The Art of Computer Programming is, however, still a work in progress. Research on seminumerical algorithms continues to grow at a phenomenal rate. Therefore some parts of this book are headed by an "under construction" icon, to apologize for the fact that the material is not up-to-date. My files are bursting with important material that l p1an to include in the fina1, glorious, fourth edition of Volume 2, perhaps 16 years from now; but I must finish Volumes 4 and 5 first, and I do not want to delay their publication any more than absolutely necessary.
I am enormously grateful to the many hundreds of people who have helped me to gather and refine this material during the past 35 years. Most of the hard work of preparing the new edition was accomplished by Silvio Levy, who expertly edited the electronic text, and by Jeffrey Oldham, who converted nearly all of the orginal illustrations to METRPOST format. I have corrected every error that alert readers detected in the second edition (as well as some mistakes that, alas,
nobody noticed); and I have tried to avoid illtroducing new errors in the new material. However, I suppose some defects still remain, and I want to fix them as soon as possible. Therefore I will cheerfully pay $2.56 to the first finder of each teclinica1, typographical, or historical error. The webpage cited on page iv coatains a current listing of all corrections that have been reported to me.
Stanford, California D.E.K
July 1997
When a book has been eight years in the making, there are too many colleagues, typists, students, teachers, and friends to thank.
Besides, I have no intention of giving such people the usual exoneration from responsibility for errors which remain.
They should have corrected me!
And sometimes they are even oponsible for ideas which may turn out in the long run to be wrong. Anyway, to such fellow explorers, my thanks.
Some people working in "higher levels" of numerical analysis will regard the topics treated here as the domain of system programmers. Other people working in "higher levels" of system programming will regard the topics treated here as the domain of numerical analysts. But I hope that there are a few people left who will want to look carefully at these basic methods. Although the methods reside perhaps on a low level, they underlie all of the more grandiose applications of computers to numerical problems, so it is importat to know them well. We are concerned here with the iaterface between numerical mathematics and compoter programming, and it is the mating of both types of skills that makes the subject so interesting.
There is a noticeably higher percentage of mathematical material in this book than in other volumes of this series, because of the nature of the subjects treated. In most cases the necessary mathematical topics are developed here stating almost from scratch (or from results proved in Volume 1), bat in several easily recognizable sections a knowledge of calculus has been assumed.
This volume comprises Chapters 3 and 4 of the complete series. Chapter 3 is concerned with"random numbers": It is not only a study of various ways to generate random sequences, it also investigates statistical tests for randomness, as well as the transformation of uniform random numbers inio other types of random quantities; the latter subject illustrates how random numbers are used in practice. I have also included a section about the nature of randomness itself. Chapter 4 is my attempt to tell the fascinating story of what people have discovered about the processes of arithmetic, after centuries of progress. It discusses various Systems for representing numbers, and how to convert between them; and it treats arithmetic on floating point numbers, high--precision integers, rational fractions, polynomials, and power series, including the questions of factoring and finding greatest common divisors.
Each of Chapters 3 and 4 can be used as the basis of a one--semester college course at the junior to graduate level. Although courses on "Random Numbers" and on "Arithmetic" are not presently a part of mally college curricula, I believe the reader will find that the subject matter of these chapters lends itself nicely to a unified treatment of material that has real educational value. My own experience has been that these courses are a good means of introducing
elementary probability theory and number theory to college students. Nearly all of the topics usually treated in such introductory courses arise naturally in connection with applications, and the presence of these aPpIications can be an important motivation that helps the student to learn and to appreciate the theory Furthermore, each chapter gives a few hints of more advanced topics that will whet the appetite of many students for further mathematical study.
For the most part this book is self contained, except for occasional discussions relating to the MIX computer explained in Volume l. Appendix B contains a summary of the mathematical notations used, some of which are a little different from those found in traditional mathematics books.
Preface to the Third Edition
When the second edition of this book was completed in l980, it represented the first major test case for prototype systems of electronic publishing called TEX and METRFONT. I am now pleased to celebrate the full development of those systems by returning to the book that inspired and shaped them. At last I am able to have all volumes of The Art of Computer Programming in a consistent format that will make them readily adaptable to future changes in printing and
display technology. The new setup has allowed me to make many thousands of improvements that I have been wanting to incorporate for a long time.
In this new edition I have gone over every word of the text, trying to retain the youthful exuberance of my original sentences while perhaps adding some more mature judgment. Dozens of new exercises have been added; dozens of old exercises have been given new and improved answers. Changes appear everywhere, but most significantly in Sections 3.5 (about theoretical guarantees of randomness), 3.6 (about portable random--number generators), 4.5.2 (about the binary gcd algorithm), and 4.7 (about composition and iteration of power series).
The Art of Computer Programming is, however, still a work in progress. Research on seminumerical algorithms continues to grow at a phenomenal rate. Therefore some parts of this book are headed by an "under construction" icon, to apologize for the fact that the material is not up-to-date. My files are bursting with important material that l p1an to include in the fina1, glorious, fourth edition of Volume 2, perhaps 16 years from now; but I must finish Volumes 4 and 5 first, and I do not want to delay their publication any more than absolutely necessary.
I am enormously grateful to the many hundreds of people who have helped me to gather and refine this material during the past 35 years. Most of the hard work of preparing the new edition was accomplished by Silvio Levy, who expertly edited the electronic text, and by Jeffrey Oldham, who converted nearly all of the orginal illustrations to METRPOST format. I have corrected every error that alert readers detected in the second edition (as well as some mistakes that, alas,
nobody noticed); and I have tried to avoid illtroducing new errors in the new material. However, I suppose some defects still remain, and I want to fix them as soon as possible. Therefore I will cheerfully pay $2.56 to the first finder of each teclinica1, typographical, or historical error. The webpage cited on page iv coatains a current listing of all corrections that have been reported to me.
Stanford, California D.E.K
July 1997
When a book has been eight years in the making, there are too many colleagues, typists, students, teachers, and friends to thank.
Besides, I have no intention of giving such people the usual exoneration from responsibility for errors which remain.
They should have corrected me!
And sometimes they are even oponsible for ideas which may turn out in the long run to be wrong. Anyway, to such fellow explorers, my thanks.
加载中...
