Trăn trừ nhị phân

Số học dấu phẩy động được coi là một chủ đề bí truyền của nhiều người. Điều này khá ngạc nhiên vì dấu chấm động phổ biến trong các hệ thống máy tính. Hầu hết mọi ngôn ngữ đều có kiểu dữ liệu dấu chấm động; . Bài báo này trình bày một hướng dẫn về các khía cạnh của dấu phẩy động có tác động trực tiếp đến các nhà thiết kế hệ thống máy tính. Nó bắt đầu với thông tin cơ bản về biểu diễn dấu phẩy động và lỗi làm tròn, tiếp tục với phần thảo luận về tiêu chuẩn dấu phẩy động IEEE và kết thúc bằng nhiều ví dụ về cách các nhà chế tạo máy tính có thể hỗ trợ dấu phẩy động tốt hơn.

Danh mục và mô tả chủ đề. (Chính) C. 0 [Computer Systems Organization]. General -- instruction set design; D. 3. 4 [Programming Languages]. Processors -- compilers, optimization; G. 1. 0 [Numerical Analysis]. General -- computer arithmetic, error analysis, numerical algorithms (Secondary)

D. 2. 1 [Software Engineering]. Requirements/Specifications -- languages; D. 3. 4 Programming Languages]. Formal Definitions and Theory -- semantics; D. 4. 1 Operating Systems]. Quản lý quy trình -- đồng bộ hóa

General Terms. Algorithms, Design, Languages

Additional Key Words and Phrases. Denormalized number, exception, floating-point, floating-point standard, gradual underflow, guard digit, NaN, overflow, relative error, rounding error, rounding mode, ulp, underflow

Introduction

Builders of computer systems often need information about floating-point arithmetic. Tuy nhiên, có rất ít nguồn thông tin chi tiết về nó. Một trong số ít cuốn sách về chủ đề này, Tính toán dấu phẩy động của Pat Sterbenz, đã hết bản in từ lâu. Bài viết này là một hướng dẫn về các khía cạnh của số học dấu phẩy động (dấu phẩy động sau đây) có kết nối trực tiếp với việc xây dựng hệ thống. Nó bao gồm ba phần kết nối lỏng lẻo. Phần đầu tiên, Lỗi làm tròn, thảo luận về ý nghĩa của việc sử dụng các chiến lược làm tròn khác nhau cho các phép tính cơ bản cộng, trừ, nhân và chia. It also contains background information on the two methods of measuring rounding error, ulps and

     n = n/2

     n = n/2

I have tried to avoid making statements about floating-point without also giving reasons why the statements are true, especially since the justifications involve nothing more complicated than elementary calculus. Those explanations that are not central to the main argument have been grouped into a section called "The Details," so that they can be skipped if desired. In particular, the proofs of many of the theorems appear in this section. The end of each proof is marked with the z symbol. When a proof is not included, the z appears immediately following the statement of the theorem

Rounding Error

Squeezing infinitely many real numbers into a finite number of bits requires an approximate representation. Although there are infinitely many integers, in most programs the result of integer computations can be stored in 32 bits. In contrast, given any fixed number of bits, most calculations with real numbers will produce quantities that cannot be exactly represented using that many bits. Therefore the result of a floating-point calculation must often be rounded in order to fit back into its finite representation. This rounding error is the characteristic feature of floating-point computation. The section Relative Error and Ulps describes how it is measured

Since most floating-point calculations have rounding error anyway, does it matter if the basic arithmetic operations introduce a little bit more rounding error than necessary? That question is a main theme throughout this section. The section Guard Digits discusses guard digits, a means of reducing the error when subtracting two nearby numbers. Guard digits were considered sufficiently important by IBM that in 1968 it added a guard digit to the double precision format in the System/360 architecture (single precision already had a guard digit), and retrofitted all existing machines in the field. Two examples are given to illustrate the utility of guard digits

The IEEE standard goes further than just requiring the use of a guard digit. It gives an algorithm for addition, subtraction, multiplication, division and square root, and requires that implementations produce the same result as that algorithm. Thus, when a program is moved from one machine to another, the results of the basic operations will be the same in every bit if both machines support the IEEE standard. This greatly simplifies the porting of programs. Other uses of this precise specification are given in Exactly Rounded Operations

Floating-point Formats

Several different representations of real numbers have been proposed, but by far the most widely used is the floating-point representation. 1 Floating-point representations have a base

In general, a floating-point number will be represented as ± d. dd. d ×

The term floating-point number will be used to mean a real number that can be exactly represented in the format under discussion. Two other parameters associated with floating-point representations are the largest and smallest allowable exponents, emax and emin. Since there are

bits, where the final +1 is for the sign bit. The precise encoding is not important for now

There are two reasons why a real number might not be exactly representable as a floating-point number. The most common situation is illustrated by the decimal number 0. 1. Although it has a finite decimal representation, in binary it has an infinite repeating representation. Thus when

Floating-point representations are not necessarily unique. For example, both 0. 01 × 101 and 1. 00 × 10-1 represent 0. 1. If the leading digit is nonzero (d0

Note that the × in a floating-point number is part of the notation, and different from a floating-point multiply operation. The meaning of the × symbol should be clear from the context. For example, the expression (2. 5 × 10-3) × (4. 0 × 102) involves only a single floating-point multiplication

Relative Error and Ulps

Since rounding error is inherent in floating-point computation, it is important to have a way to measure this error. Consider the floating-point format with

Để tính toán lỗi tương đối tương ứng với. 5 ulp, observe that when a real number is approximated by the closest possible floating-point number d. dd. dd ×

Đặc biệt, lỗi tương đối tương ứng với. 5 ulp có thể thay đổi theo hệ số

Trong ví dụ trên, lỗi tương đối là. 00159/3. 14159

Để minh họa sự khác biệt giữa ulps và lỗi tương đối, hãy xem xét số thực x = 12. 35. Nó được xấp xỉ bởi = 1. 24 × 101. lỗi là 0. 5 ulps, lỗi tương đối là 0. 8

The most natural way to measure rounding error is in ulps. For example rounding to the nearest floating-point number corresponds to an error of less than or equal to . 5 ulp. However, when analyzing the rounding error caused by various formulas, relative error is a better measure. A good illustration of this is the analysis in the section Theorem 9. Vì

When only the order of magnitude of rounding error is of interest, ulps and

Guard Digits

One method of computing the difference between two floating-point numbers is to compute the difference exactly and then round it to the nearest floating-point number. This is very expensive if the operands differ greatly in size. Assuming p = 3, 2. 15 × 1012 - 1. 25 × 10-5 would be calculated as

which rounds to 2. 15 × 1012. Rather than using all these digits, floating-point hardware normally operates on a fixed number of digits. Suppose that the number of digits kept is p, and that when the smaller operand is shifted right, digits are simply discarded (as opposed to rounding). Then 2. 15 × 1012 - 1. 25 × 10-5 becomes

The answer is exactly the same as if the difference had been computed exactly and then rounded. Take another example. 10. 1 - 9. 93. This becomes

The correct answer is . 17, so the computed difference is off by 30 ulps and is wrong in every digit. How bad can the error be?

Theorem 1

Proof

When

và câu trả lời là chính xác. Với một chữ số bảo vệ, sai số tương đối của kết quả có thể lớn hơn

This rounds to 102, compared with the correct answer of 101. 41, for a relative error of . 006, which is greater than

Theorem 2

This theorem will be proven in Rounding Error. Addition is included in the above theorem since x and y can be positive or negative

Cancellation

The last section can be summarized by saying that without a guard digit, the relative error committed when subtracting two nearby quantities can be very large. In other words, the evaluation of any expression containing a subtraction (or an addition of quantities with opposite signs) could result in a relative error so large that all the digits are meaningless (Theorem 1). When subtracting nearby quantities, the most significant digits in the operands match and cancel each other. There are two kinds of cancellation. catastrophic and benign

Catastrophic cancellation occurs when the operands are subject to rounding errors. For example in the quadratic formula, the expression b2 - 4ac occurs. The quantities b2 and 4ac are subject to rounding errors since they are the results of floating-point multiplications. Suppose that they are rounded to the nearest floating-point number, and so are accurate to within . 5 ulp. When they are subtracted, cancellation can cause many of the accurate digits to disappear, leaving behind mainly digits contaminated by rounding error. Hence the difference might have an error of many ulps. For example, consider b = 3. 34, a = 1. 22, and c = 2. 28. Giá trị chính xác của b2 - 4ac là. 0292. But b2 rounds to 11. 2 và 4ac làm tròn thành 11. 1, do đó câu trả lời cuối cùng là. 1 which is an error by 70 ulps, even though 11. 2 - 11. 1 is exactly equal to . 16. The subtraction did not introduce any error, but rather exposed the error introduced in the earlier multiplications

Benign cancellation occurs when subtracting exactly known quantities. If x and y have no rounding error, then by Theorem 2 if the subtraction is done with a guard digit, the difference x-y has a very small relative error (less than 2

A formula that exhibits catastrophic cancellation can sometimes be rearranged to eliminate the problem. Again consider the quadratic formula

When, thendoes not involve a cancellation and

But the other addition (subtraction) in one of the formulas will have a catastrophic cancellation. To avoid this, multiply the numerator and denominator of r1 by

(and similarly for r2) to obtain

Ifand, then computing r1 using formula (4) will involve a cancellation. Therefore, use formula (5) for computing r1 and (4) for r2. On the other hand, if b < 0, use (4) for computing r1 and (5) for r2.

The expression x2 - y2 is another formula that exhibits catastrophic cancellation. It is more accurate to evaluate it as (x - y)(x + y). 7 Unlike the quadratic formula, this improved form still has a subtraction, but it is a benign cancellation of quantities without rounding error, not a catastrophic one. By Theorem 2, the relative error in x - y is at most 2

In order to avoid confusion between exact and computed values, the following notation is used. Whereas x - y denotes the exact difference of x and y, xy denotes the computed difference (i. e. , with rounding error). Similarly

     n = n/2

     n = n/2

Although (xy)

The expression x2 - y2 is more accurate when rewritten as (x - y)(x + y) because a catastrophic cancellation is replaced with a benign one. We next present more interesting examples of formulas exhibiting catastrophic cancellation that can be rewritten to exhibit only benign cancellation

The area of a triangle can be expressed directly in terms of the lengths of its sides a, b, and c as

(Suppose the triangle is very flat; that is, a

There is a way to rewrite formula (6) so that it will return accurate results even for flat triangles [Kahan 1986]. It is

If a, b, and c do not satisfy a

Although formula (7) is much more accurate than (6) for this example, it would be nice to know how well (7) performs in general

Theorem 3

The condition that e < . 005 được đáp ứng trong hầu hết mọi hệ thống dấu phẩy động thực tế. Ví dụ: khi

In statements like Theorem 3 that discuss the relative error of an expression, it is understood that the expression is computed using floating-point arithmetic. In particular, the relative error is actually of the expression

     n = n/2

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

A final example of an expression that can be rewritten to use benign cancellation is (1 + x)n, where. This expression arises in financial 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

dollars. If this is computed using

The troublesome expression (1 + i/n)n can be rewritten as enln(1 + i/n), where now the problem is to compute ln(1 + x) for small x. One approach is to use the approximation ln(1 + x)

Theorem 4 assumes that

     n = n/2

     n = n/2

Theorem 4

This formula will work for any value of x but is only interesting for, which is where catastrophic cancellation occurs in the naive formula ln(1 + x). Although the formula may seem mysterious, there is a simple explanation for why it works. Write ln(1 + x) as

The left hand factor can be computed exactly, but the right hand factor µ(x) = ln(1 + x)/x will suffer a large rounding error when adding 1 to x. However, µ is almost constant, since ln(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 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 floating-point operations are done with a guard digit, they are not as accurate as if they were computed exactly then rounded to the nearest floating-point number. Operations performed in this manner will be called exactly rounded. 8 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 definition 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 significant 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

Để làm rõ kết quả này, hãy xem xét

and each successive value of xn increases by . 01, until xn = 9. 45 (n

One application of exact rounding occurs in multiple precision arithmetic. There are two basic approaches to higher precision. One approach represents floating-point numbers using a very large significand, 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 floating-point numbers as an array of ordinary floating-point numbers, where adding the elements of the array in infinite precision recovers the high precision floating-point number. It is this second approach that will be discussed here. The advantage of using an array of floating-point numbers is that it can be coded portably in a high level language, but it requires exactly rounded arithmetic

Chìa khóa của phép nhân trong hệ thống này là biểu diễn tích xy dưới dạng tổng, trong đó mỗi phép cộng có cùng độ chính xác với x và y. Điều này có thể được thực hiện bằng cách tách x và y. Viết x = xh + xl và y = yh + yl, tích chính xác là

Nếu x và y có p bit có nghĩa, thì các phép cộng cũng sẽ có p bit có nghĩa với điều kiện là xl, xh, yh, yl có thể được biểu diễn bằng cách sử dụng [p/2] bit. Khi p chẵn, dễ dàng tìm được một phép chia. số x0. x1. xp - 1 có thể được viết dưới dạng tổng của x0. x1. xp/2 - 1 và 0. 0. 0xp/2. xp - 1. Khi p là số lẻ, phương pháp tách đơn giản này sẽ không hoạt động. Tuy nhiên, có thể thu được thêm một bit bằng cách sử dụng các số âm. Ví dụ: nếu

Định lý 6

và mỗi xi có thể biểu diễn bằng cách sử dụng [p/2] bit chính xác

Để xem định lý này hoạt động như thế nào trong một ví dụ, hãy

Ví dụ cuối cùng về làm tròn chính xác, xem xét chia m cho 10. Kết quả là một số dấu phẩy động nói chung sẽ không bằng m/10. Khi

Định lý 7

Proof

The theorem holds true for any base

We are now in a position to answer the question, Does it matter if the basic arithmetic operations introduce a little more rounding error than necessary? The answer is that it does matter, because accurate basic operations enable us to prove that formulas are "correct" in the sense they have a small relative error. The section Cancellation discussed several algorithms that require guard digits to produce correct results in this sense. If the input to those formulas are numbers representing imprecise measurements, however, the bounds of Theorems 3 and 4 become less interesting. The reason is that the benign cancellation x - y can become catastrophic if x and y are only approximations to some measured quantity. But accurate operations are useful even in the face of inexact data, because they enable us to establish exact relationships like those discussed in Theorems 6 and 7. These are useful even if every floating-point variable is only an approximation to some actual value

The IEEE Standard

There are two different IEEE standards for floating-point computation. IEEE 754 is a binary standard that requires

This section provides a tour of the IEEE standard. Each subsection discusses one aspect of the standard and why it was included. Mục đích của bài báo này không phải là để tranh luận rằng tiêu chuẩn IEEE là tiêu chuẩn dấu phẩy động tốt nhất có thể mà là để chấp nhận tiêu chuẩn như đã cho và giới thiệu về việc sử dụng nó. For full details consult the standards themselves [IEEE 1987; Cody et al. 1984]

Formats and Operations

Base

It is clear why IEEE 854 allows

There are several reasons why IEEE 854 requires that if the base is not 10, it must be 2. The section Relative Error and Ulps mentioned one reason. the results of error analyses are much tighter when

Another possible explanation for choosing

In most modern hardware, the performance gained by avoiding a shift for a subset of operands is negligible, and so the small wobble of

IEEE 754 single precision is encoded in 32 bits using 1 bit for the sign, 8 bits for the exponent, and 23 bits for the significand. Tuy nhiên, nó sử dụng một bit ẩn, do đó, ý nghĩa là 24 bit (p = 24), mặc dù nó được mã hóa chỉ bằng 23 bit

Precision

The IEEE standard defines four different precisions. single, double, single-extended, and double-extended. In IEEE 754, single and double precision correspond roughly to what most floating-point hardware provides. Single precision occupies a single 32 bit word, double precision two consecutive 32 bit words. Extended precision is a format that offers at least a little extra precision and exponent range (TABLE D-1)

The IEEE standard only specifies a lower bound on how many extra bits extended precision provides. The minimum allowable double-extended format is sometimes referred to as 80-bit format, even though the table shows it using 79 bits. The reason is that hardware implementations of extended precision normally do not use a hidden bit, and so would use 80 rather than 79 bits. 13

The standard puts the most emphasis on extended precision, making no recommendation concerning double precision, but strongly recommending that Implementations should support the extended format corresponding to the widest basic format supported,

One motivation for extended precision comes from calculators, which will often display 10 digits, but use 13 digits internally. By displaying only 10 of the 13 digits, the calculator appears to the user as a "black box" that computes exponentials, cosines, etc. to 10 digits of accuracy. Để máy tính tính toán các hàm như exp, log và cos trong phạm vi 10 chữ số với hiệu quả hợp lý, nó cần thêm một vài chữ số để hoạt động với. It is not hard to find a simple rational expression that approximates log with an error of 500 units in the last place. Thus computing with 13 digits gives an answer correct to 10 digits. By keeping these extra 3 digits hidden, the calculator presents a simple model to the operator

Độ chính xác mở rộng trong tiêu chuẩn IEEE phục vụ chức năng tương tự. Nó cho phép các thư viện tính toán số lượng một cách hiệu quả trong khoảng. 5 ulp với độ chính xác đơn (hoặc kép), cung cấp cho người dùng các thư viện đó một mô hình đơn giản, cụ thể là mỗi thao tác nguyên thủy, có thể là một phép nhân đơn giản hoặc một lệnh gọi nhật ký, trả về một giá trị chính xác trong khoảng. 5 lần. Tuy nhiên, khi sử dụng độ chính xác mở rộng, điều quan trọng là đảm bảo rằng việc sử dụng nó minh bạch cho người dùng. For example, on a calculator, if the internal representation of a displayed value is not rounded to the same precision as the display, then the result of further operations will depend on the hidden digits and appear unpredictable to the user

To illustrate extended precision further, consider the problem of converting between IEEE 754 single precision and decimal. Lý tưởng nhất là các số có độ chính xác đơn sẽ được in với đủ chữ số để khi đọc lại số thập phân, số có độ chính xác đơn có thể được phục hồi. Hóa ra 9 chữ số thập phân là đủ để khôi phục một số nhị phân chính xác duy nhất (xem phần Chuyển đổi nhị phân sang thập phân). Khi chuyển đổi một số thập phân trở lại biểu diễn nhị phân duy nhất của nó, một lỗi làm tròn nhỏ tới 1 ulp là nghiêm trọng, vì nó sẽ đưa ra câu trả lời sai. Here is a situation where extended precision is vital for an efficient algorithm. When single-extended is available, a very straightforward method exists for converting a decimal number to a single precision binary one. First read in the 9 decimal digits as an integer N, ignoring the decimal point. From TABLE D-1, p 

If double precision is supported, then the algorithm above would be run in double precision rather than single-extended, but to convert double precision to a 17-digit decimal number and back would require the double-extended format

Exponent

Since the exponent can be positive or negative, some method must be chosen to represent its sign. Two common methods of representing signed numbers are sign/magnitude and two's complement. Dấu hiệu/độ lớn là hệ thống được sử dụng cho dấu hiệu của ý nghĩa và trong các định dạng IEEE. one bit is used to hold the sign, the rest of the bits represent the magnitude of the number. The two's complement representation is often used in integer arithmetic. In this scheme, a number in the range [-2p-1, 2p-1 - 1] is represented by the smallest nonnegative number that is congruent to it modulo 2p

The IEEE binary standard does not use either of these methods to represent the exponent, but instead uses a biased representation. In the case of single precision, where the exponent is stored in 8 bits, the bias is 127 (for double precision it is 1023). What this means is that ifis the value of the exponent bits interpreted as an unsigned integer, then the exponent of the floating-point number is- 127. This is often called the unbiased exponent to distinguish from the biased exponent

Referring to TABLE D-1, single precision has emax = 127 and emin = -126. The reason for having . emin. < emax is so that the reciprocal of the smallest numberwill not overflow. Although it is true that the reciprocal of the largest number will underflow, underflow is usually less serious than overflow. The section Base explained that emin - 1 is used for representing 0, and Special Quantities will introduce a use for emax + 1. In IEEE single precision, this means that the biased exponents range between emin - 1 = -127 and emax + 1 = 128, whereas the unbiased exponents range between 0 and 255, which are exactly the nonnegative numbers that can be represented using 8 bits

Operations

The IEEE standard requires that the result of addition, subtraction, multiplication and division be exactly rounded. That is, the result must be computed exactly and then rounded to the nearest floating-point number (using round to even). The section Guard Digits pointed out that computing the exact difference or sum of two floating-point numbers can be very expensive when their exponents are substantially different. That section introduced guard digits, which provide a practical way of computing differences while guaranteeing that the relative error is small. However, computing with a single guard digit will not always give the same answer as computing the exact result and then rounding. By introducing a second guard digit and a third sticky bit, differences can be computed at only a little more cost than with a single guard digit, but the result is the same as if the difference were computed exactly and then rounded [Goldberg 1990]. Thus the standard can be implemented efficiently

One reason for completely specifying the results of arithmetic operations is to improve the portability of software. When a program is moved between two machines and both support IEEE arithmetic, then if any intermediate result differs, it must be because of software bugs, not from differences in arithmetic. Another advantage of precise specification is that it makes it easier to reason about floating-point. Proofs about floating-point are hard enough, without having to deal with multiple cases arising from multiple kinds of arithmetic. Just as integer programs can be proven to be correct, so can floating-point programs, although what is proven in that case is that the rounding error of the result satisfies certain bounds. Theorem 4 is an example of such a proof. These proofs are made much easier when the operations being reasoned about are precisely specified. Once an algorithm is proven to be correct for IEEE arithmetic, it will work correctly on any machine supporting the IEEE standard

Brown [1981] has proposed axioms for floating-point that include most of the existing floating-point hardware. However, proofs in this system cannot verify the algorithms of sections Cancellation and Exactly Rounded Operations, which require features not present on all hardware. Furthermore, Brown's axioms are more complex than simply defining operations to be performed exactly and then rounded. Thus proving theorems from Brown's axioms is usually more difficult than proving them assuming operations are exactly rounded

There is not complete agreement on what operations a floating-point standard should cover. In addition to the basic operations +, -, × and /, the IEEE standard also specifies that square root, remainder, and conversion between integer and floating-point be correctly rounded. It also requires that conversion between internal formats and decimal be correctly rounded (except for very large numbers). Kulisch and Miranker [1986] have proposed adding inner product to the list of operations that are precisely specified. They note that when inner products are computed in IEEE arithmetic, the final answer can be quite wrong. For example sums are a special case of inner products, and the sum ((2 × 10-30 + 1030) - 1030) - 10-30 is exactly equal to 10-30, but on a machine with IEEE arithmetic the computed result will be -10-30. It is possible to compute inner products to within 1 ulp with less hardware than it takes to implement a fast multiplier [Kirchner and Kulish 1987]. 14 15

All the operations mentioned in the standard are required to be exactly rounded except conversion between decimal and binary. The reason is that efficient algorithms for exactly rounding all the operations are known, except conversion. For conversion, the best known efficient algorithms produce results that are slightly worse than exactly rounded ones [Coonen 1984]

The IEEE standard does not require transcendental functions to be exactly rounded because of the table maker's dilemma. To illustrate, suppose you are making a table of the exponential function to 4 places. Then exp(1. 626) = 5. 0835. Điều này có nên được làm tròn thành 5. 083 or 5. 084? If exp(1. 626) is computed more carefully, it becomes 5. 08350. And then 5. 083500. And then 5. 0835000. Since exp is transcendental, this could go on arbitrarily long before distinguishing whether exp(1. 626) is 5. 083500. 0ddd or 5. 0834999. 9ddd. Thus it is not practical to specify that the precision of transcendental functions be the same as if they were computed to infinite precision and then rounded. Another approach would be to specify transcendental functions algorithmically. But there does not appear to be a single algorithm that works well across all hardware architectures. Rational approximation, CORDIC,16 and large tables are three different techniques that are used for computing transcendentals on contemporary machines. Each is appropriate for a different class of hardware, and at present no single algorithm works acceptably over the wide range of current hardware

Special Quantities

Trên một số phần cứng dấu phẩy động, mọi mẫu bit biểu thị một số dấu phẩy động hợp lệ. The IBM System/370 is an example of this. On the other hand, the VAXTM reserves some bit patterns to represent special numbers called reserved operands. This idea goes back to the CDC 6600, which had bit patterns for the special quantities

     n = n/2

     if (n==0) return u

The IEEE standard continues in this tradition and has NaNs (Not a Number) and infinities. Without any special quantities, there is no good way to handle exceptional situations like taking the square root of a negative number, other than aborting computation. Under IBM System/370 FORTRAN, the default action in response to computing the square root of a negative number like -4 results in the printing of an error message. Since every bit pattern represents a valid number, the return value of square root must be some floating-point number. In the case of System/370 FORTRAN,is returned. In IEEE arithmetic, a NaN is returned in this situation

The IEEE standard specifies the following special values (see TABLE D-2). ± 0, số không chuẩn hóa, ±

NaNs

Traditionally, the computation of 0/0 orhas been treated as an unrecoverable error which causes a computation to halt. However, there are examples where it makes sense for a computation to continue in such a situation. Consider a subroutine that finds the zeros of a function f, say

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

This problem can be avoided by introducing a special value called NaN, and specifying that the computation of expressions like 0/0 andproduce NaN, rather than halting. A list of some of the situations that can cause a NaN are given in TABLE D-3. Then when

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     if (n==0) return u

     n = n/2

     n = n/2

     if (n==0) return u

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Another approach to writing a zero solver that doesn't require the user to input a domain is to use signals. The zero-finder could install a signal handler for floating-point exceptions. Then if

     if (n==0) return u

In IEEE 754, NaNs are often represented as floating-point numbers with the exponent emax + 1 and nonzero significands. Implementations are free to put system-dependent information into the significand. Thus there is not a unique NaN, but rather a whole family of NaNs. When a NaN and an ordinary floating-point number are combined, the result should be the same as the NaN operand. Thus if the result of a long computation is a NaN, the system-dependent information in the significand will be the information that was generated when the first NaN in the computation was generated. Actually, there is a caveat to the last statement. If both operands are NaNs, then the result will be one of those NaNs, but it might not be the NaN that was generated first

Infinity

Just as NaNs provide a way to continue a computation when expressions like 0/0 orare encountered, infinities provide a way to continue when an overflow occurs. This is much safer than simply returning the largest representable number. As an example, consider computing, when

The division of 0 by 0 results in a NaN. A nonzero number divided by 0, however, returns infinity. 1/0 =

The rule for determining the result of an operation that has infinity as an operand is simple. replace infinity with a finite number x and take the limit as x

Similarly, 4 -

Khi một biểu thức con ước tính thành NaN, giá trị của toàn bộ biểu thức cũng là một NaN. In the case of ±

Signed Zero

Zero is represented by the exponent emin - 1 and a zero significand. Since the sign bit can take on two different values, there are two zeros, +0 and -0. If a distinction were made when comparing +0 and -0, simple tests like

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Một ví dụ khác về việc sử dụng luồng dưới mối quan tâm bằng 0 có dấu và các hàm có gián đoạn ở 0, chẳng hạn như nhật ký. In IEEE arithmetic, it is natural to define log 0 = -

Probably the most interesting use of signed zero occurs in complex arithmetic. To take a simple example, consider the equation. Điều này chắc chắn đúng khi z

Back to. If z =1 = -1 + i0, then

and so, while. Thus IEEE arithmetic preserves this identity for all z. Some more sophisticated examples are given by Kahan [1987]. Although distinguishing between +0 and -0 has advantages, it can occasionally be confusing. For example, signed zero destroys the relation x = y 

số không chuẩn hóa

Consider normalized floating-point numbers with

It's very easy to imagine writing the code fragment,

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

The IEEE standard uses denormalized18 numbers, which guarantee (10), as well as other useful relations. They are the most controversial part of the standard and probably accounted for the long delay in getting 754 approved. Most high performance hardware that claims to be IEEE compatible does not support denormalized numbers directly, but rather traps when consuming or producing denormals, and leaves it to software to simulate the IEEE standard. 19 The idea behind denormalized numbers goes back to Goldberg [1967] and is very simple. When the exponent is emin, the significand does not have to be normalized, so that when

There is a small snag when

Nhắc lại ví dụ về

FIGURE D-2 illustrates denormalized numbers. The top number line in the figure shows normalized floating-point numbers. Notice the gap between 0 and the smallest normalized number. If the result of a floating-point calculation falls into this gulf, it is flushed to zero. The bottom number line shows what happens when denormals are added to the set of floating-point numbers. The "gulf" is filled in, and when the result of a calculation is less than, it is represented by the nearest denormal. When denormalized numbers are added to the number line, the spacing between adjacent floating-point numbers varies in a regular way. adjacent spacings are either the same length or differ by a factor of

Without gradual underflow, the simple expression x - y can have a very large relative error for normalized inputs, as was seen above for x = 6. 87 × 10-97 and y = 6. 81 × 10-97. Large relative errors can happen even without cancellation, as the following example shows [Demmel 1984]. Consider dividing two complex numbers, a + ib and c + id. The obvious formula

suffers from the problem that if either component of the denominator c + id is larger than, the formula will overflow, even though the final result may be well within range. A better method of computing the quotients is to use Smith's formula

Applying Smith's formula to (2 · 10-98 + i10-98)/(4 · 10-98 + i(2 · 10-98)) gives the correct answer of 0. 5 with gradual underflow. It yields 0. 4 với flush to zero, lỗi 100 ulps. It is typical for denormalized numbers to guarantee error bounds for arguments all the way down to 1. 0 x.

Exceptions, Flags and Trap Handlers

Khi một điều kiện đặc biệt như chia cho 0 hoặc tràn xảy ra trong số học IEEE, mặc định là cung cấp kết quả và tiếp tục. Typical of the default results are NaN for 0/0 and, and

Sometimes continuing execution in the face of exception conditions is not appropriate. The section Infinity gave the example of x/(x2 + 1). When x >, the denominator is infinite, resulting in a final answer of 0, which is totally wrong. Although for this formula the problem can be solved by rewriting it as 1/(x + x-1), rewriting may not always solve the problem. The IEEE standard strongly recommends that implementations allow trap handlers to be installed. Then when an exception occurs, the trap handler is called instead of setting the flag. The value returned by the trap handler will be used as the result of the operation. Trình xử lý bẫy có trách nhiệm xóa hoặc đặt cờ trạng thái;

The IEEE standard divides exceptions into 5 classes. overflow, underflow, division by zero, invalid operation and inexact. There is a separate status flag for each class of exception. The meaning of the first three exceptions is self-evident. Invalid operation covers the situations listed in TABLE D-3, and any comparison that involves a NaN. The default result of an operation that causes an invalid exception is to return a NaN, but the converse is not true. When one of the operands to an operation is a NaN, the result is a NaN but no invalid exception is raised unless the operation also satisfies one of the conditions in TABLE D-3. 20

*x is the exact result of the operation,

The inexact exception is raised when the result of a floating-point operation is not exact. In the

There is an implementation issue connected with the fact that the inexact exception is raised so often. If floating-point hardware does not have flags of its own, but instead interrupts the operating system to signal a floating-point exception, the cost of inexact exceptions could be prohibitive. This cost can be avoided by having the status flags maintained by software. The first time an exception is raised, set the software flag for the appropriate class, and tell the floating-point hardware to mask off that class of exceptions. Then all further exceptions will run without interrupting the operating system. When a user resets that status flag, the hardware mask is re-enabled

Trap Handlers

One obvious use for trap handlers is for backward compatibility. Old codes that expect to be aborted when exceptions occur can install a trap handler that aborts the process. This is especially useful for codes with a loop like

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

There is a more interesting use for trap handlers that comes up when computing products such asthat could potentially overflow. One solution is to use logarithms, and compute expinstead. Vấn đề với cách tiếp cận này là nó kém chính xác hơn và tốn kém hơn biểu thức đơn giản, ngay cả khi không có tràn. There is another solution using trap handlers called over/underflow counting that avoids both of these problems [Sterbenz 1974]

The idea is as follows. There is a global counter initialized to zero. Whenever the partial productoverflows for some k, the trap handler increments the counter by one and returns the overflowed quantity with the exponent wrapped around. In IEEE 754 single precision, emax = 127, so if pk = 1. 45 × 2130, it will overflow and cause the trap handler to be called, which will wrap the exponent back into range, changing pk to 1. 45 × 2-62 (see below). Similarly, if pk underflows, the counter would be decremented, and negative exponent would get wrapped around into a positive one. When all the multiplications are done, if the counter is zero then the final product is pn. If the counter is positive, the product overflowed, if the counter is negative, it underflowed. If none of the partial products are out of range, the trap handler is never called and the computation incurs no extra cost. Even if there are over/underflows, the calculation is more accurate than if it had been computed with logarithms, because each pk was computed from pk - 1 using a full precision multiply. Barnett [1987] discusses a formula where the full accuracy of over/underflow counting turned up an error in earlier tables of that formula

IEEE 754 specifies that when an overflow or underflow trap handler is called, it is passed the wrapped-around result as an argument. The definition of wrapped-around for overflow is that the result is computed as if to infinite precision, then divided by 2

Rounding Modes

In the IEEE standard, rounding occurs whenever an operation has a result that is not exact, since (with the exception of binary decimal conversion) each operation is computed exactly and then rounded. By default, rounding means round toward nearest. Tiêu chuẩn yêu cầu cung cấp ba chế độ làm tròn khác, đó là làm tròn về 0, làm tròn về phía +

One application of rounding modes occurs in interval arithmetic (another is mentioned in Binary to Decimal Conversion). When using interval arithmetic, the sum of two numbers x and y is an interval, whereis x

When a floating-point calculation is performed using interval arithmetic, the final answer is an interval that contains the exact result of the calculation. This is not very helpful if the interval turns out to be large (as it often does), since the correct answer could be anywhere in that interval. Interval arithmetic makes more sense when used in conjunction with a multiple precision floating-point package. The calculation is first performed with some precision p. If interval arithmetic suggests that the final answer may be inaccurate, the computation is redone with higher and higher precisions until the final interval is a reasonable size

Flags

The IEEE standard has a number of flags and modes. As discussed above, there is one status flag for each of the five exceptions. underflow, overflow, division by zero, invalid operation and inexact. There are four rounding modes. round toward nearest, round toward +

Consider writing a subroutine to compute xn, where n is an integer. When n > 0, a simple routine like

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     if (n==0) return u

     n = n/2

     n = n/2

     n = n/2

If n < 0, then a more accurate way to compute xn is not to call

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Another example of the use of flags occurs when computing arccos via the formula

If arctan(

Systems Aspects

The design of almost every aspect of a computer system requires knowledge about floating-point. Computer architectures usually have floating-point instructions, compilers must generate those floating-point instructions, and the operating system must decide what to do when exception conditions are raised for those floating-point instructions. Computer system designers rarely get guidance from numerical analysis texts, which are typically aimed at users and writers of software, not at computer designers. As an example of how plausible design decisions can lead to unexpected behavior, consider the following BASIC program

     n = n/2

     n = n/2

     n = n/2

When compiled and run using Borland's Turbo Basic on an IBM PC, the program prints

     n = n/2

     n = n/2

Incidentally, some people think that the solution to such anomalies is never to compare floating-point numbers for equality, but instead to consider them equal if they are within some error bound E. This is hardly a cure-all because it raises as many questions as it answers. What should the value of E be? If x < 0 and y > 0 are within E, should they really be considered to be equal, even though they have different signs? Furthermore, the relation defined by this rule, a ~ b 

Instruction Sets

It is quite common for an algorithm to require a short burst of higher precision in order to produce accurate results. One example occurs in the quadratic formula ()/2a. As discussed in the section Proof of Theorem 4, when b2

The computation of b2 - 4ac in double precision when each of the quantities a, b, and c are in single precision is easy if there is a multiplication instruction that takes two single precision numbers and produces a double precision result. In order to produce the exactly rounded product of two p-digit numbers, a multiplier needs to generate the entire 2p bits of product, although it may throw bits away as it proceeds. Thus, hardware to compute a double precision product from single precision operands will normally be only a little more expensive than a single precision multiplier, and much cheaper than a double precision multiplier. Despite this, modern instruction sets tend to provide only instructions that produce a result of the same precision as the operands. 23

If an instruction that combines two single precision operands to produce a double precision product was only useful for the quadratic formula, it wouldn't be worth adding to an instruction set. However, this instruction has many other uses. Consider the problem of solving a system of linear equations,

which can be written in matrix form as Ax = b, where

Suppose that a solution x(1) is computed by some method, perhaps Gaussian elimination. There is a simple way to improve the accuracy of the result called iterative improvement. First compute

and then solve the system

Note that if x(1) is an exact solution, then

The three steps (12), (13), and (14) can be repeated, replacing x(1) with x(2), and x(2) with x(3). This argument that x(i + 1) is more accurate than x(i) is only informal. For more information, see [Golub and Van Loan 1989]

When performing iterative improvement,

To summarize, instructions that multiply two floating-point numbers and return a product with twice the precision of the operands make a useful addition to a floating-point instruction set. Some of the implications of this for compilers are discussed in the next section

Languages and Compilers

The interaction of compilers and floating-point is discussed in Farnum [1988], and much of the discussion in this section is taken from that paper

Ambiguity

Ideally, a language definition should define the semantics of the language precisely enough to prove statements about programs. While this is usually true for the integer part of a language, language definitions often have a large grey area when it comes to floating-point. Perhaps this is due to the fact that many language designers believe that nothing can be proven about floating-point, since it entails rounding error. Nếu vậy, các phần trước đã chứng minh sự ngụy biện trong lập luận này. This section discusses some common grey areas in language definitions, including suggestions about how to deal with them

Remarkably enough, some languages don't clearly specify that if

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Một sự mơ hồ khác trong hầu hết các định nghĩa ngôn ngữ liên quan đến những gì xảy ra khi tràn, tràn và các ngoại lệ khác. The IEEE standard precisely specifies the behavior of exceptions, and so languages that use the standard as a model can avoid any ambiguity on this point

Another grey area concerns the interpretation of parentheses. Due to roundoff errors, the associative laws of algebra do not necessarily hold for floating-point numbers. For example, the expression

     n = n/2

     n = n/2

Subexpression evaluation is imprecisely defined in many languages. Suppose that

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

The second approach is to allow mixed expressions, in which case rules for subexpression evaluation must be provided. There are a number of guiding examples. The original definition of C required that every floating-point expression be computed in double precision [Kernighan and Ritchie 1978]. This leads to anomalies like the example at the beginning of this section. The expression

     n = n/2

     n = n/2

Another guiding example is inner products. If the inner product has thousands of terms, the rounding error in the sum can become substantial. One way to reduce this rounding error is to accumulate the sums in double precision (this will be discussed in more detail in the section Optimizers). If

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

A rule that covers both of the previous two examples is to compute an expression in the highest precision of any variable that occurs in that expression. Then

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

A more sophisticated subexpression evaluation rule is as follows. First assign each operation a tentative precision, which is the maximum of the precisions of its operands. This assignment has to be carried out from the leaves to the root of the expression tree. Then perform a second pass from the root to the leaves. In this pass, assign to each operation the maximum of the tentative precision and the precision expected by the parent. In the case of

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

The disadvantage of this rule is that the evaluation of a subexpression depends on the expression in which it is embedded. This can have some annoying consequences. For example, suppose you are debugging a program and want to know the value of a subexpression. You cannot simply type the subexpression to the debugger and ask it to be evaluated, because the value of the subexpression in the program depends on the expression it is embedded in. A final comment on subexpressions. since converting decimal constants to binary is an operation, the evaluation rule also affects the interpretation of decimal constants. This is especially important for constants like

     n = n/2

Another potential grey area occurs when a language includes exponentiation as one of its built-in operations. Unlike the basic arithmetic operations, the value of exponentiation is not always obvious [Kahan and Coonen 1982]. If

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Trên thực tế, tiêu chuẩn FORTRAN nói rằng

Unfortunately, with the introduction of ±

     n = n/2

The IEEE Standard

The section The IEEE Standard," discussed many of the features of the IEEE standard. However, the IEEE standard says nothing about how these features are to be accessed from a programming language. Thus, there is usually a mismatch between floating-point hardware that supports the standard and programming languages like C, Pascal or FORTRAN. Some of the IEEE capabilities can be accessed through a library of subroutine calls. For example the IEEE standard requires that square root be exactly rounded, and the square root function is often implemented directly in hardware. This functionality is easily accessed via a library square root routine. However, other aspects of the standard are not so easily implemented as subroutines. For example, most computer languages specify at most two floating-point types, while the IEEE standard has four different precisions (although the recommended configurations are single plus single-extended or single, double, and double-extended). Infinity provides another example. Các hằng để biểu diễn ±

Một tình huống tinh vi hơn là thao túng trạng thái liên quan đến tính toán, trong đó trạng thái bao gồm các chế độ làm tròn, bit kích hoạt bẫy, trình xử lý bẫy và cờ ngoại lệ. Một cách tiếp cận là cung cấp các chương trình con để đọc và ghi trạng thái. Ngoài ra, một cuộc gọi duy nhất có thể đặt nguyên tử một giá trị mới và trả về giá trị cũ thường hữu ích. Như các ví dụ trong phần Các cờ cho thấy, một kiểu sửa đổi trạng thái IEEE rất phổ biến là chỉ thay đổi nó trong phạm vi của một khối hoặc chương trình con. Do đó, lập trình viên phải tìm từng lối ra khỏi khối và đảm bảo trạng thái được khôi phục. Hỗ trợ ngôn ngữ để đặt trạng thái chính xác trong phạm vi của một khối sẽ rất hữu ích ở đây. Modula-3 là một ngôn ngữ triển khai ý tưởng này cho trình xử lý bẫy [Nelson 1991]

There are a number of minor points that need to be considered when implementing the IEEE standard in a language. Vì x - x = +0 với mọi x,27 (+0) - (+0) = +0. Tuy nhiên, -(+0) = -0, do đó -x không được định nghĩa là 0 - x. Việc giới thiệu NaN có thể gây nhầm lẫn, bởi vì một NaN không bao giờ bằng bất kỳ số nào khác (bao gồm cả NaN khác), vì vậy x = x không còn đúng nữa. Trên thực tế, biểu thức x

     n = n/2

     n = n/2

Mặc dù tiêu chuẩn IEEE xác định các phép toán dấu phẩy động cơ bản để trả về NaN nếu bất kỳ toán hạng nào là NaN, đây có thể không phải lúc nào cũng là định nghĩa tốt nhất cho các phép toán phức hợp. Ví dụ: khi tính toán hệ số tỷ lệ thích hợp để sử dụng trong việc vẽ đồ thị, giá trị lớn nhất của một tập hợp giá trị phải được tính toán. Trong trường hợp này, điều hợp lý là thao tác tối đa chỉ cần bỏ qua NaN

Cuối cùng, làm tròn có thể là một vấn đề. Tiêu chuẩn IEEE xác định làm tròn rất chính xác và nó phụ thuộc vào giá trị hiện tại của các chế độ làm tròn. Điều này đôi khi xung đột với định nghĩa làm tròn ẩn trong chuyển đổi loại hoặc hàm

     n = n/2

Trình tối ưu hóa

Compiler texts tend to ignore the subject of floating-point. For example Aho et al. [1986] mentions replacing

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

This is designed to give an estimate for machine epsilon. If an optimizing compiler notices that eps + 1 > 1

Many problems, such as numerical integration and the numerical solution of differential equations involve computing sums with many terms. Because each addition can potentially introduce an error as large as . 5 ulp, a sum involving thousands of terms can have quite a bit of rounding error. A simple way to correct for this is to store the partial summand in a double precision variable and to perform each addition using double precision. If the calculation is being done in single precision, performing the sum in double precision is easy on most computer systems. However, if the calculation is already being done in double precision, doubling the precision is not so simple. One method that is sometimes advocated is to sort the numbers and add them from smallest to largest. However, there is a much more efficient method which dramatically improves the accuracy of sums, namely

Theorem 8 (Kahan Summation Formula)

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Using the naive formula, the computed sum is equal towhere .

An optimizer that believed floating-point arithmetic obeyed the laws of algebra would conclude that C = [T-S] - Y = [(S+Y)-S] - Y = 0, rendering the algorithm completely useless. These examples can be summarized by saying that optimizers should be extremely cautious when applying algebraic identities that hold for the mathematical real numbers to expressions involving floating-point variables

Another way that optimizers can change the semantics of floating-point code involves constants. In the expression

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Common subexpression elimination is another example of an optimization that can change floating-point semantics, as illustrated by the following code

     n = n/2

     n = n/2

     n = n/2

Although

     n = n/2

     n = n/2

Despite these examples, there are useful optimizations that can be done on floating-point code. First of all, there are algebraic identities that are valid for floating-point numbers. Some examples in IEEE arithmetic are x + y = y + x, 2 ×  x = x + x, 1 × x = x, and 0. 5× x = x/2. However, even these simple identities can fail on a few machines such as CDC and Cray supercomputers. Instruction scheduling and in-line procedure substitution are two other potentially useful optimizations. 28

As a final example, consider the expression

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Some compiler writers view restrictions which prohibit converting (x + y) + z to x + (y + z) as irrelevant, of interest only to programmers who use unportable tricks. Perhaps they have in mind that floating-point numbers model real numbers and should obey the same laws that real numbers do. The problem with real number semantics is that they are extremely expensive to implement. Every time two n bit numbers are multiplied, the product will have 2n bits. Every time two n bit numbers with widely spaced exponents are added, the number of bits in the sum is n + the space between the exponents. The sum could have up to (emax - emin) + n bits, or roughly 2·emax + n bits. An algorithm that involves thousands of operations (such as solving a linear system) will soon be operating on numbers with many significant bits, and be hopelessly slow. The implementation of library functions such as sin and cos is even more difficult, because the value of these transcendental functions aren't rational numbers. Exact integer arithmetic is often provided by lisp systems and is handy for some problems. However, exact floating-point arithmetic is rarely useful

The fact is that there are useful algorithms (like the Kahan summation formula) that exploit the fact that (x + y) + z

holds (as well as similar bounds for -, × and /). Since these bounds hold for almost all commercial hardware, it would be foolish for numerical programmers to ignore such algorithms, and it would be irresponsible for compiler writers to destroy these algorithms by pretending that floating-point variables have real number semantics

Exception Handling

The topics discussed up to now have primarily concerned systems implications of accuracy and precision. Trap handlers also raise some interesting systems issues. The IEEE standard strongly recommends that users be able to specify a trap handler for each of the five classes of exceptions, and the section Trap Handlers, gave some applications of user defined trap handlers. In the case of invalid operation and division by zero exceptions, the handler should be provided with the operands, otherwise, with the exactly rounded result. Depending on the programming language being used, the trap handler might be able to access other variables in the program as well. For all exceptions, the trap handler must be able to identify what operation was being performed and the precision of its destination

The IEEE standard assumes that operations are conceptually serial and that when an interrupt occurs, it is possible to identify the operation and its operands. On machines which have pipelining or multiple arithmetic units, when an exception occurs, it may not be enough to simply have the trap handler examine the program counter. Hardware support for identifying exactly which operation trapped may be necessary

Another problem is illustrated by the following program fragment

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Suppose the second multiply raises an exception, and the trap handler wants to use the value of

     if (n==0) return u

     if (n==0) return u

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     if (n==0) return u

But there are still problems. In the fragment

the two instructions might well be executed in parallel. If the multiply traps, its argument

     n = n/2

     n = n/2

W. Kahan has proposed using presubstitution instead of trap handlers to avoid these problems. In this method, the user specifies an exception and the value he wants to be used as the result when the exception occurs. As an example, suppose that in code for computing (sin x)/x, the user decides that x = 0 is so rare that it would improve performance to avoid a test for x = 0, and instead handle this case when a 0/0 trap occurs. Using IEEE trap handlers, the user would write a handler that returns a value of 1 and install it before computing sin x/x. Using presubstitution, the user would specify that when an invalid operation occurs, the value 1 should be used. Kahan gọi đây là sự thay thế trước, bởi vì giá trị được sử dụng phải được chỉ định trước khi xảy ra ngoại lệ. Khi sử dụng trình xử lý bẫy, giá trị được trả về có thể được tính khi bẫy xảy ra

The advantage of presubstitution is that it has a straightforward hardware implementation. 29 As soon as the type of exception has been determined, it can be used to index a table which contains the desired result of the operation. Although presubstitution has some attractive attributes, the widespread acceptance of the IEEE standard makes it unlikely to be widely implemented by hardware manufacturers

The Details

A number of claims have been made in this paper concerning properties of floating-point arithmetic. We now proceed to show that floating-point is not black magic, but rather is a straightforward subject whose claims can be verified mathematically. This section is divided into three parts. The first part presents an introduction to error analysis, and provides the details for the section Rounding Error. The second part explores binary to decimal conversion, filling in some gaps from the section The IEEE Standard. The third part discusses the Kahan summation formula, which was used as an example in the section Systems Aspects

Rounding Error

In the discussion of rounding error, it was stated that a single guard digit is enough to guarantee that addition and subtraction will always be accurate (Theorem 2). We now proceed to verify this fact. Theorem 2 has two parts, one for subtraction and one for addition. The part for subtraction is

Theorem 9

If x and y are positive floating-point numbers in a format with parameters

Proof

When

Định lý 10

If x

Proof

The sum is at least

It is obvious that combining these two theorems gives Theorem 2. Theorem 2 gives the relative error for performing one operation. Comparing the rounding error of x2 - y2 and (x + y) (x - y) requires knowing the relative error of multiple operations. The relative error of xy is

Similarly

Assuming that multiplication is performed by computing the exact product and then rounding, the relative error is at most . 5 ulp, so

for any floating-point numbers u and v. Putting these three equations together (letting u = xy and v = x

So the relative error incurred when computing (x - y) (x + y) is

This relative error is equal to

A similar analysis of (x

When x and y are nearby, the error term (

We next turn to an analysis of the formula for the area of a triangle. In order to estimate the maximum error that can occur when computing with (7), the following fact will be needed

Theorem 11

Proof

When

Theorem 12

Proof

     n = n/2

Theorem 12 certainly shows that there is no catastrophic cancellation in formula (7). So although it is not necessary to show formula (7) is numerically stable, it is satisfying to have a bound for the entire formula, which is what Theorem 3 of Cancellation gives

Proof of Theorem 3

To make the heuristic explanation immediately following the statement of Theorem 4 precise, the next theorem describes just how closely µ(x) approximates a constant

Theorem 13

Proof

Proof of Theorem 4

where .

is

with .

An interesting example of error analysis using formulas (19), (20), and (21) occurs in the quadratic formula. The section Cancellation, explained how rewriting the equation will eliminate the potential cancellation caused by the ± operation. But there is another potential cancellation that can occur when computing d = b2 - 4ac. This one cannot be eliminated by a simple rearrangement of the formula. Roughly speaking, when b2

If b2

Proof. Write (b

The inequality

shows that

where

so the absolute error ina is about. Since

Finally, we turn to the proof of Theorem 6. It is based on the following fact, which is proven in the section Theorem 14 and Theorem 8

Theorem 14

Proof of Theorem 6

Theorem 6 gives a way to express the product of two working precision numbers exactly as a sum. There is a companion formula for expressing a sum exactly. If . x.

Binary to Decimal Conversion

Since single precision has p = 24, and 224 < 108, you might expect that converting a binary number to 8 decimal digits would be sufficient to recover the original binary number. However, this is not the case

Theorem 15

Proof

The same argument applied to double precision shows that 17 decimal digits are required to recover a double precision number

Binary-decimal conversion also provides another example of the use of flags. Recall from the section Precision, that to recover a binary number from its decimal expansion, the decimal to binary conversion must be computed exactly. That conversion is performed by multiplying the quantities N and 10. P. (which are both exact if p < 13) in single-extended precision and then rounding this to single precision (or dividing if p < 0; both cases are similar). Of course the computation of N · 10. P. cannot be exact; it is the combined operation round(N · 10. P. ) that must be exact, where the rounding is from single-extended to single precision. To see why it might fail to be exact, take the simple case of

By using the IEEE flags, double rounding can be avoided as follows. Save the current value of the inexact flag, and then reset it. Set the rounding mode to round-to-zero. Then perform the multiplication N · 10. P. Lưu trữ giá trị mới của cờ không chính xác trong

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Errors In Summation

The section Optimizers, mentioned the problem of accurately computing very long sums. The simplest approach to improving accuracy is to double the precision. To get a rough estimate of how much doubling the precision improves the accuracy of a sum, let s1 = x1, s2 = s1 

The first equality of (31) shows that the computed value ofis the same as if an exact summation was performed on perturbed values of xj. The first term x1 is perturbed by n

For an intuitive explanation of why the Kahan summation formula works, consider the following diagram of the procedure

Each time a summand is added, there is a correction factor C which will be applied on the next loop. So first subtract the correction C computed in the previous loop from Xj, giving the corrected summand Y. Then add this summand to the running sum S. The low order bits of Y (namely Yl) are lost in the sum. Next compute the high order bits of Y by computing T - S. When Y is subtracted from this, the low order bits of Y will be recovered. These are the bits that were lost in the first sum in the diagram. They become the correction factor for the next loop. A formal proof of Theorem 8, taken from Knuth [1981] page 572, appears in the section Theorem 14 and Theorem 8. "

Summary

It is not uncommon for computer system designers to neglect the parts of a system related to floating-point. This is probably due to the fact that floating-point is given very little (if any) attention in the computer science curriculum. This in turn has caused the apparently widespread belief that floating-point is not a quantifiable subject, and so there is little point in fussing over the details of hardware and software that deal with it

This paper has demonstrated that it is possible to reason rigorously about floating-point. For example, floating-point algorithms involving cancellation can be proven to have small relative errors if the underlying hardware has a guard digit, and there is an efficient algorithm for binary-decimal conversion that can be proven to be invertible, provided that extended precision is supported. The task of constructing reliable floating-point software is made much easier when the underlying computer system is supportive of floating-point. In addition to the two examples just mentioned (guard digits and extended precision), the section Systems Aspects of this paper has examples ranging from instruction set design to compiler optimization illustrating how to better support floating-point

The increasing acceptance of the IEEE floating-point standard means that codes that utilize features of the standard are becoming ever more portable. The section The IEEE Standard, gave numerous examples illustrating how the features of the IEEE standard can be used in writing practical floating-point codes

Acknowledgments

This article was inspired by a course given by W. Kahan at Sun Microsystems from May through July of 1988, which was very ably organized by David Hough of Sun. My hope is to enable others to learn about the interaction of floating-point and computer systems without having to get up in time to attend 8. 00 a. m. lectures. Thanks are due to Kahan and many of my colleagues at Xerox PARC (especially John Gilbert) for reading drafts of this paper and providing many useful comments. Nhận xét từ Paul Hilfinger và một trọng tài ẩn danh cũng giúp cải thiện phần trình bày

References

Aho, Alfred V. , Sethi, R. , và Ullman J. Đ. 1986. Trình biên dịch. Principles, Techniques and Tools, Addison-Wesley, Reading, MA

ANSI 1978. American National Standard Programming Language FORTRAN, ANSI Standard X3. 9-1978, American National Standards Institute, New York, NY

Barnett, David 1987. A Portable Floating-Point Environment, unpublished manuscript

Brown, W. S. 1981. A Simple but Realistic Model of Floating-Point Computation, ACM Trans. on Math. Software 7(4), pp. 445-480

Cody, W. J et. al. 1984. A Proposed Radix- and Word-length-independent Standard for Floating-point Arithmetic, IEEE Micro 4(4), pp. 86-100

Cody, W. J. 1988. Floating-Point Standards -- Theory and Practice, in "Reliability in Computing. the role of interval methods in scientific computing", ed. by Ramon E. Moore, pp. 99-107, Academic Press, Boston, MA

Coonen, Jerome 1984. Contributions to a Proposed Standard for Binary Floating-Point Arithmetic, PhD Thesis, Univ. of California, Berkeley

Dekker, T. J. 1971. A Floating-Point Technique for Extending the Available Precision, Numer. Math. 18(3), pp. 224-242

Demmel, James 1984. Underflow and the Reliability of Numerical Software, SIAM J. Sci. Stat. Comput. 5(4), pp. 887-919

Farnum, Charles 1988. Compiler Support for Floating-point Computation, Software-Practice and Experience, 18(7), pp. 701-709

Forsythe, G. E. and Moler, C. B. 1967. Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, NJ

Goldberg, I. Bennett 1967. 27 Bits Are Not Enough for 8-Digit Accuracy, Comm. of the ACM. 10(2), pp 105-106

Goldberg, David 1990. Computer Arithmetic, in "Computer Architecture. A Quantitative Approach", by David Patterson and John L. Hennessy, Appendix A, Morgan Kaufmann, Los Altos, CA

Golub, Gene H. and Van Loan, Charles F. 1989. Matrix Computations, 2nd edition,The Johns Hopkins University Press, Baltimore Maryland

Graham, Ronald L. , Knuth, Donald E. and Patashnik, Oren. 1989. Concrete Mathematics, Addison-Wesley, Reading, MA, p. 162

Hewlett Packard 1982. HP-15C Advanced Functions Handbook

IEEE 1987. IEEE Standard 754-1985 for Binary Floating-point Arithmetic, IEEE, (1985). Reprinted in SIGPLAN 22(2) pp. 9-25

Kahan, W. 1972. A Survey Of Error Analysis, in Information Processing 71, Vol 2, pp. 1214 - 1239 (Ljubljana, Yugoslavia), North Holland, Amsterdam

Kahan, W. 1986. Calculating Area and Angle of a Needle-like Triangle, unpublished manuscript

Kahan, W. 1987. Branch Cuts for Complex Elementary Functions, in "The State of the Art in Numerical Analysis", ed. by M. J. D. Powell and A. Iserles (Univ of Birmingham, England), Chapter 7, Oxford University Press, New York

Kahan, W. 1988. Unpublished lectures given at Sun Microsystems, Mountain View, CA

Kahan, W. and Coonen, Jerome T. 1982. The Near Orthogonality of Syntax, Semantics, and Diagnostics in Numerical Programming Environments, in "The Relationship Between Numerical Computation And Programming Languages", ed. by J. K. Reid, pp. 103-115, North-Holland, Amsterdam

Kahan, W. and LeBlanc, E. 1985. Anomalies in the IBM Acrith Package, Proc. 7th IEEE Symposium on Computer Arithmetic (Urbana, Illinois), pp. 322-331

Kernighan, Brian W. and Ritchie, Dennis M. 1978. The C Programming Language, Prentice-Hall, Englewood Cliffs, NJ

Kirchner, R. và Kulisch, U. 1987. Arithmetic for Vector Processors, Proc. Hội nghị chuyên đề IEEE lần thứ 8 về số học máy tính (Como, Ý), trang. 256-269

Knuth, Donald E. , 1981. Nghệ thuật lập trình máy tính, Tập II, Phiên bản thứ hai, Addison-Wesley, Reading, MA

Kulisch, U. W. , và Miranker, W. L. 1986. Số học của máy tính kỹ thuật số. Một cách tiếp cận mới, Đánh giá SIAM 28(1), trang 1-36

Matula, D. W. và Kornerup, P. 1985. Số học hợp lý chính xác hữu hạn. Hệ thống số gạch chéo, IEEE Trans. trên may tinh. C-34(1), trang 3-18

Nelson, G. 1991. Systems Programming With Modula-3, Prentice-Hall, Englewood Cliffs, NJ

Reiser, John F. and Knuth, Donald E. 1975. Evading the Drift in Floating-point Addition, Information Processing Letters 3(3), pp 84-87

Sterbenz, Pat H. 1974. Floating-Point Computation, Prentice-Hall, Englewood Cliffs, NJ

Swartzlander, Earl E. and Alexopoulos, Aristides G. 1975. The Sign/Logarithm Number System, IEEE Trans. Comput. C-24(12), pp. 1238-1242

Walther, J. S. , 1971. A unified algorithm for elementary functions, Proceedings of the AFIP Spring Joint Computer Conf. 38, trang. 379-385

Theorem 14 and Theorem 8

This section contains two of the more technical proofs that were omitted from the text

Theorem 14

Proof

     n = n/2

     n = n/2

     n = n/2

     if (n==0) return u

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Theorem 8 (Kahan Summation Formula)

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Proof

Finally, what is wanted is the coefficient of x1 in sk. To get this value, let xn + 1 = 0, let all the Greek letters with subscripts of n + 1 equal 0, and compute sn + 1. Then sn + 1 = sn - cn, and the coefficient of x1 in sn is less than the coefficient in sn + 1, which is Sn = 1 +

Differences Among IEEE 754 Implementations

Bài báo trước đã chỉ ra rằng số học dấu phẩy động phải được triển khai cẩn thận, vì các lập trình viên có thể phụ thuộc vào các thuộc tính của nó để đảm bảo tính đúng đắn và chính xác của chương trình của họ. Đặc biệt, tiêu chuẩn IEEE yêu cầu triển khai cẩn thận và chỉ có thể viết các chương trình hữu ích hoạt động chính xác và mang lại kết quả chính xác trên các hệ thống tuân thủ tiêu chuẩn. Người đọc có thể muốn kết luận rằng các chương trình như vậy sẽ có thể di chuyển được đến tất cả các hệ thống của IEEE. Thật vậy, phần mềm di động sẽ dễ viết hơn nếu nhận xét "Khi một chương trình được di chuyển giữa hai máy và cả hai đều hỗ trợ số học IEEE, thì nếu bất kỳ kết quả trung gian nào khác đi, thì đó phải là do lỗi phần mềm, không phải do sự khác biệt về số học," là

Thật không may, tiêu chuẩn IEEE không đảm bảo rằng cùng một chương trình sẽ mang lại kết quả giống hệt nhau trên tất cả các hệ thống phù hợp. Hầu hết các chương trình sẽ thực sự tạo ra các kết quả khác nhau trên các hệ thống khác nhau vì nhiều lý do. Thứ nhất, hầu hết các chương trình liên quan đến việc chuyển đổi số giữa định dạng thập phân và nhị phân và tiêu chuẩn IEEE không chỉ định đầy đủ độ chính xác mà các chuyển đổi đó phải được thực hiện. Mặt khác, nhiều chương trình sử dụng các chức năng cơ bản do thư viện hệ thống cung cấp và tiêu chuẩn hoàn toàn không chỉ định các chức năng này. Tất nhiên, hầu hết các lập trình viên đều biết rằng các tính năng này nằm ngoài phạm vi của tiêu chuẩn IEEE.

Nhiều lập trình viên có thể không nhận ra rằng ngay cả một chương trình chỉ sử dụng các định dạng số và hoạt động theo tiêu chuẩn IEEE có thể tính toán các kết quả khác nhau trên các hệ thống khác nhau. Trên thực tế, các tác giả của tiêu chuẩn dự định cho phép các triển khai khác nhau thu được các kết quả khác nhau. Ý định của họ thể hiện rõ trong định nghĩa về thuật ngữ đích trong tiêu chuẩn IEEE 754. "Đích có thể được chỉ định rõ ràng bởi người dùng hoặc được cung cấp ngầm bởi hệ thống (ví dụ: kết quả trung gian trong các biểu thức con hoặc đối số cho các thủ tục). Một số ngôn ngữ đặt kết quả tính toán trung gian ở đích ngoài tầm kiểm soát của người dùng. Tuy nhiên, tiêu chuẩn này xác định kết quả của một hoạt động theo định dạng của đích đó và các giá trị của toán hạng. " (IEEE 754-1985, p. 7) Nói cách khác, tiêu chuẩn IEEE yêu cầu mỗi kết quả được làm tròn chính xác theo độ chính xác của đích mà nó sẽ được đặt vào, nhưng tiêu chuẩn không yêu cầu độ chính xác của đích đó được xác định bởi chương trình của người dùng. Do đó, các hệ thống khác nhau có thể đưa kết quả của chúng đến các đích với độ chính xác khác nhau, khiến cùng một chương trình tạo ra các kết quả khác nhau (đôi khi rất đáng kể), mặc dù các hệ thống đó đều tuân theo tiêu chuẩn

Một số ví dụ trong bài báo trước phụ thuộc vào một số kiến ​​thức về cách làm tròn số học dấu phẩy động. Để dựa vào các ví dụ như thế này, một lập trình viên phải có khả năng dự đoán cách một chương trình sẽ được diễn giải và đặc biệt, trên hệ thống IEEE, độ chính xác của đích đến của mỗi phép toán số học có thể là bao nhiêu. Than ôi, lỗ hổng trong định nghĩa đích của tiêu chuẩn IEEE làm suy yếu khả năng của lập trình viên để biết chương trình sẽ được diễn giải như thế nào. Do đó, một số ví dụ nêu trên, khi được triển khai dưới dạng các chương trình di động rõ ràng bằng ngôn ngữ cấp cao, có thể không hoạt động chính xác trên các hệ thống IEEE thường cung cấp kết quả tới đích với độ chính xác khác với mong đợi của lập trình viên. Các ví dụ khác có thể hoạt động, nhưng việc chứng minh rằng chúng hoạt động có thể nằm ngoài khả năng của một lập trình viên bình thường

Trong phần này, chúng tôi phân loại các triển khai số học IEEE 754 hiện có dựa trên độ chính xác của các định dạng đích mà chúng thường sử dụng. Sau đó, chúng tôi xem xét một số ví dụ từ bài báo để chỉ ra rằng việc cung cấp kết quả với độ chính xác rộng hơn mong đợi của chương trình có thể khiến chương trình tính toán kết quả sai mặc dù nó có thể đúng khi sử dụng độ chính xác dự kiến. Chúng tôi cũng xem lại một trong những bằng chứng trong bài báo để minh họa nỗ lực trí tuệ cần thiết để đối phó với độ chính xác ngoài dự kiến ​​ngay cả khi nó không làm mất hiệu lực chương trình của chúng tôi. Những ví dụ này cho thấy rằng bất chấp tất cả những gì tiêu chuẩn IEEE quy định, sự khác biệt mà tiêu chuẩn này cho phép giữa các triển khai khác nhau có thể ngăn chúng ta viết phần mềm số hiệu quả, di động có hành vi mà chúng ta có thể dự đoán chính xác. Sau đó, để phát triển phần mềm như vậy, trước tiên chúng ta phải tạo ra các ngôn ngữ lập trình và môi trường hạn chế tính biến đổi mà tiêu chuẩn IEEE cho phép và cho phép các lập trình viên thể hiện ngữ nghĩa dấu phẩy động mà chương trình của họ phụ thuộc vào.

Triển khai IEEE 754 hiện tại

Việc triển khai số học IEEE 754 hiện tại có thể được chia thành hai nhóm được phân biệt theo mức độ chúng hỗ trợ các định dạng dấu phẩy động khác nhau trong phần cứng. Các hệ thống dựa trên mở rộng, được minh họa bởi dòng bộ xử lý Intel x86, cung cấp hỗ trợ đầy đủ cho định dạng độ chính xác kép mở rộng nhưng chỉ hỗ trợ một phần cho độ chính xác đơn và kép. chúng cung cấp các hướng dẫn để tải hoặc lưu trữ dữ liệu ở độ chính xác đơn và kép, chuyển đổi dữ liệu nhanh chóng sang hoặc từ định dạng kép mở rộng và chúng cung cấp các chế độ đặc biệt (không phải mặc định) trong đó kết quả của các phép toán số học được làm tròn thành đơn . (Bộ xử lý sê-ri Motorola 68000 làm tròn kết quả cho cả độ chính xác và phạm vi của định dạng đơn hoặc kép trong các chế độ này. Intel x86 và bộ xử lý tương thích làm tròn kết quả thành độ chính xác của định dạng đơn hoặc kép nhưng vẫn giữ nguyên phạm vi như định dạng kép mở rộng. ) Các hệ thống đơn/kép, bao gồm hầu hết các bộ xử lý RISC, cung cấp hỗ trợ đầy đủ cho các định dạng chính xác đơn và kép nhưng không hỗ trợ định dạng chính xác kép mở rộng tuân thủ IEEE. (Kiến trúc IBM POWER chỉ cung cấp hỗ trợ một phần cho độ chính xác đơn, nhưng với mục đích của phần này, chúng tôi phân loại nó là hệ thống đơn/kép. )

Để xem cách tính toán có thể hoạt động khác nhau trên hệ thống dựa trên mở rộng so với trên hệ thống đơn/kép, hãy xem xét phiên bản C của ví dụ từ phần Các khía cạnh hệ thống

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Ở đây các hằng số 3. 0 and 7. 0 được hiểu là số dấu phẩy động có độ chính xác kép và biểu thức 3. 0/7. 0 kế thừa kiểu dữ liệu

     n = n/2

     n = n/2

     n = n/2

Trên một hệ thống dựa trên mở rộng, mặc dù biểu thức 3. 0/7. 0 có loại

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Cạm bẫy trong tính toán trên các hệ thống dựa trên mở rộng

Sự khôn ngoan thông thường cho rằng các hệ thống dựa trên mở rộng phải tạo ra kết quả ít nhất là chính xác, nếu không muốn nói là chính xác hơn kết quả được cung cấp trên hệ thống đơn/kép, vì hệ thống trước luôn cung cấp độ chính xác ít nhất bằng và thường cao hơn hệ thống sau. Các ví dụ tầm thường như chương trình C ở trên cũng như các chương trình phức tạp hơn dựa trên các ví dụ được thảo luận bên dưới cho thấy sự khôn ngoan này tốt nhất là ngây thơ. một số chương trình rõ ràng là di động, thực sự là di động trên các hệ thống đơn/kép, cung cấp kết quả không chính xác trên các hệ thống dựa trên mở rộng chính xác do trình biên dịch và phần cứng đôi khi cung cấp độ chính xác cao hơn mong đợi của chương trình

Các ngôn ngữ lập trình hiện tại khiến chương trình khó xác định độ chính xác mà nó mong đợi. Như phần Ngôn ngữ và Trình biên dịch đã đề cập, nhiều ngôn ngữ lập trình không chỉ định rằng mỗi lần xuất hiện của một biểu thức như

     n = n/2

     n = n/2

Các tiêu chuẩn ngôn ngữ không hoàn toàn đổ lỗi cho sự thất thường của việc đánh giá biểu thức. Các hệ thống dựa trên mở rộng chạy hiệu quả nhất khi các biểu thức được đánh giá trong các thanh ghi độ chính xác mở rộng bất cứ khi nào có thể, tuy nhiên các giá trị phải được lưu trữ được lưu trữ ở độ chính xác hẹp nhất được yêu cầu. Hạn chế một ngôn ngữ để yêu cầu đánh giá

     n = n/2

     n = n/2

Các chương trình thực tế có phụ thuộc vào giả định rằng một biểu thức đã cho luôn đánh giá cùng một giá trị không?

     n = n/2

     n = n/2

     n = n/2

Trên hệ thống dựa trên mở rộng, trình biên dịch có thể đánh giá biểu thức

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Để thuật toán của Định lý 4 hoạt động chính xác, biểu thức

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Có những ví dụ khác có thể gặp trục trặc trên các hệ thống dựa trên mở rộng ngay cả khi mỗi biểu thức con được lưu trữ và do đó được làm tròn với cùng độ chính xác. Nguyên nhân là làm tròn kép. Ở chế độ chính xác mặc định, một hệ thống dựa trên mở rộng ban đầu sẽ làm tròn từng kết quả thành độ chính xác kép mở rộng. Nếu kết quả đó sau đó được lưu trữ với độ chính xác gấp đôi, nó sẽ được làm tròn lại. Sự kết hợp của hai cách làm tròn này có thể mang lại một giá trị khác với giá trị có được bằng cách làm tròn kết quả đầu tiên một cách chính xác để tăng gấp đôi độ chính xác. Điều này có thể xảy ra khi kết quả được làm tròn thành độ chính xác kép mở rộng là "trường hợp giữa chừng", tôi. e. , nó nằm chính xác ở giữa hai số chính xác kép, do đó, lần làm tròn thứ hai được xác định theo quy tắc làm tròn số chẵn. Nếu lần làm tròn thứ hai này quay cùng hướng với lần đầu tiên, thì sai số làm tròn ròng sẽ vượt quá nửa đơn vị ở vị trí cuối cùng. (Tuy nhiên, xin lưu ý rằng việc làm tròn hai lần chỉ ảnh hưởng đến các phép tính có độ chính xác kép. Người ta có thể chứng minh rằng tổng, hiệu, tích hoặc thương của hai số p-bit hoặc căn bậc hai của một số p-bit, trước tiên được làm tròn thành q bit và sau đó thành p bit cho cùng một giá trị như thể kết quả là . Do đó, độ chính xác kép mở rộng đủ rộng để các tính toán chính xác đơn lẻ không bị làm tròn kép. )

Một số thuật toán phụ thuộc vào làm tròn chính xác có thể thất bại với làm tròn kép. Trên thực tế, ngay cả một số thuật toán không yêu cầu làm tròn chính xác và hoạt động chính xác trên nhiều loại máy không tuân thủ IEEE 754 cũng có thể thất bại khi làm tròn hai lần. Hữu ích nhất trong số này là các thuật toán di động để thực hiện nhiều phép tính số học chính xác mô phỏng được đề cập trong phần Phép toán được làm tròn chính xác. Ví dụ: quy trình được mô tả trong Định lý 6 để tách một số dấu phẩy động thành các phần cao và thấp không hoạt động chính xác trong số học làm tròn kép. cố gắng chia số chính xác kép 252 + 3 × 226 - 1 thành hai phần, mỗi phần có tối đa 26 bit. Khi mỗi thao tác được làm tròn chính xác thành độ chính xác gấp đôi, phần có thứ tự cao là 252 + 227 và phần có thứ tự thấp là 226 - 1, nhưng khi mỗi thao tác được làm tròn trước thành độ chính xác gấp đôi mở rộng rồi đến độ chính xác gấp đôi, quy trình sẽ tạo ra giá trị cao . Số thứ hai chiếm 27 bit, vì vậy bình phương của nó không thể được tính chính xác với độ chính xác gấp đôi. Tất nhiên, vẫn có thể tính bình phương của số này với độ chính xác gấp đôi mở rộng, nhưng thuật toán kết quả sẽ không còn khả dụng cho các hệ thống đơn/kép. Ngoài ra, các bước sau trong thuật toán nhân chính xác bội giả định rằng tất cả các tích từng phần đã được tính toán với độ chính xác kép. Xử lý chính xác hỗn hợp các biến kép kép và mở rộng sẽ khiến việc triển khai trở nên đắt đỏ hơn đáng kể

Tương tự như vậy, các thuật toán di động để thêm nhiều số chính xác được biểu thị dưới dạng mảng các số chính xác kép có thể không thành công trong phép tính làm tròn hai lần. Các thuật toán này thường dựa trên một kỹ thuật tương tự như công thức tính tổng của Kahan. Như lời giải thích không chính thức về công thức tính tổng được đưa ra trên Errors In Summation gợi ý, nếu

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

sau đó trong hầu hết các phép tính,

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Cuối cùng, một số thuật toán thoạt nhìn có vẻ phụ thuộc vào việc làm tròn chính xác trên thực tế có thể hoạt động chính xác với phép làm tròn hai lần. Trong những trường hợp này, chi phí đối phó với việc làm tròn hai lần không nằm ở việc triển khai mà nằm ở việc xác minh rằng thuật toán có hoạt động như quảng cáo hay không. Để minh họa, ta chứng minh biến thể sau của Định lý 7

Định lý 7'

Proof

Giả sử không mất mát rằng m > 0. Đặt q = mn. Chia tỷ lệ theo lũy thừa hai, chúng ta có thể xem xét một cài đặt tương đương trong đó 252

Gọi e là lỗi làm tròn trong phép tính q, sao cho q = m/n + e và giá trị được tính toán q

Trong số học làm tròn hai lần, vẫn có thể xảy ra trường hợp q là thương được làm tròn chính xác (mặc dù nó thực sự đã được làm tròn hai lần), vì vậy. e. < 1/2 như trên. Trong trường hợp này, chúng tôi có thể kháng cáo các lập luận của đoạn trước miễn là chúng tôi xem xét thực tế rằng q

Cuối cùng, chúng ta còn lại để xem xét các trường hợp trong đó q không phải là thương được làm tròn chính xác do làm tròn hai lần. Trong những trường hợp này, chúng ta có. e. < 1/2 + 2-(d + 1) trong trường hợp xấu nhất, trong đó d là số bit thừa ở định dạng kép mở rộng. (Tất cả các hệ thống dựa trên mở rộng hiện có đều hỗ trợ định dạng kép mở rộng với chính xác 64 bit có nghĩa; đối với định dạng này, d = 64 - 53 = 11. ) Vì làm tròn hai lần chỉ tạo ra kết quả làm tròn không chính xác khi làm tròn thứ hai được xác định theo quy tắc làm tròn về số chẵn, nên q phải là một số nguyên chẵn. Do đó, nếu n có dạng 1/2 + 2-(k + 1), thì ne = nq - m là bội số nguyên của 2-k và

Nếu k

Nếu k

Bằng chứng trước cho thấy tích chỉ có thể làm tròn hai lần nếu thương thực hiện, và thậm chí sau đó, nó làm tròn thành kết quả đúng. Bằng chứng cũng chỉ ra rằng việc mở rộng lập luận của chúng ta để bao gồm khả năng làm tròn hai lần có thể là một thách thức ngay cả đối với một chương trình chỉ có hai phép tính dấu phẩy động. Đối với một chương trình phức tạp hơn, có thể không thể tính toán một cách có hệ thống các tác động của phép làm tròn hai lần, chưa kể đến các kết hợp tổng quát hơn của phép tính chính xác kép mở rộng và kép

Hỗ trợ ngôn ngữ lập trình cho độ chính xác mở rộng

Không nên dùng các ví dụ trước để gợi ý rằng bản thân độ chính xác mở rộng là có hại. Nhiều chương trình có thể được hưởng lợi từ độ chính xác mở rộng khi lập trình viên có thể sử dụng nó một cách có chọn lọc. Thật không may, các ngôn ngữ lập trình hiện tại không cung cấp đủ phương tiện để lập trình viên chỉ định thời điểm và cách sử dụng độ chính xác mở rộng. Để chỉ ra những hỗ trợ nào là cần thiết, chúng tôi xem xét các cách mà chúng tôi có thể muốn quản lý việc sử dụng độ chính xác mở rộng

Trong một chương trình di động sử dụng độ chính xác kép làm độ chính xác làm việc danh nghĩa của nó, có năm cách chúng ta có thể muốn kiểm soát việc sử dụng độ chính xác rộng hơn

1. Biên dịch để tạo mã nhanh nhất, sử dụng độ chính xác mở rộng nếu có thể trên các hệ thống dựa trên mở rộng. Rõ ràng hầu hết các phần mềm số không yêu cầu nhiều phép tính hơn là lỗi tương đối trong mỗi thao tác được giới hạn bởi "máy epsilon". Khi dữ liệu trong bộ nhớ được lưu trữ ở độ chính xác kép, epsilon của máy thường được coi là lỗi làm tròn tương đối lớn nhất ở độ chính xác đó, vì dữ liệu đầu vào (đúng hoặc sai) được cho là đã được làm tròn khi chúng được nhập và kết quả sẽ . Do đó, trong khi tính toán một số kết quả trung gian ở độ chính xác mở rộng có thể mang lại kết quả chính xác hơn, thì độ chính xác mở rộng là không cần thiết. Trong trường hợp này, chúng tôi có thể muốn trình biên dịch chỉ sử dụng độ chính xác mở rộng khi nó sẽ không làm chậm chương trình một cách đáng kể và nếu không thì sử dụng độ chính xác kép
2. Sử dụng định dạng rộng hơn gấp đôi nếu định dạng đó đủ nhanh và đủ rộng, nếu không thì sử dụng định dạng khác. Một số tính toán có thể được thực hiện dễ dàng hơn khi có độ chính xác mở rộng, nhưng chúng cũng có thể được thực hiện với độ chính xác kép chỉ với nỗ lực lớn hơn một chút. Xem xét tính toán định mức Euclide của một vectơ số chính xác kép. Bằng cách tính bình phương của các phần tử và tích lũy tổng của chúng ở định dạng kép mở rộng IEEE 754 với phạm vi số mũ rộng hơn, chúng ta có thể tránh được tình trạng tràn hoặc tràn quá sớm đối với các vectơ có độ dài thực tế. Trên các hệ thống dựa trên mở rộng, đây là cách nhanh nhất để tính định mức. Trên các hệ thống đơn/kép, một định dạng kép mở rộng sẽ phải được mô phỏng trong phần mềm (nếu một phần mềm được hỗ trợ) và việc mô phỏng như vậy sẽ chậm hơn nhiều so với việc chỉ sử dụng độ chính xác kép, kiểm tra các cờ ngoại lệ để xác định xem có xảy ra tràn hoặc tràn . Lưu ý rằng để hỗ trợ việc sử dụng độ chính xác mở rộng này, một ngôn ngữ phải cung cấp cả chỉ báo về định dạng có sẵn rộng nhất, tốc độ hợp lý, để chương trình có thể chọn phương pháp sử dụng và các tham số môi trường cho biết độ chính xác và phạm vi của từng định dạng . g. , rằng nó có phạm vi rộng hơn gấp đôi)
3. Sử dụng định dạng rộng hơn gấp đôi ngay cả khi nó phải được mô phỏng trong phần mềm. Đối với các chương trình phức tạp hơn ví dụ chuẩn Euclide, lập trình viên có thể chỉ muốn tránh viết hai phiên bản của chương trình và thay vào đó dựa vào độ chính xác mở rộng ngay cả khi nó chậm. Một lần nữa, ngôn ngữ phải cung cấp các tham số môi trường để chương trình có thể xác định phạm vi và độ chính xác của định dạng có sẵn rộng nhất
4. Không sử dụng độ chính xác rộng hơn; . Đối với các chương trình được viết dễ dàng nhất phụ thuộc vào số học chính xác kép được làm tròn chính xác, bao gồm một số ví dụ được đề cập ở trên, ngôn ngữ phải cung cấp cách để lập trình viên chỉ ra rằng không được sử dụng độ chính xác mở rộng, mặc dù có thể tính toán kết quả trung gian . (Các kết quả trung gian được tính toán theo cách này vẫn có thể phải làm tròn hai lần nếu chúng bị tràn khi lưu vào bộ nhớ. nếu kết quả của một phép toán số học trước tiên được làm tròn thành 53 bit có nghĩa, sau đó được làm tròn lại thành ít bit có nghĩa hơn khi nó phải được không chuẩn hóa, thì kết quả cuối cùng có thể khác với kết quả thu được bằng cách làm tròn chỉ một lần thành số không được chuẩn hóa. Tất nhiên, hình thức làm tròn kép này rất khó có thể ảnh hưởng xấu đến bất kỳ chương trình thực tế nào. )
5. Làm tròn kết quả chính xác cho cả độ chính xác và phạm vi của định dạng kép. Việc thực thi nghiêm ngặt độ chính xác kép này sẽ hữu ích nhất cho các chương trình kiểm tra phần mềm số hoặc bản thân số học gần giới hạn của cả phạm vi và độ chính xác của định dạng kép. Các chương trình kiểm tra cẩn thận như vậy có xu hướng khó viết theo cách di động; . Do đó, một lập trình viên sử dụng hệ thống dựa trên mở rộng để phát triển phần mềm mạnh mẽ phải có khả năng di động đối với tất cả các triển khai IEEE 754 sẽ nhanh chóng đánh giá cao khả năng mô phỏng số học của các hệ thống đơn/kép mà không cần nỗ lực phi thường

Không có ngôn ngữ hiện tại nào hỗ trợ tất cả năm tùy chọn này. Trên thực tế, một số ngôn ngữ đã cố gắng cung cấp cho lập trình viên khả năng kiểm soát việc sử dụng độ chính xác mở rộng. Một ngoại lệ đáng chú ý là ISO/IEC 9899. Ngôn ngữ lập trình 1999 - Tiêu chuẩn C, phiên bản mới nhất của ngôn ngữ C, hiện đang ở giai đoạn chuẩn hóa cuối cùng

Tiêu chuẩn C99 cho phép triển khai đánh giá các biểu thức ở định dạng rộng hơn định dạng thường được liên kết với loại của chúng, nhưng tiêu chuẩn C99 khuyến nghị sử dụng một trong ba phương pháp đánh giá biểu thức duy nhất. Ba phương pháp được đề xuất được đặc trưng bởi mức độ mà các biểu thức được "thăng cấp" thành các định dạng rộng hơn và việc triển khai được khuyến khích xác định phương pháp nào nó sử dụng bằng cách xác định macro tiền xử lý

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Sự kết hợp các tính năng được yêu cầu hoặc khuyến nghị bởi tiêu chuẩn C99 hỗ trợ một số trong năm tùy chọn được liệt kê ở trên nhưng không phải tất cả. Ví dụ: nếu một triển khai ánh xạ loại

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Tương tự như vậy, tiêu chuẩn C99 cung cấp các giải pháp cho một số vấn đề được minh họa bằng các ví dụ trong phần này nhưng không phải tất cả. Phiên bản tiêu chuẩn C99 của hàm

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Đoạn sau đây cho thấy một triển khai có thể

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Tất nhiên, để tìm ra giải pháp này, lập trình viên phải biết rằng biểu thức

     n = n/2

     n = n/2

     n = n/2

Thật trùng hợp, cách tiếp cận của tiêu chuẩn C99 để hỗ trợ tính di động giữa các hệ thống có khả năng số học số nguyên khác nhau gợi ý một cách tốt hơn để hỗ trợ các kiến ​​trúc dấu phẩy động khác nhau. Mỗi triển khai tiêu chuẩn C99 cung cấp tệp tiêu đề

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

     n = n/2

Hỗ trợ ngôn ngữ cho độ chính xác mở rộng có phức tạp như vậy không? . Tuy nhiên, các hệ thống dựa trên mở rộng đặt ra những lựa chọn khó khăn. chúng không hỗ trợ tính toán chính xác kép thuần túy cũng như tính toán chính xác mở rộng thuần túy hiệu quả như hỗn hợp của cả hai và các chương trình khác nhau yêu cầu các hỗn hợp khác nhau. Hơn nữa, không nên để việc lựa chọn thời điểm sử dụng độ chính xác mở rộng cho những người viết trình biên dịch, những người thường bị cám dỗ bởi các điểm chuẩn (và đôi khi được các nhà phân tích số nói thẳng ra) coi số học dấu phẩy động là "không chính xác vốn có" và do đó không xứng đáng cũng như không có khả năng. . Thay vào đó, sự lựa chọn phải được trình bày cho các lập trình viên và họ sẽ yêu cầu các ngôn ngữ có khả năng thể hiện sự lựa chọn của họ.

Sự kết luận

Những nhận xét ở trên không nhằm mục đích chê bai các hệ thống dựa trên mở rộng mà để vạch trần một số sai lầm, điều đầu tiên là tất cả các hệ thống IEEE 754 phải cung cấp kết quả giống hệt nhau cho cùng một chương trình. Chúng tôi đã tập trung vào sự khác biệt giữa các hệ thống dựa trên mở rộng và hệ thống đơn/kép, nhưng còn có sự khác biệt nữa giữa các hệ thống trong mỗi họ này. Ví dụ: một số hệ thống đơn/đôi cung cấp một lệnh duy nhất để nhân hai số và cộng số thứ ba chỉ với một lần làm tròn cuối cùng. Hoạt động này, được gọi là phép cộng-thêm kết hợp, có thể khiến cùng một chương trình tạo ra các kết quả khác nhau trên các hệ thống đơn/kép khác nhau và giống như độ chính xác mở rộng, nó thậm chí có thể khiến cùng một chương trình tạo ra các kết quả khác nhau trên cùng một hệ thống tùy thuộc vào việc . (Một phép cộng nhân hợp nhất cũng có thể làm hỏng quá trình tách của Định lý 6, mặc dù nó có thể được sử dụng theo cách không di động để thực hiện nhiều phép nhân chính xác mà không cần tách. ) Mặc dù tiêu chuẩn IEEE không lường trước được hoạt động như vậy, nhưng nó vẫn tuân thủ. sản phẩm trung gian được chuyển đến một "điểm đến" ngoài tầm kiểm soát của người dùng đủ rộng để giữ chính xác sản phẩm đó và tổng cuối cùng được làm tròn chính xác để khớp với điểm đến chính xác đơn hoặc kép

Ý tưởng rằng IEEE 754 quy định chính xác kết quả mà một chương trình nhất định phải cung cấp dù sao cũng rất hấp dẫn. Nhiều lập trình viên muốn tin rằng họ có thể hiểu hành vi của một chương trình và chứng minh rằng nó sẽ hoạt động chính xác mà không cần tham khảo trình biên dịch biên dịch nó hoặc máy tính chạy nó. Theo nhiều cách, hỗ trợ niềm tin này là một mục tiêu đáng giá cho các nhà thiết kế hệ thống máy tính và ngôn ngữ lập trình. Thật không may, khi nói đến số học dấu phẩy động, mục tiêu hầu như không thể đạt được. Các tác giả của các tiêu chuẩn IEEE biết điều đó và họ đã không cố gắng đạt được nó. Kết quả là, mặc dù gần như tuân thủ (hầu hết) tiêu chuẩn IEEE 754 trong toàn ngành công nghiệp máy tính, các lập trình viên của phần mềm di động vẫn phải tiếp tục đối phó với số học dấu chấm động không thể đoán trước.

Nếu các lập trình viên khai thác các tính năng của IEEE 754, họ sẽ cần các ngôn ngữ lập trình giúp dự đoán số học dấu phẩy động. Tiêu chuẩn C99 cải thiện khả năng dự đoán ở một mức độ nào đó với chi phí yêu cầu các lập trình viên viết nhiều phiên bản chương trình của họ, mỗi phiên bản cho một

     n = n/2