Donald Knuth的《计算机程序设计艺术》第二版

需积分: 9 126 浏览量更新于2024-07-28 收藏 43.37MB PDF 举报

"Donald_E._Knuth_-_The_Art_of_Computer_Programming - 这是一本由Donald E. Knuth编写的计算机编程经典著作，第二版，属于 Addison-Wesley 出版社的计算机科学与信息处理系列，涵盖了基础算法和半数值算法等主题。" 《计算机程序设计艺术》是Donald E. Knuth的一部多卷本巨著，旨在全面、深入地探讨计算机编程的艺术和科学。这本书分为多个卷，其中第二版的第二卷专注于"半数值算法"。Donald E. Knuth是斯坦福大学的教授，他在计算机科学领域具有极高的声望，尤其在算法分析方面的工作被誉为经典。该书的内容覆盖了电子数字计算机编程的基础和高级概念，包括但不限于： 1. **基础算法**：这部分可能涉及排序、搜索、递归、动态规划等基本算法，这些算法是所有编程问题的基础，并且在软件开发中起着至关重要的作用。 2. **半数值算法**：这部分内容可能涵盖数学计算的近似方法，比如数值积分、根查找、随机数生成、概率统计和线性代数等。这些算法在科学计算、工程应用和数据分析等领域有着广泛的应用。 3. **编程实践**：Knuth的书中通常会深入讨论算法的效率、可读性和可维护性，这些都是编写高质量代码的关键要素。他强调代码的清晰性和文档的重要性，对编程风格和习惯有独到见解。 4. **算法分析**：书中可能包含对各种算法的时间复杂度和空间复杂度的分析，帮助读者理解算法的性能并做出合理的选择。 5. **计算机科学理论**：除了实际编程技巧，这本书也可能涵盖一些理论概念，如图论、组合优化和计算复杂性理论，这些理论为理解和解决问题提供了坚实的数学基础。 6. **编程语言**：尽管没有直接提及，但作为一本关于编程的权威著作，它很可能讨论了多种编程语言，特别是那些适合实现复杂算法的语言，如C、Lisp或Fortran。《计算机程序设计艺术》是一本对计算机科学家和工程师来说极其宝贵的资源，它不仅提供了丰富的算法实例和深入的理论解释，还提倡了一种追求卓越编程的哲学。其严谨的学术态度和实用性的结合，使得这本书成为程序员和计算机科学教育者的必备参考书籍。

RANDOM NUMBERS

3.1

Several people experimented with the middle-square method in the early

1950s. Working with numbers that have four digits instead of ten, G. E. Forsythe

tried 16 different starting values and found that 12 of them led to sequences

ending with the cycle 6100, 2100, 4100, 8100, 6100, . . . , while two of them

degenerated to zero. N. Metropolis also conducted extensive tests on the middle-

square method, mostly in the binary number system. He showed that when 20-

bit numbers are being used, there are 13 different cycles into which the sequence

might degenerate, the longest of which has a period of length 142.

It is fairly easy to restart the middle-square method on a new value when

zero has been detected, but long cycles are somewhat harder to avoid. Exercise 7

discusses some interesting ways to determine the cycles of periodic sequences,

using very little memory space.

A theoretical disadvantage of the middle-square method is given in exercises

9 and 10. On the other hand, working with 38-bit numbers, Metropolis obtained a

sequence of about 750,000 numbers before degeneracy occurred, and the resulting

750,000

38 bits satisfactorily passed statistical tests for randomness. This

shows that the middle-square method can give usable results, but it is rather

dangerous to put much faith in it until after elaborate computations have been

performed.

Many random number generators in use today are not very good. There is

a tendency for people to avoid learning anything about such subroutines; quite

often we find that some old method that is comparatively unsatisfactory has

blindly been passed down from one programmer to another, and today’s users

have no understanding of its limitations. We shall see in this chapter that it is

not difficult to learn the most important facts about random number generators

and their proper use.

It is not easy to invent a foolproof source of random numbers. This fact was

convincingly impressed upon the author several years ago, when he attempted

to create a fantastically good generator using the following peculiar approach:

Algorithm K (“Super-random” number generator). Given a lo-digit decimal

number X, this algorithm may be used to change X to the number that should

come next in a supposedly random sequence. Although the algorithm might be

expected to yield quite a random sequence, reasons given below show that it

is, in fact, not very good at all. (The reader need not study this algorithm in

great detail except to observe how complicated it is; note, in particular, steps

Kl and K2.)

Kl. [Choose number of iterations.] Set Y t [X/lOgl , the most significant

digit of X. (We will execute steps K2 through K13 exactly Y + 1 times;

that is, we will apply randomizing transformations a random number of

times.)

K2. [Choose random step.] Set 2 e lX/108j mod 10, the second most signifi-

cant digit of X. Go to step K(3 + 2). (That is, we now jump to a random

step in the program.)

K3. [Ensure 2 5 x lo’.] If X < 5000000000, set X c X + 5000000000.

3.1

INTRODUCTION

device. A famous random-number machine called ERNIE has been used to pick

the winning numbers in the British Premium Savings Bonds lottery. [See the

articles by Kendall and Babington-Smith in J. Royal Stat. Sot., Series A,

101

(1938), 147-166, and Series B, 6 (1939), 51-61; see also the review of the RAND

table in Math. Comp. 10 (1956), 39-43, and the discussion of ERNIE by W. E.

Thomson et al., J. Royal Stat. Sot., Series A, 122 (1959), 301-333.1

Shortly after computers were introduced, people began to search for efficient

ways to obtain random numbers within computer programs. A table can be used,

but this method is of limited utility because of the memory space and input time

requirement, because the table may be too short, and because it is a bit of a

nuisance to prepare and maintain the table. Machines such as ERNIE might

be attached to the computer, but this would be unsatisfactory since it would be

impractical to reproduce calculations exactly a second time when checking out

a program; and such machines have tended to suffer from malfunctions that are

difficult to detect.

The inadequacy of these methods led to an interest in the production of

random numbers using the arithmetic operations of a computer. John von

Neumann first suggested this approach in about 1946, using the “middle-square”

method. His idea was to take the square of the previous random number and

to extract the middle digits; for example, if we are generating lo-digit numbers

and the previous value was 5772156649, we square it to get

33317792380594909201,

and the next number is therefore 7923805949.

There is a fairly obvious objection to this technique: how can a sequence

generated in such a way be random, since each number is completely determined

by its predecessor? The answer is that this sequence isn’t random, but it appears

to be. In typical applications the actual relationship between one number and

its successor has no physical significance; hence the nonrandom character is

not really undesirable. Intuitively, the middle square seems to be a fairly good

scrambling of the previous number.

Sequences generated in a deterministic way such as this are usually called

pseudo-random or quasi-random sequences in the highbrow technical literature,

but in this book we shall simply call them random sequences, with the under-

standing that they only appear to be random. Being “apparently random” is

perhaps all that can be said about any random sequence anyway. Random

numbers generated deterministically on computers have worked quite well in

nearly every application, provided that a suitable method has been carefully

selected. Of course, deterministic sequences aren’t always the answer; they cer-

tainly shouldn’t replace ERNIE for the lotteries.

Von Neumann’s original “middle-square method” has actually proved to be a

comparatively poor source of random numbers. The danger is that the sequence

tends to get into a rut, a short cycle of repeating elements. For example, if zero

ever appears as a number of the sequence, it will continually perpetuate itself.

RANDOM NUMBERS

3.1

e) Decision making. There are reports that many executives make their deci-

sions by flipping a coin or by throwing darts, etc. It is also rumored that some

college professors prepare their grades on such a basis. Sometimes it is impor-

tant to make a completely “unbiased” decision; this ability is occasionally useful

in computer algorithms, for example in situations where a fixed decision made

each time would cause the algorithm to run more slowly. Randomness is also an

essential part of optimal strategies in the theory of games.

f) Recreation. Rolling dice, shuffling decks of cards, spinning roulette wheels,

etc., are fascinating pastimes for just about everybody. These traditional uses

of random numbers have suggested the name “Monte Carlo method,” a general

term used to describe any algorithm that employs random numbers.

People who think about this topic almost invariably get into philosophical

discussions about what the word “random” means. In a sense, there is no such

thing as a random number; for example, is 2 a random number? Rather, we speak

of a sequence of independent random numbers with a specified distribution, and

this means loosely that each number was obtained merely by chance, having

nothing to do with other numbers of the sequence, and that each number has a

specified probability of falling in any given range of values.

A uniform distribution on a finite set of numbers is one in which each possible

number is equally probable. A distribution is generally understood to be uniform

unless some other distribution is specifically mentioned.

Each of the ten digits 0 through 9 will occur about & of the time in a

(uniform) sequence of random digits. Each pair of two successive digits should

occur about & of the time, etc. Yet if we take a truly random sequence of a

million digits, it will not always have exactly 100,000 zeros, 100,000 ones, etc. In

fact, chances of this are quite slim; a sequence of such sequences will have this

character on the average.

Any specified sequence of a million digits is equally as probable as the

sequence consisting of a million zeros. Thus, if we are choosing a million digits at

random and if the first 999,999 of them happen to come out to be zero, the chance

that the final digit is zero is still exactly &, in a truly random situation. These

statements seem paradoxical to many people, but there is really no contradiction

involved.

There are several ways to formulate decent abstract definitions of random-

ness, and we will return to this interesting subject in Section 3.5; but for the

moment, let us content ourselves with an intuitive understanding of the concept.

At first, people who needed random numbers in their scientific work would

draw balls out of a “well-stirred urn” or would roll dice or deal out cards. A

table of over 40,000 random digits, “taken at random from census reports,” was

published in 1927 by L. H. C. Tippett. Since then, a number of devices have

been built to generate random numbers mechanically; the first such machine was

used in 1939 by M. G. Kendall and B. Babington-Smith to produce a table of

100,000 random digits, and in 1955 the RAND Corporation published a widely

used table of a million random digits obtained with the help of another special

3.1

INTRODUCTION

K4. [Middle square.] Replace X by lX2/105] mod lOlo, i.e., by the middle of

the square of X.

K5. [Multiply.] Replace X by (1001001001 X) mod lOlo.

K6. [Pseudo-complement.] If X < 100000000, then set X +- X + 9814055677;

otherwise set X +- lOlo - X.

K7. [Interchange halves.] Interchange the low-order five digits of X with the

high-order five digits, i.e., X +- 105(X mod 105) + lX/105], the middle 10

digits of (lOlo + 1)X.

K8. [Multiply.] Same as step K5.

K9. [Decrease digits.] Decrease each nonzero digit of the decimal representation

of X by one.

K10.

[99999 modify.] If X < 105, set X c X2 + 99999; otherwise set X t

x - 99999.

Kll.

[Normalize.] (At this point X cannot be zero.) If X < log, set X + 10X

and repeat this step.

K12. [Modified middle square.] Replace X by 1X(X - 1)/105] mod lOlo, i.e., by

the middle 10 digits of X(X - 1).

K13. [Repeat?] If Y > 0, decrease Y by 1 and return to step K2. If Y = 0, the

algorithm terminates with X as the desired “random” value. I

(The machine-language program corresponding to the above algorithm was in-

tended to be so complicated that a person reading a listing of it without ex-

planatory comments wouldn’t know what the program was doing.)

Considering all the contortions of Algorithm K, doesn’t it seem plausible

that it should produce almost an infinite supply of unbelievably random num-

bers? No! In fact, when this algorithm was first put onto a computer, it almost

immediately converged to the lO-digit value 6065038420, which-by extraordi-

nary coincidence-is transformed into itself by the algorithm (see Table 1). With

another starting number, the sequence began to repeat after 7401 values, in a

cyclic period of length 3178.

The moral of this story is that random numbers should not be generated

with a method chosen at random. Some theory should be used.

In this chapter, we shall consider random number generators that are su-

perior to the middle-square method and to Algorithm K; the corresponding se-

quences are guaranteed to have certain desirable random properties, and no

degeneracy will occur. We shall explore the reasons for this random behavior

in some detail, and we shall also consider techniques for manipulating random

numbers. For example, one of our investigations will be the shuffling of a simu-

lated deck of cards within a computer program.

Section 3.6 summarizes this chapter and lists several bibliographic sources.

6 RANDOM NUMBERS

3.1

Table 1

A COLOSSAL COINCIDENCE: THE NUMBER 6065038420

IS TRANSFORMED INTO ITSELF BY ALGORITHM K.

Step

KlO

Kll

K12

KlO

Kll

K12

EXERCISES

X (after)

6065038420

6910360760

8031120760

1968879240

7924019688

9631707688

8520606577

8520506578

0323372207

9676627793

2779396766

4942162766

3831051655

3830951656

1905867781

3319967479

6680032521

3252166800

2218966800

Y=6

Y=5

Y=4

Step

KlO

Kll

K12

KlO

Kll

K12

Kll

K12

KlO

Kll

K12

X (after)

1107855700

1107755701

1226919902

0048821902

9862877579

7757998628

2384626628

1273515517

1273415518

5870802097

3172562687

1540029446

7015475446

2984524554

2455429845

2730274845

1620163734

1620063735

6065038420

b 1. [ZV] Suppose that you wish to obtain a decimal digit at random, not using a

computer. Which of the following methods would be suitable?

a) Open a telephone directory to a random place (i.e., stick your finger in it some-

where) and use the units digit of the first number found on the selected page.

b) Same as (a), but use the units digit of the page number.

c) Roll a die that is in the shape of a regular icosahedron, whose twenty faces have

been labeled with the digits 0, 0, 1, 1, . . . , 9,9. Use the digit that appears on top,

when the die comes to rest. (A felt table with a hard surface is recommended for

rolling dice.)

d) Expose a geiger counter to a source of radioactivity for one minute (shielding

yourself) and use the units digit of the resulting count. Assume that the geiger

counter displays the number of counts in decimal notation, and that the count is

initially zero.

e) Glance at your wristwatch; and if the position of the second-hand is between 6n

and 6(n + 1) seconds, choose the digit n.

f) Ask a friend to think of a random digit, and use the digit he names.

g) Ask an enemy to think of a random digit, and use the digit he names.

剩余703页未读，继续阅读

zhangwenhuan

粉丝: 1
资源: 128

Donald Knuth的《计算机程序设计艺术》第二版

[计算机科学经典著作].Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.1.pdf

Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.1

[Donald_E._Knuth]_The_Art_of_Computer_Programming epub版本 英文4册全

Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.3.7z.001

Addison.Wesley.Donald.E.Knuth.The.Art.of.Computer.Programming.Volume.3.7z.002

The.Art.of.Computer.Programming.Volume.1.Fascicle.1.MMIX.2004.Donald_Knuth

The.Art.Of.Computer.Programming.3rd.ed.Vol1.-.Donald.Knuth

The.Art.Of.Computer.Programming.2nd.ed.Vol3.-.Donald.Knuth

Selected.Papers.on.Discrete.Mathematics__D.E.Knuth.pdf

donald e. knuth - the art of computer programming volume2.part1

最新资源

[Donald_E._Knuth]_The_Art_of_Computer_Programming epub版本英文4册全