APPARATUS FOR PERFORMING MODAL INTERVAL CALCULATIONS BASED ON DECORATION CONFIGURATION

Abstract

Apparatus performs various modal interval computations, while accounting for various modal interval operand configurations that are not amenable to ordinary computational operations. Upon detecting an exponent field of all 1's, the apparatus adapts various conventions involving leading bits in the fraction field of the modal interval endpoints to return a result having a useful meaning.

Claims

1. Apparatus for calculating a first result modal interval dependent on a first modal interval, each said modal interval defined by first and second endpoints each comprising sign, fraction and exponent bit fields, said apparatus comprising: a) a first operand register for holding the first and second endpoints of the first modal interval, and for providing a first operand signal specifying the contents of the first modal interval endpoints' fields; b) a first analysis element for receiving the first operand signal, for creating a first truth table for the first endpoint and a second truth table for the second endpoint, each truth table including a sign bit (S) indicating the sign of the respective endpoint, a not-a-number bit (N) indicating whether the respective endpoint is Not-a-Number, an infinity bit (I) indicating whether the respective endpoint is infinity and a zero bit (Z) indicating whether the respective endpoint is zero; c) a first logic array for determining a classification from the first and second truth tables, the classification including an empty bit (E) and, optionally, a tracking decoration (T), wherein: when the first and second truth tables indicate that the first and second endpoints have the same sign and a value of infinity, the empty bit is 1 and the tracking decoration indicates an empty or non-empty restriction; when the first and second truth tables indicate that one of the first and second endpoints are not-a-number, the empty bit is 1 and the tracking decoration is the NaN decoration field from the not-a-number endpoint; when the first and second truth tables indicate that both of the first and second endpoints are not-a-number, the empty bit is 1 and the tracking decoration indicates an empty input restriction; otherwise the empty bit is 0 and the tracking decoration is not used; and, d) providing a result signal encoding the first result modal interval wherein: when the empty bit is 1, the first result modal interval is the first modal interval; and when the empty bit is 0, the first result modal interval is a result of a computation by a first computational element receiving the first operand signal and the first and second truth tables.

2. The apparatus of claim 1, wherein the first analysis element creates the first and second truth tables dependent on a preselected exponent field bit configuration in each of the first and second endpoints, and on a preselected fraction field configuration in each of the first and second endpoints.

3. The apparatus of claim 1 adapted for calculating a second result modal interval dependent on the first modal interval and on a second modal interval having the same structure as the first modal interval and having a third endpoint and a fourth endpoint, comprising: a) a second operand register for holding the third endpoint and the fourth endpoint of the second modal interval, and for providing a second operand signal specifying the contents of the second modal interval's endpoints' fields; b) a second analysis element for receiving the second operand signal, creating a third truth table for the third endpoint and a fourth truth table for the fourth endpoint; c) a second logic array for determining a classification from the third and fourth truth tables, the classification including an empty bit (E) and, optionally, a tracking decoration (T), wherein: when the third and fourth truth tables indicate that the third and fourth endpoints have the same sign and a value of infinity, the empty bit is 1 and the tracking decoration indicates an empty or non-empty restriction; when the third and fourth truth tables indicate that one of the third and fourth endpoints are not-a-number, the empty bit is 1 and the tracking decoration is the NaN decoration field from the not-a-number endpoint; when the third and fourth truth tables indicate that both of the third and fourth endpoints are not-a-number, the empty bit is 1 and the tracking decoration indicates an empty input restriction; otherwise the empty bit is and the tracking decoration is not used; d)-h) providing a result signal encoding the second result modal interval wherein: when the empty bit from the classification of the first and second truth tables is 1 and the empty bit from the classification of the third and fourth truth tables is 1, the second result modal interval is either the first modal interval or the second modal interval, whichever is associated with the tracking decoration of minimum value (see reference numeral 50); when the empty bit from the classification of the first and second truth tables is 1 and the empty bit from the classification of the third and fourth truth tables is 0, the second result modal interval is the first modal interval; when the empty bit from the classification of the first and second truth tables is 0 and the empty bit from the classification of the third and fourth truth tables is 1, the second result modal interval is the second modal interval; and when the empty bit from the classification of the first and second truth tables is 0 and the empty bit from the classification of the third and fourth truth tables is 0, the second result modal interval is a result of a computation by a second computational element receiving the first and second operands signals and the first, second, third, and fourth truth tables.

Description

DESCRIPTION OF THE FIGURES

[0030] FIG. 1 depicts the natural domain of the floor function, which is the entire real number line. The function is not continuous on its natural domain, however the restriction of the function to the interval X=[1,3/2] is continuous.

[0031] FIG. 2 is a visualization of modal intervals in the R.sup.2 plane. Points above the = line are proper modal intervals and points below this line are improper modal intervals. Points on the line are point-wise modal intervals.

[0032] FIG. 3 is a visualization of the inclusion (.Math.) and less-or-equal () relations for modal intervals B, C, D and E relative to modal interval A.

[0033] FIG. 4 depicts how the syntax tree of a real function implicitly defines a modal interval expression. Real operators are transformed into their modal interval extension and real variables into modal interval variables.

[0034] FIG. 5 defines the five tracking decorations of the present invention in TABLE 1 and the five static decorations of the present invention in TABLE 2. TABLE 3 is an alternate definition of the static decorations in TABLE 2. TABLE 4 defines bit encodings of tracking decorations in a NaN decoration field of an IEEE 754-2008 binary64 datum.

[0035] FIG. 6 is a Venn Diagram showing the logical relations between the five sets of tracking decorations of the present invention.

[0036] FIG. 7 is a Venn Diagram showing the logical relations between the five sets of static decorations of the present invention.

[0037] FIG. 8 depicts an IEEE 754-2008 interchange encoding for a binary64 datum. The NaN decoration field in bits 49 and 50 is not part of the IEEE 754-2008 standard and is defined solely for the sake of the present invention.

[0038] FIG. 9 is a logic diagram that defines a truth table consisting of Sign (S), NaN (N), Infinity (I) and Zero (Z) classification bits for a binary64 datum.

[0039] FIG. 10 depicts a modal interval datum [a.sub.1, a.sub.2], which is encoded into 128 bits as two binary64 datums a.sub.1 and a.sub.2.

[0040] FIG. 11 is a logic diagram that defines the Empty (E) bit and Tracking Decoration (T) of a modal interval datum.

[0041] FIG. 12 depicts a unary modal interval operation, which takes an operand [a.sub.1, a.sub.2] as input and produces a result [b.sub.1, b.sub.2].

[0042] FIG. 13 is a logic diagram for a unary modal interval operation using decorations.

[0043] FIG. 14 is a logic diagram for a modal interval negation operation.

[0044] FIG. 15 is a logic diagram for a modal interval operation.

[0045] FIG. 16 is a logic diagram for a restricted modal interval reciprocal operation.

[0046] FIG. 17 is a logic diagram for a modal interval sign operation.

[0047] FIG. 18 is a logic diagram for a modal interval absolute value operation.

[0048] FIG. 19 is a logic diagram for a modal interval square operation.

[0049] FIG. 20 is a logic diagram for a modal interval square root operation.

[0050] FIG. 21 is a logic diagram for a restricted modal interval square root operation.

[0051] FIG. 22 is a logic diagram for a modal interval exponential operation.

[0052] FIG. 23 is a logic diagram for a modal interval logarithm operation.

[0053] FIG. 24 is a logic diagram for a restricted modal interval logarithm operation.

[0054] FIG. 25 depicts a binary modal interval operation, which takes operands [a.sub.1, a.sub.2] and [b.sub.1, b.sub.2] as input and produces a result [c.sub.1, c.sub.2].

[0055] FIG. 26 is a logic diagram for a binary modal interval operation using decorations.

[0056] FIG. 27 is a logic diagram for a modal interval addition operation

[0057] FIG. 28 is a logic diagram for a modal interval subtraction operation.

[0058] FIG. 29 is a logic diagram for a modal interval multiplication operation.

[0059] FIG. 30 is a logic diagram for a modal interval division operation.

[0060] FIG. 31 is a logic diagram for a modal irate operation.

[0061] FIG. 32 is a logic diagram for a modal interval maximum operation.

[0062] FIG. 33 is a logic diagram for a modal interval meet operation.

[0063] FIG. 34 is a logic diagram for a modal interval join operation.

DESCRIPTION OF THE INVENTION

[0064] In furtherance of disclosing important features of the present invention and distinguishing it from the references of prior art, a preliminary overview of related concepts and prior art work is in order.

Natural Domains and Continuity

[0065] In the realm of pure mathematics, operations on real numbers are functions that have a natural domain. For example, the square root of a negative real number is not defined, so the natural domain of the square root operation is the set of all non-negative real numbers. Division by zero is also not defined, so the natural domain of the reciprocal operation is the set of all non-zero real numbers. And so on for each contemplated operation. In other words, whenever the input to an operation is not an element of the natural domain of the operation, the operation is not defined.

[0066] Continuity is another important property of functions of real numbers. Formal definitions of a continuous function are well-known in the prior art and can be given in terms of sequences or limits of the function. Informally, if a function is continuous then any time a sequence converges in the domain, the image of the sequence in the range also converges. In other words, one could either take the limit first, and then apply the function, or apply the function first, and then take the limits.

[0067] Even more particularly, if : R.sup.n.fwdarw.R is a function that maps n-dimensional real vectors R.sup.n to real numbers R and D.sub..Math.R.sup.n is the natural domain of , then for any X.Math.D.sub., the property of continuity may be further defined in terms of the restriction of on X. In this case, the only relevant aspect of the continuity property is with respect to the portions of the function that are restricted to the domain X, wherein X is a subset of the natural domain D.sub. of the function. For example, consider the function floor(x): R.fwdarw.R depicted in FIG. 1 which rounds the real number x to the closest integer n such that nx. The floor function is defined for any real number x. So the natural domain of the function is the entire real number line. However, the function is not continuous on its natural domain. This is because, for example, if x=1 there is no sequence or limit from the left of x=1 that converges to (x)=1. However, if the restriction of the floor function to the interval X=[1, 3/2] is instead considered, then the floor function is continuous on X because there is no xX such that x<1 and this means there can be no sequence or limit from the left of x=1.

[0068] The restriction of a function to X can be continuous if and only if X is also a subset of the natural domain of the function. For example, the natural domain of the square root operation is the set of all non-negative real numbers. So the restriction of the square root operation to X=[16, 4] cannot be continuous because there are elements of X=[16, 4] which do not belong to the natural domain of the operation and for which the operation is not defined. In other words, X in this case is not a subset of the natural domain of the operation.

[0069] Because the empty set () is a subset of every set, it is also a subset of all natural domains of all functions. The restriction of a function to the empty set must therefore be contemplated. As it turns out, the restriction of any function to the empty set X= is always defined and continuous. This is perhaps a little counterintuitive, but nonetheless mathematically correct. Formal mathematical reasoning to prove this is well known in the prior art.

Modal Intervals

[0070] The present invention is concerned with modal interval arithmetic and modal interval analysis. In particular, the present invention is concerned with an improved system and method of detecting exceptional conditions in modal interval operations. The prior notions of a real function, the natural domain of a real function, and the restriction of a real function to a subset of the natural domain of the function are therefore lifted into the topic of modal intervals.

[0071] For the purposes of the present invention, a modal interval is defined as an ordered pair [a, b] such that a and b are real numbers or signed infinities. However, the two pairs [, ] and [+, +] are excluded. Note that no restriction ab is required.

[0072] The set-theoretic interpretation of a modal interval is defined as

Set([a, b])={xR:min(a, b)xmax(a, b)}.

and the notation x [a, b] may be used as an abbreviation for x Set([a, b]). The empty set () is not a modal interval, however Set()=.

[0073] A closed interval includes all of its limit points. Every modal interval [a, b] is a closed interval. If both a and b are real numbers, the modal interval is bounded. If a modal interval is not bounded, then at least one of the endpoints is or + and the modal interval still contains all of its limit points but not all of its endpoints. Modal intervals of the form

[, +], [, b], [a, +], [+, b], [a, ] and [+, ]

are therefore understood to be unbounded. Despite the use of square brackets, infinity is never an element of any modal interval, and

[, ] and [+, +]

are by definition not modal intervals.

[0074] A modal interval [a, b] is called proper if ab. The modal interval is called improper if ab. It is called a point or a point-wise modal interval if a=b. Note that a point-wise modal interval is also a proper and an improper modal interval at the same time.

[0075] The set of all bounded modal intervals can be visualized as points in the R.sup.2 plane, where canonical abscissa and ordinate are defined respectively as the left and right bound of a modal interval [a, b], i. e.,

([a, b])=a and ([a, b])=b.

[0076] FIG. 2 is such a visualization. Points above the = line are proper modal intervals and points below this line are improper modal intervals. Points on the line are point-wise modal intervals. It should be noted the subset of bounded modal intervals visualized in the figure is the famous set known in the prior art as the Kaucher intervals. Also, the subset of the Kaucher intervals on or above the = line is the famous set of classic intervals popularized in the late 1960's by Ramon E Moore. The set of classic intervals does not include any improper intervals.

[0077] As of this date, the subset of bounded and unbounded proper modal intervals is the set of intervals supported in the working draft of the IEEE Standard for Interval Arithmetic. That standard is currently under development by the P1788 Working Group committee at the time of this writing and does not provide any provision for bounded or unbounded improper intervals. The present invention therefore contemplates the broadest set of intervals as it is the only one that consists of a set wherein each element of the set may be bounded or unbounded, proper or improper,

[0078] A predicate is a Boolean function, and a proposition is a predicate wherein each variable is universally () or existentially () quantified.

[0079] The modal quantifier Q of a modal interval [a, b] quantifies a real variable x by the definition

[0080] Q(x, [a, b])=if a<b then x Set([a, b]) else x Set([a, b]).

[0081] The modal operators are

Dual([a, b])=[b, a],

Prop([a, b])=[min(a, b), max(a, b)],

Impr([a, b])=[max(a, b), min(a, b)],

and the corresponding modal quantifiers D, E and U are defined as

D(x, [a, b])=Q(x, Dual([a, b])),

E(x, [a, b])=Q(x, Prop([a, b])),

U(x, [a, b])=Q(x, Impr([a, b])).

With the modal quantifiers Q, D, E and U it is possible to form propositions with modal intervals. For example, if A and B are modal intervals then the inclusion (.Math.) relation is

A.Math.BD(a, A)Q(b, B): a=b,

and the less-or-equal () relation is

ABU(a, A)E(b, B): ab and U(b, B)E(a, A): ab.

[0082] FIG. 3 is a geometric visualization of these modal interval relations in the R.sup.2 plane. The inclusion and less-or-equal relations are shown for modal intervals B, C, D and E relative to the modal interval A.

[0083] If x is a real number, the rounding operators (x) and (x) are digital approximations of x such that the relations

(x)x and (x)x

are always true. For any modal interval [a, b],

Inn([a, b])=[(a), (b)] and Out([a, b])=[(a), (b)]

are the inner and outer digital roundings, respectively of [a, b].

[0084] The inner and outer digital roundings are universally possible for any digital scale and satisfy the property

Inn([a, b]).Math.[a, b].Math.Out([a, b])

such that the equivalence

Inn([a, b])=Dual(Out(Dual([a, b])))

makes unnecessary the implementation of the inner rounding.

Decorations and Property Tracking

[0085] A decoration is a mathematical property of a real function restricted to the domain of its modal interval inputs. Decorations provide a framework for detecting exceptional conditions such as out-of-domain arguments or non-continuous functions.

[0086] Looking at the syntactic tree for a real function, where the nodes are operators, the leaves are variables, and branches define the domain of each operator, the real function can be operationally extended to a modal interval expression by using the computational program implicitly defined by the syntactic tree of the real function. This is accomplished by transforming all of the real operators into their modal interval extension and all of the real variables into modal interval variables.

[0087] FIG. 4 is an example that shows how the syntax tree of the real function

(x, y)=y/sqrt((1x)*(1+x))

implicitly defines a modal interval expression. Real operators and variables 12 are respectively transformed into their modal interval counterparts 15. Evaluation of the expression begins at the leafs of the tree, where variables are propagated up the branches to the operations. The operations accept the variables as operands, perform an operation and generate a result. The result of each operation is then propagated up the branches into other operations until all nodes in the tree have been evaluated and a final result is propagated to the root of the tree.

[0088] The present invention makes a distinction between two types of decorations. A static decoration is the absolute mathematical truth about the restriction of an individual operation to the domain of its modal interval inputs. A tracking decoration, on the other hand, is a mathematical implication that is obtained for a modal interval expression by propagating static decorations in the expression tree up the branches and to the root. The method used to propagate static decorations through an expression tree in order to obtain a tracking decoration is called property tracking.

[0089] TABLE 1 in FIG. 5 defines the five (5) tracking decorations EIN, DAC, DEF, GAP and NDF of the present invention. If :R.sup.n.fwdarw.R is a real function and X is an n-dimensional modal interval box, each tracking decoration is a set whose elements are the (, X) pairs which satisfy the stated mathematical property about the restriction of on Set(X). Furthermore, whenever X is the empty set the (, X) pair is an element of EIN, otherwise the (, X) pair must be an element of another decoration.

[0090] FIG. 6 is a Venn Diagram showing the logical relations between the five sets of tracking decorations. The five tracking decorations form the inclusion relations

EIN.Math.DAC.Math.DEF.Math.GAPNDFEIN

Note that EIN is a subset of all tracking decorations and GAP is a superset of all tracking decorations.

[0091] For example, if is the square root operator and X=[1, 4] then for this particular (, X) pair the restriction of on X is defined and continuous. Since X is not empty, the (, X) pair cannot be an element of EIN. Additionally, the (, X) pair cannot be an element of NDF because in this case (X) is not empty, either. However, if X is the empty set then the (, X) pair is an element of EIN, and since EIN is a subset of all tracking decorations the (, X) pair is also an element of DAC, DEF, GAP and NDF.

[0092] An important note should be made regarding the prior art as it pertains to decorations. A draft of the IEEE Standard for Interval Arithmetic, which is under development at the time of this writing, contains a decoration system that was at least partially conceived by the applicant of the present invention. That decoration system has some common characteristics to the decoration system of the present invention, such as DEF and DAC decorations. However, there are some important differences, namely the absence of an EIN decoration as well as the inclusion of several other decorations not defined in the present invention such as ILL (ill-formed), COM (a common interval) and BND (a bounded interval). Applicant's white paper entitled Decorations as State Machine provides rationale why these competing decoration systems are unnecessary or insufficient for reliable interval computations and how the unique decoration system of the present invention overcomes those issues.

[0093] TABLE 2 in FIG. 5 presents the five (5) static decorations ein, dac, def, gap and ndf of the present invention. Note that static decorations have the same names as tracking decorations, but the tracking decorations are uppercase and the static decorations are lowercase.

[0094] For any (, X) pair, the notation S(, X) indicates which static decoration the (, X) pair is an element of as a function of TABLE 2. If has n operands, the notation S(, X) is shorthand for S(, X.sub.1, X.sub.2, . . . , X.sub.n).

[0095] If : R.sup.n.fwdarw.R is a real function and D.sub..Math.R.sup.n is the natural domain of , and if X is an n-dimensional modal interval box, then TABLE 3 in FIG. 5 is an alternate definition of S(, X) that defines the same sets as TABLE 2 in FIG. 5.

[0096] FIG. 7 is a Venn Diagram showing the logical relations between the five sets of static decorations. While the tracking decorations in TABLE 1 of FIG. 5 partition the universe of all (; X) pairs into a hierarchical arrangement of nested sets (c. f. FIG. 6), the static decorations in TABLES 2-3 of FIG. 5 partition the universe of all (, X) pairs into five disjoint sets (c. f. FIG. 7).

[0097] For example, if is the square root operation and X.sub.1=[2, 4], X.sub.2=[1, 1] and X.sub.3=[4, 2] then S(, X.sub.1)=dac because Set(X.sub.1) is a nonempty subset of D.sub. and the restriction of on X.sub.1 is continuous; S(, X.sub.2)=gap because Set(X.sub.2) is not a subset of D.sub. but the intersection of Set(X.sub.2) and D.sub. is nonempty; and S(, X.sub.3)=ndf because X.sub.3 is not empty but the intersection of Set(X.sub.3) and D.sub. is empty.

[0098] Property tracking is the method used to propagate static decorations through an expression tree in order to obtain a tracking decoration. To facilitate this method, the notion of a decorated interval is contemplated. A decorated interval is a pair (X, D) that consists of a modal interval X and a tracking decoration D. The empty set is not an interval, however the notion of a decorated empty set (, D) is also contemplated.

[0099] The method of property tracking begins with initialization. Each modal interval variable X.sub.1, X.sub.2, . . . , X.sub.n in the leafs of the expression tree is promoted to a decorated interval (X.sub.1, DAC), (X.sub.2, DAC), . . . , (X.sub.n, DAC). If any variable in a leaf of the expression tree is an empty set, then the empty variable is promoted to a decorated empty set (, EIN). Similarly, if any variable in a leaf of the expression tree is [+, +]or [, ], then the variable is promoted, respectively, to ([+, +], GAP) or ([, ], GAP).

[0100] The decorated variables are then propagated up the branches of the expression tree to the operations. The operations accept the decorated variables as operands, perform an operation and generate a decorated result. For each operation, if :R.sup.n.fwdarw.R is the real function and

(X.sub.i, D.sub.i)=((X.sub.1, D.sub.1), (X.sub.2, D.sub.2), . . . , (X.sub.n, D.sub.n)

are the decorated internal operands of , then the decorated result of the operation has the tracking decoration

T(, (X.sub.i, D.sub.i))=min{S(, X.sub.1, X.sub.2, . . . , X.sub.n), D.sub.1, D.sub.2, . . . , D.sub.n}.

[0101] In other words, the decorated result of the operation has a tracking decoration which is the minimum element of a set formed by the union of the static decoration S(, X.sub.1, X.sub.2, . . . , X.sub.n) of the operation and the decorations D.sub.1, D.sub.2, . . . , D.sub.n of the operands.

[0102] For the sake of determining the minimum element of a set of decorations, the decorations are linearly ordered

ndf/NDF<gap/GAP<def/DEF<dac/DAC<ein/EIN

[0103] The decorated result of each operation is then propagated up the branches into other operations. The procedure is repeated until all nodes in the tree have been evaluated and a final decorated result is propagated to the root of the tree.

Digital Encodings of Modal, Intervals and Decorations

[0104] Inside a computer, the endpoints of a modal interval may be represented by elements of a digital scale. In a preferred embodiment of the present invention, the digital scale conforms to the binary64 interchange format encoding of IEEE 754-2008. For the sake of discourse, only the binary64 encoding will be explained or considered in the rest of this document. However, the use of other digital scales or interchange format encodings as it pertains to the present invention should be obvious.

[0105] A binary64 floating-point datum is 64 bits of information partitioned into sign, exponent and fraction fields as shown in register 20 of FIG. 8. The fraction field is in bits 0 to 51; the exponent field is in bits 52 to 62; and the sign field is the most significant bit 63. The floating-point data represented by this encoding is: [0106] Zero. If the exponent and fraction are zero, then the floating-point data is a positive or negative zero +0 or 0 when the sign bit is 0 or 1, respectively. [0107] Non-zero finite number. If the exponent and fraction are not zero and the exponent bits are not all 1, then by definition the floating-point data is a positive or negative non-zero finite number when the sign bit is 0 or 1, respectively. [0108] Infinity. If the exponent bits are all set to 1 and the fraction is zero, then the floating-point data is + or when the sign bit is 0 or 1, respectively. The infinities are the maximum numbers that can be represented in floating-point format. Negative infinity is less than any finite number and positive infinity is greater than any finite number. [0109] NaN (Not-a-Number). If the exponent bits are all set to 1 and the fraction is not zero, then the floating-point data is a non-number that lies outside the range of representable floating-point numbers, regardless of the sign bit. If bit 51 is set to 1, then the NaN is quiet (QNaN); otherwise the NaN is signaling (SNaN). For the purposes of the present invention, bits 49 to 50 are the NaN decoration field. The NaN decoration field is not part of the IEEE 754-2008 standard and is defined solely for the sake of the present invention.

[0110] A binary64 datum may be associated with a truth table 23 consisting of a set of classification bits as depicted in FIG. 9. The classification bits consist of a Sign (S), NaN (N), Infinity (I) and Zero (Z) bit. Bit 63 of the binary64 datum is copied to the Sign bit. The NaN, Infinity and Zero bits are set to 0 or 1 depending on the combined value of the exponent and fraction of the binary64 datum. If the combined value is greater than 0x7FF0000000000000, then the NaN bit is set to 1; if the combined value is equal to 0x7FF0000000000000, then the Infinity bit is set to 1; if the combined value is equal to zero, then the Zero bit is set to 1; otherwise the respective NaN, Infinity and. Zero bits are set to 0 and the binary64 datum is a positive or negative non-zero finite number.

[0111] If x is a floating-point datum, then S(x), N(x), I(x) and Z(x) arc notations used in this document to represent the respective values of the Sign, NaN, Infinity and Zero classification bits of truth table 23.

[0112] If bit 51 of a NaN is set to 1, then the NaN is quiet (QNaN); otherwise the NaN is signaling (SNaN). If the NaN is signaling, at least one other fraction bit of the NaN must be set to 1 to distinguish the NaN from an infinity. The difference between a quiet and signaling NaN is for the sake of compatibility with IEEE 754-2008 standard interchange format encoding. However, the present invention does not require signaling NaN operations.

[0113] Bits 0 to 50 are the NaN payload. All bits of the payload may be set to any value so long as the entire fraction field of a NaN does not become zero. The preferred embodiment of the present invention may use bits 49 to 50 of a NaN payload as a NaN decoration field to encode a representation of a tracking decoration.

[0114] If x is a NaN, then T(x) is the representation of a tracking decoration encoded within the NaN decoration field of x as depicted in TABLE 4 of FIG. 5. The tracking decoration EIN has no designated encoding within the NaN decoration field. The reason for this will be shown in the following parts of the document.

[0115] If n is the representation of a tracking decoration, then NaN(n), QNaN(n) and SNaN(n) are notations used in this document to represent the respective encodings of a NaN, quiet NaN or signaling NaN when the bits of the decoration field are set to the corresponding value of n as depicted in TABLE 4 of FIG. 5.

[0116] A modal interval datum [a.sub.1, a.sub.2] may be encoded into 128 bits as two binary64 datums a.sub.1 and a.sub.2 as illustrated in register 27 of FIG. 10. If a.sub.1 or a.sub.2 is a NaN, or if a.sub.1 and a.sub.2 are infinities with the same sign, then the 128-bit encoding represents non-interval data.

[0117] All non-interval data is an encoding of a decorated empty set.

[0118] If a.sub.1 and a.sub.2 are binary64 datums that do not represent a NaN, and if n is a representation of one of the tracking decorations DAC, DEF, GAP or NDF (see TABLE 1 in FIG. 5) encoded in a NaN decoration field as depicted in TABLE 4 of FIG. 5, then a decorated empty set (, n) is encoded by any non-interval data of the form

[.sub.1, NaN(n)] or [NaN(n), .sub.2].

[0119] Any such encoding of a decorated empty set (, n) may be provided as input to an operation of the present invention, and a canonical encoding

[+0, QNaN(n)] or [QNaN(n), +0]

may be provided as a result of an operation which produces a decorated empty set as output.

[0120] Non-interval data of the form

[NaN, NaN]

is an encoding of the decorated empty set (, EIN), and non-interval data of the form

[, ] or [+, +]

is an encoding of the decorated empty set (, GAP)

[0121] FIG. 11 shows how a modal interval datum [a.sub.1, a.sub.2] is classified by an Empty (E) bit and a representation of a Tracking Decoration (T). The classification 33 is a function of truth tables each consisting of the Sign (S), NaN (N) and Infinity (I) bits, respectively, of the binary64 datums a.sub.1 and a.sub.2, as well as the respective NaN decoration field of a.sub.1 or a.sub.2, if either a.sub.1 or a.sub.2 is a NaN. The logic diagram 30 computes the classification 33 according to the following specifications.

[0122] The Empty bit in FIG. 11 is set to 1 if a.sub.1 and a.sub.2 are both infinities with the same sign or if a.sub.1 or a.sub.2 is a NaN; otherwise the Empty bit is set to 0. If a.sub.1 and a.sub.2 are infinities with the same sign, the Tracking Decoration is GAP; if a.sub.1 is a NaN and a.sub.2 is not, the Tracking Decoration is a representation of the NaN decoration field from a.sub.1; if a.sub.2 is a NaN and a.sub.1 is not, the Tracking Decoration is a representation of the NaN decoration field from a.sub.2; otherwise the Tracking Decoration is EIN. Strictly speaking, the Tracking Decoration has no meaning unless the Empty bit is set to 1. If the Empty bit is 0, the modal interval datum is a bounded or unbounded modal interval and the Tracking Decoration is not used.

[0123] If [a.sub.1, a.sub.2] is a modal interval datum, then E(a.sub.1, a.sub.2) and T(a.sub.1, a.sub.2) are notations used in this document to represent the respective values of the Empty bit and the Tracking Decoration.

Modal Interval Operations with Decorations

[0124] The present invention provides an improved system and method for reliable and efficient modal interval operations using decorations. The preferred embodiment of the present invention is an arithmetic functional unit (AFU) as depicted in applicant's U.S. Pat. No. 7,949,700 entitled Modal Interval Processor. Modal interval operand and result signals for the AFU are digitally encoded using the methods described in the previous section of this document entitled Digital Encodings of Modal Intervals and Decorations.

[0125] As will be shown subsequently for select modal interval operations, the result of a modal interval operation is typically obtained by performing a floating-point calculation on select endpoints of the modal interval operands. Because floating-point calculations are often inexact, the present invention requires the rounding operators (x) and (x) to ensure modal interval results obey the outer digital rounding of modal intervals.

[0126] FIG. 12 shows a unary modal interval operation for example computes in a functional element 36. Element 36 may comprise one or more sub-elements and may be implemented as hardware, firmware or software. Element 36 takes an operand [a.sub.1, a.sub.2] held in register 27 as input and produces a result [b.sub.1, b.sub.2] held in a result register 39.

[0127] FIG. 13 is a more detailed logic diagram of FIG. 12. A truth table 48 specifies the value in result register 39. The truth table is a function of the Empty (E) bit 42 associated with operand 27. A truth table value of 0 selects the computation function associated with the particular operation. The other truth table value specifies the result 39 is a copy of operand 27. Therefore, if [a.sub.1, a.sub.2] is an encoding of non-interval data, i.e., if [a.sub.1, a.sub.2] is an encoding of a decorated empty set, then the operand [a.sub.1, a.sub.2] is the result of the operation. Otherwise [a.sub.1, a.sub.2] is an encoding of a bounded or unbounded modal interval and the result is defined separately for each operation.

[0128] FIGS. 14-24 depict the result of several unary modal interval operations after a determination has been made that the operand [a.sub.1, a.sub.2] in FIG. 13 is an encoding of a bounded or unbounded modal interval.

[0129] FIG. 14 is a logic diagram for a modal interval negation operation. The operation effectively multiplies the modal interval by 1. Since negation of floating-point numbers is exact, the modal interval negation operation is exact and requires no rounding operators.

[0130] FIG. 15 is a logic diagram for a modal interval reciprocal operation. The operation is defined if and only if a.sub.1 and a.sub.2 are both non-zero numbers with the same sign, otherwise the result of the operation is a decorated empty set. If a.sub.1 and a.sub.2 are both zero, the empty set is decorated with NDF; otherwise the empty set is decorated with GAP.

[0131] FIG. 16 is a logic diagram for a restricted modal interval reciprocal operation. The operation silently removes zero from the input of the operation. Unlike the modal interval reciprocal operation in FIG. 15, the operand [a.sub.1, a.sub.2] may have one endpoint that is zero.

[0132] FIG. 17 is a logic diagram for a modal interval sign operation. The operation is defined for the entire real number line. However, the operation is continuous if and only if a.sub.1 and a.sub.2 are both strictly positive, both strictly negative or both zero. If the operation is not continuous, the result is an encoding of the decorated empty set (, DEF).

[0133] FIG. 18 is a logic diagram for a modal interval absolute value operation. Since absolute value of a floating-point number a.sub.1 or a.sub.2 is exact, the modal interval absolute value operation is exact and requires no rounding operators.

[0134] FIG. 19 is a logic diagram for a modal interval square operation.

[0135] FIG. 20 is a logic diagram for a modal interval square root operation. The operation is not defined if a.sub.1 or a.sub.2 is a negative non-zero number. In conformance to the IEEE 754-2008 standard, this allows 0 to be an element of the natural domain of the operation. If a.sub.1 or a.sub.2 is a negative non-zero number, the result of the operation is a decorated empty set. If a.sub.1 and a.sub.2 are both negative non-zero numbers, the empty set is decorated with NDF; otherwise the empty set is decorated with GAP.

[0136] FIG. 21 is a logic diagram for a restricted modal interval square root operation. The operation silently removes negative non-zero numbers from the input of the operation. Unlike the modal interval square root operation in FIG. 20, the operand [a.sub.1, a.sub.2] may have one negative non-zero number as an endpoint, so long as a.sub.1 and a.sub.2 are not both negative non-zero numbers.

[0137] FIG. 22 is a logic diagram for a modal interval exponential operation.

[0138] FIG. 23 is a logic diagram for a modal interval logarithm operation. The operation is defined if and only if a.sub.1 and a.sub.2 are both non-zero positive numbers. If a.sub.1 or a.sub.2 is less-or-equal to zero, the result of the operation is a decorated empty set. If a.sub.1 and a.sub.2 are both less-or-equal to zero, the empty set is decorated with NDF; otherwise the empty set is decorated with GAP.

[0139] FIG. 24 is a logic diagram for a restricted modal interval logarithm operation. The operation silently removes negative numbers and zero from the input of the operation. Unlike the modal interval logarithm operation in FIG. 23, the operand [a.sub.1, a.sub.2] may have one endpoint less-or-equal to zero, as long as a.sub.1 and a.sub.2 are not both less-or-equal to zero.

[0140] FIG. 25 shows a binary modal interval operation for example computes in a functional element 37. Element 37 may comprise one or more sub-elements and may be implemented as hardware, firmware or software. Element 37 takes operands [a.sub.1, a.sub.2] and [b.sub.1, b.sub.2] held respectively in registers 27 and 28 as input and produces a result [c.sub.1, c.sub.2] held in a result register 29.

[0141] FIG. 26 is a more detailed logic diagram of FIG. 25. A comparator 44 receives the tracking decoration bits derived from the operands 27 and 28 and then provides a 1 output when the three tracking bits T(a.sub.1, a.sub.2) are numerically larger than the three tracking bits T(b.sub.1, b.sub.2), and a 0 output otherwise. Logic elements 50 produce a truth table 58 that specifies the value in result register 29. A truth table value of 0 0 selects the computation function associated with the particular operation. A truth table value of 1 1 selects a value [d.sub.1, d.sub.2] produced by multiplexing operands 27 and 28 based on the output of comparator 44. The other truth table values specify the result defined for that truth table value. The logic elements 50 are a function of the Empty (E) bit and Tracking Decoration (T) pairs 42 and 43 associated respectively with operands 27 and 28. If [a.sub.1, a.sub.2] or [b.sub.1, b.sub.2] is an encoding of non-interval data, i. e., if [a.sub.1, a.sub.2] or [b.sub.1, b.sub.2] is an encoding of a decorated empty set, the result of the operation is one of the operands [a.sub.1, a.sub.2] or [b.sub.1, b.sub.2]. If both operands are decorated empty sets, there the operand with the minimum Tracking Decoration is the result, taking care to return operand [a.sub.1, a.sub.2] in the event both operands are decorated empty sets with the same Tracking Decoration; if only one operand is a decorated empty set, then the operand which is the decorated empty set is the result of the operation; otherwise [a.sub.1, a.sub.2] and [b.sub.1, b.sub.2] are both encodings of a bounded or unbounded modal interval and the result is defined differently for each operation.

[0142] FIGS. 27-34 depict the result of several binary modal interval operations after a determination has been made that the operands [a.sub.1, a.sub.2] and [b.sub.1, b.sub.2] in FIG. 26 are both encodings of a bounded or unbounded modal interval.

[0143] FIG. 27 is a logic diagram for a binary modal interval addition operation. The operation is not defined if a.sub.1+b.sub.1 or a.sub.1+b.sub.2 is a sum of infinities of opposite sign or if the sums a.sub.1+b.sub.1 and a.sub.2+b.sub.2 are infinities of the same sign. If the operation is not defined, the result is an encoding o the decorated empty set (, GAP).

[0144] FIG. 28 is a logic diagram for a binary modal interval subtraction operation. The operation is not defined if a.sub.1b.sub.2 or a.sub.2b.sub.1 is a difference of infinities of the same sign or if the differences a.sub.1b.sub.2 and a.sub.2+b.sub.1 are infinities of the same sign. If the operation is not defined, the result is an encoding of the decorated empty set (, GAP).

[0145] FIG. 29 is a logic diagram for a binary modal interval multiplication operation. If a.sub.1, a.sub.2, b.sub.1 or b.sub.2 is an infinity or a zero, the result of the operation may require a floating-point multiplication of an infinity and a zero. According to the IEEE 754-2008 standard, a floating-point multiplication of an infinity and a zero is an undefined operation and may return a NaN. The modal interval multiplication operation deviates from this convention and instead defines the floating-point multiplication of an infinity and a zero to be

()(0)=(0)()=+0

()(+0)=(+0)()=0

(+)(0)=(0)(+)=0

(+)(0)=(+0)(+)=+0

according to applicant's U.S. Pat. No. 8,204,926 entitled Reliable and Efficient Modal Interval Arithmetic Operations. The modal interval multiplication operation is therefore always defined so long as the operands [a.sub.1, a.sub.2] and [b.sub.1, b.sub.2] are bounded or unbounded modal intervals.

[0146] FIG. 30 is a logic diagram for a binary modal interval division operation.

[0147] FIGS. 31-34 are logic diagrams, respectively, for the binary modal interval lattice operations minimum, maximum, meet and join. Since the minimum and maximum of floating-point numbers is exact, all of the lattice operations are exact and require no rounding operators. It is possible the minimum and maximum operations may produce a result which is a representation of the decorated empty set (, GAP), encoded as [, ] for the minimum operation and [+, +] for the maximum operation.