《计算机程序设计艺术》第二卷：深入数值算法

需积分: 10 71 浏览量更新于2024-07-30 收藏 43.37MB PDF 举报

"计算机程序设计艺术第二卷 - Donald E. Knuth" 《计算机程序设计艺术》是计算机科学领域的经典之作，由斯坦福大学的Donald E. Knuth教授撰写。这本书是程序设计者必读的权威文献，尤其对于计算机专业的学生而言，它构成了扎实的基础知识体系。虽然书中涉及的数学概念较为深入，需要读者具备一定的数学功底，但一旦掌握，将极大地提升编程技能和算法理解。本书的第二卷——《Seminumerical Algorithms》（半数值算法）主要聚焦于与数值计算相关的编程技术。在这一卷中，Knuth教授深入探讨了各种计算方法，包括但不限于： 1. **随机数生成**：讨论了如何生成高质量的伪随机数序列，这对于模拟和统计分析至关重要。 2. **排序与搜索算法**：详尽阐述了快速排序、归并排序、二分查找等经典算法，这些算法在实际编程中广泛使用。 3. **数值分析**：涵盖了浮点数表示、误差分析、近似计算等内容，帮助程序员理解和处理数值计算中的精度问题。 4. **数据压缩**：介绍了哈夫曼编码和游程编码等数据压缩技术，这些技术在信息传输和存储中扮演着重要角色。 5. **数值方程求解**：讲解了线性代数中的矩阵运算、特征值求解以及非线性方程组的数值解法。 6. **傅里叶变换**：探讨了离散傅里叶变换（DFT）及其快速算法FFT，它们在信号处理和图像分析等领域有广泛应用。 7. **概率和统计**：介绍了概率论的基础知识以及统计推断的算法，为数据分析和机器学习提供了理论基础。书中的内容不仅限于算法的描述，还包含了大量实例和习题，旨在帮助读者巩固理解和实践应用。此外，Knuth的写作风格严谨且富有启发性，他强调代码的清晰性和效率，提倡编程艺术，这对任何想要提升编程技巧的人来说都是宝贵的学习资源。《计算机程序设计艺术》第二卷是一本深度和广度兼备的教材，它不仅是学习高级算法的宝典，也是提升编程思维和解决问题能力的良师益友。尽管挑战性较大，但投入的时间和精力无疑将转化为编程生涯中的宝贵财富。

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页未读，继续阅读

flywing_ly

粉丝: 0
资源: 9

《计算机程序设计艺术》第二卷：深入数值算法

计算机程序设计艺术（第二卷）.pdf

计算机程序设计艺术第二卷1

计算机程序设计艺术第二卷2

计算机程序设计艺术第二卷第三版英文版

D.E.Knuth(高德纳)著，计算机程序设计艺术第二卷,英文原版，epub

计算机程序设计艺术第二卷：数学与密码学精华

计算机程序设计艺术（第二卷）

计算机程序设计艺术第一卷

计算机程序设计艺术 第三卷

计算机程序设计艺术第四卷

最新资源

计算机程序设计艺术第三卷