浮点运算详解：每个计算机科学家必知

需积分: 10 197 浏览量更新于2024-07-27 收藏 307KB PDF 举报

"这篇文档是David Goldberg的文章'What Every Computer Scientist Should Know About Floating Point Arithmetic'的编辑重印版，最初发表在1991年3月的'Computing Surveys'期刊上。本文深入探讨了浮点计算的重要性、误差、标准、系统方面以及详细细节，旨在让计算机科学家了解浮点运算的方方面面。" 浮点运算算法是计算机科学中的一个核心概念，虽然对许多人来说可能显得深奥，但其实际应用却无处不在。浮点数据类型存在于几乎所有的编程语言中，从个人电脑到超级计算机都配备了浮点加速器，编译器经常需要编译包含浮点算法的代码，而且操作系统必须处理如溢出等浮点异常情况。文章首先介绍了浮点运算的基本概念，包括浮点表示的近似性和由此产生的舍入误差。由于浮点数无法精确表示所有实数，因此在进行浮点运算时会引入误差。这些误差源于将无限精度的数学真实值转化为有限的二进制表示。舍入策略（如最接近原则）是控制这种误差的关键，而理解这些误差对于分析算法的精度和性能至关重要。接着，文章详细讨论了 IEEE 754 浮点计算标准，这是定义浮点数值表示和运算行为的国际标准。该标准涵盖了单精度和双精度浮点格式，以及特殊值（如无穷大和NaN）的处理。理解这个标准对于编写高效且可靠的跨平台浮点代码是必要的。文章进一步阐述了浮点运算的系统层面考虑，如硬件实现、内存管理、以及不同架构下的兼容性问题。此外，它还深入到浮点运算的详细细节，包括运算顺序、精度损失和性能优化。最后，文章提供了一个总结，回顾了浮点计算的主要挑战和解决策略，并感谢了对此领域做出贡献的学者。参考文献则为读者提供了进一步学习的资源。这篇文章是理解和掌握浮点运算基础知识的重要参考资料，对于任何从事计算科学、软件开发或系统设计的人来说，都是不可或缺的知识库。

What Every Computer Scientist Should Know About Floating Point Arithmetic 165

Theorem 3

The rounding error incurred when using (7) to compute the area of a triangle is at

most 11ε, provided that subtraction is performed with a guard digit, e ≤ .005, and

that square roots are computed to within 1/2 ulp.

The condition that e < .005 is met in virtually every actual ﬂoating-point

system. For example when β = 2, p ≥ 8 ensures that e < .005, and when β = 10,

p ≥ 3 is enough.

In statements like Theorem 3 that discuss the relative error of an expression, it

is understood that the expression is computed using ﬂoating-point arithmetic.

In particular, the relative error is actually of the expression

SQRT((a ⊕ (b ⊕ c)) ⊗ (c (a b)) ⊗ (c ⊕ (a b)) ⊗ (a ⊕ (b c))) 4 (8)

Because of the cumbersome nature of (8), in the statement of theorems we will

usually say the computed value of E rather than writing out E with circle

notation.

Error bounds are usually too pessimistic. In the numerical example given

above, the computed value of (7) is 2.35, compared with a true value of 2.34216

for a relative error of 0.7ε, which is much less than 11ε. The main reason for

computing error bounds is not to get precise bounds but rather to verify that

the formula does not contain numerical problems.

A ﬁnal example of an expression that can be rewritten to use benign

cancellation is (1 + x)

, where . This expression arises in ﬁnancial

calculations. Consider depositing $100 every day into a bank account that

earns an annual interest rate of 6%, compounded daily. If n = 365 and i = .06,

the amount of money accumulated at the end of one year is 100

dollars. If this is computed using β = 2 and p = 24, the result is $37615.45

compared to the exact answer of $37614.05, a discrepancy of $1.40. The reason

for the problem is easy to see. The expression 1 + i/n involves adding 1 to

.0001643836, so the low order bits of i/n are lost. This rounding error is

ampliﬁed when 1 + i/n is raised to the nth power.

x 1«

1 in⁄+()

–

in⁄

--------------------------------

What Every Computer Scientist Should Know About Floating Point Arithmetic 167

accurately? There is; namely = (1 ⊕ x) 1, because then 1 + is exactly

equal to 1 ⊕ x.

The results of this section can be summarized by saying that a guard digit

guarantees accuracy when nearby precisely known quantities are subtracted

(benign cancellation). Sometimes a formula that gives inaccurate results can be

rewritten to have much higher numerical accuracy by using benign

cancellation; however, the procedure only works if subtraction is performed

using a guard digit. The price of a guard digit is not high, because it merely

requires making the adder one bit wider. For a 54 bit double precision adder,

the additional cost is less than 2%. For this price, you gain the ability to run

many algorithms such as the formula (6) for computing the area of a triangle

and the expression ln(1 + x). Although most modern computers have a guard

digit, there are a few (such as Cray

systems) that do not.

Exactly Rounded Operations

When ﬂoating-point operations are done with a guard digit, they are not as

accurate as if they were computed exactly then rounded to the nearest ﬂoating-

point number. Operations performed in this manner will be called exactly

rounded.

The example immediately preceding Theorem 2 shows that a single

guard digit will not always give exactly rounded results. The previous section

gave several examples of algorithms that require a guard digit in order to work

properly. This section gives examples of algorithms that require exact

rounding.

So far, the deﬁnition of rounding has not been given. Rounding is

straightforward, with the exception of how to round halfway cases; for

example, should 12.5 round to 12 or 13? One school of thought divides the 10

digits in half, letting {0, 1, 2, 3, 4} round down, and {5, 6, 7, 8, 9} round up; thus

12.5 would round to 13. This is how rounding works on Digital Equipment

Corporation’s VAX™ computers. Another school of thought says that since

numbers ending in 5 are halfway between two possible roundings, they should

round down half the time and round up the other half. One way of obtaining

this 50% behavior to require that the rounded result have its least signiﬁcant

1. Also commonly referred to as correctly rounded. -- Ed.

168 Numerical Computation Guide

digit be even. Thus 12.5 rounds to 12 rather than 13 because 2 is even. Which of

these methods is best, round up or round to even? Reiser and Knuth [1975]

offer the following reason for preferring round to even.

Theorem 5

Let x and y be ﬂoating-point numbers, and deﬁne x

= x, x

= (x

y) ⊕ y, …,

= (x

n-1

y) ⊕ y. If ⊕ and are exactly rounded using round to even, then

either x

= x for all n or x

= x

for all n ≥ 1. ❚

To clarify this result, consider β = 10, p = 3 and let x = 1.00, y = -.555. When

rounding up, the sequence becomes x

y = 1.56, x

= 1.56 .555 = 1.01,

y = 1.01 ⊕ .555 = 1.57, and each successive value of x

increases by .01,

until x

= 9.45 (n ≤ 845)

. Under round to even, x

is always 1.00. This example

suggests that when using the round up rule, computations can gradually drift

upward, whereas when using round to even the theorem says this cannot

happen. Throughout the rest of this paper, round to even will be used.

One application of exact rounding occurs in multiple precision arithmetic.

There are two basic approaches to higher precision. One approach represents

ﬂoating-point numbers using a very large signiﬁcand, which is stored in an

array of words, and codes the routines for manipulating these numbers in

assembly language. The second approach represents higher precision ﬂoating-

point numbers as an array of ordinary ﬂoating-point numbers, where adding

the elements of the array in inﬁnite precision recovers the high precision

ﬂoating-point number. It is this second approach that will be discussed here.

The advantage of using an array of ﬂoating-point numbers is that it can be

coded portably in a high level language, but it requires exactly rounded

arithmetic.

The key to multiplication in this system is representing a product xy as a sum,

where each summand has the same precision as x and y. This can be done by

splitting x and y. Writing x = x

+ x

and y = y

+ y

, the exact product is xy =

+ x

. If x and y have p bit signiﬁcands, the summands will

also have p bit signiﬁcands provided that x

, x

, y

can be represented using

p/2 bits. When p is even, it is easy to ﬁnd a splitting. The number

… x

p - 1

can be written as the sum of x

… x

p/2 - 1

and

0.0 … 0x

p/2

… x

p -1

. When p is odd, this simple splitting method won’t work.

1. When n = 845, x

= 9.45, x

+ 0.555 = 10.0, and 10.0 - 0.555 = 9.45. Therefore, x

= x

845

for n > 845.

剩余77页未读，继续阅读

benchfox

粉丝: 0
资源: 1

浮点运算详解：每个计算机科学家必知

浮点数计算：计算机科学家必知

计算机科学家必知：David Goldberg论浮点运算设计

浮点数运算解析

What Every Computer Scientist Should Know About Floating-Point Arithmetic

What Every Engineer Should Know About Excel(2nd) epub

计算机科学家必知浮点数运算要点

知攻善防-应急响应靶机-web2.z18

知攻善防-应急响应靶机-web2.z09

白色简洁风格的影视众筹平台整站网站源码下载.zip

HTTP请求流程深入解析与性能优化技术指南

最新资源