INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 1 91-02-11 pa WI !standard 04.05.05 (03) 91-02-11 AI-00889/00 !standard 04.05.05 (12) !editor Wichmann/Goodenough 90-12-21 !class pathology 90-02-11 (provisional classification) !status work-item 91-02-11 !status received 89-01-06 !topic INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) !summary 91-02-11 (DRAFT) For an integer type T, - the value of T'BASE'FIRST rem (-1) is zero. - the value of T'BASE'FIRST mod (-1) is zero. - the value of T'BASE'FIRST/(-(-1)) is T'BASE'FIRST. No exception is raised for these expressions. !question 91-02-11 (DRAFT) 4.5.5(3-4) defines the effect of the rem operator: Integer division and remainder are defined by the relation A = (A/B)*B + (A rem B) where (A rem B) has the sign of A and an absolute value less than the absolute value of B. According to the latter part of this definition, INTEGER'FIRST rem (-1) equals zero, since zero is the only integer whose value is less than the absolute value of -1. On the other hand, the specified relation requires the evaluation of INTEGER'FIRST/(-1), and this evaluation is allowed to raise NUMERIC_ERROR (or CONSTRAINT_ERROR; see AI-00387) for twos-complement machines since 4.5(7) says: The predefined operations on integer types either yield the mathematically correct result or raise the exception NUMERIC_ERROR. A predefined operation that delivers a result of an integer type (other than universal_integer) can only raise the exception NUMERIC_ ERROR if the mathematical result is not a value of the type. For a twos-complement machine, the value of -INTEGER'FIRST exceeds the value of INTEGER'LAST, so NUMERIC_ERROR can be raised. Is an implementation therefore required (or allowed) to raise NUMERIC_ERROR for INTEGER'FIRST rem (-1)? Is it required (or allowed) to return the value zero? Are implementations free to choose one of these alternatives? DRAFT DRAFT DRAFT INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 2 91-02-11 pa WI The same questions arise for INTEGER'FIRST mod (-1), since 4.5.5(5) says: The result of the modulus operation is such that A mod B) has the sign of B and an absolute value less than the the absolute value of B; in addition, for some integer value N, this result must satisfy the relation A = B*N + (A mod B) For twos-complement machines, when B is -1 and A is INTEGER'FIRST, N must have a value one greater than the value of INTEGER'LAST. Since this value cannot be represented as a value of type INTEGER, is INTEGER'FIRST mod (-1) allowed to raise NUMERIC_ERROR? Finally, 4.5.5(4) also says: Integer division satisfies the identity (-A)/B = -(A/B) = A/(-B) Consider the expression INTEGER'FIRST/(-1), which is allowed to raise NUMERIC_ERROR for twos-complement machines. Therefore, according to the above identity, since B is (-1) and since -(INTEGER'FIRST/(-1)) is allowed to raise NUMERIC_ERROR, is INTEGER'FIRST/(-(-1)) also allowed to raise NUMERIC_ ERROR? !recommendation 91-02-11 (DRAFT) Integer division and remainder are defined by the following mathematical relation A = (A/B)*B + (A rem B) where (A rem B) has the sign of A and an absolute value less than the absolute value of B. The result of the modulus operation is such that (A mod B) has the sign of B and an absolute value less than the absolute value of B; in addition, for some integer value N, this result must satisfy the mathematical relation A = B*N + (A mod B) Finally, integer division satisfies the mathematical identity (-A)/B = -(A/B) = A/(-B) !discussion 91-02-11 (DRAFT) The intention in using equations to specify the effect of integer division, mod, and rem was to interpret the equations in a mathematical sense. In particular, the identity in 4.5.5(4) was clearly intended in a mathematical sense since the identity is not a legal Ada expression. DRAFT DRAFT DRAFT INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 3 91-02-11 pa WI The effect of interpreting the equations in a mathematical sense is that the rem and mod operators yield the value zero when the second operand has the value -1. Similarly, the identity given in 4.5.5(4) has no effect on the interpretation of INTEGER'FIRST/(-(-1)). A survey of compilers from major vendors showed that A rem B and A mod B yields zero when A has the value T'BASE'FIRST (for integer type T) and the value of B is -1. Therefore there is no penalty in requiring that zero be returned for both rem and mod in these cases. !appendix 90-12-21 ***************************************************************************** !section 04.05 (07) Gary Morris 89-01-06 83-01256 !version 1983 !topic Raising NUMERIC_ERROR on remainder operations I have a question about the "rem" operation and the Ada rules that apply to it. Specifically: Is it acceptable to raise NUMERIC_ERROR for a "rem" (or "mod") operation when the operands are integer'first (-32768) and -1? Consider a machine with twos complement integer arithmetic, where the predefined integer type has a range that is symmetric around zero with an extra negative value (such as -32768..32767). The result of the operation (-32768 rem -1) has a valid mathematical result of 0 but the division operation (-32768/-1) used to compute the remainder yields a NUMERIC_ERROR (because the mathematical result of the division is 32768, outside the range of the type). Note that this problem only arises with these two values of the operands, all other values for either operand yield the desired result. In the RM 4.5/7, this operation may raise NUMERIC_ERROR only if the mathematical result is not a value of the type. Since the mathematical result (0) is a value for this type, RM 4.5/7 requires that no exception be raised. However, according to the RM 4.5.5/3-4, integer remainder is defined in terms of integer divide and multiply: > Since integer division and remainder are defined by the relation 3 > > A = (A/B)*B + (A rem B) 4 Or: A - (A/B)*B = (A rem B) With a 16 bit twos complement integer type, where A is -32768 and B is -1, the mathematical result of the division is 32768. This value is DRAFT DRAFT DRAFT INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 4 91-02-11 pa WI outside the range of the base type (range -32768..32767) and NUMERIC_ERROR is raised on divide. Since a divide is used on most all machines in the computation of remainder (divide instructions typically return both quotient and remainder) it makes sense for NUMERIC_ERROR to be allowed for "rem" (and "mod") when it is allowed for divide. To disallow NUMERIC_ERROR for this situation would require an explicit check of the operands on every remainder operation to see if they were 'first and -1. This seems an unreasonable overhead for an unusual case. A survey of three different Ada compilers, showed that all three are not in compliance with the RM 4.5/7 when performing of a "rem" or "mod" with the values of 'first and -1. The compilers tested were TeleSoft VAX/VMS Ada version 3.22, Sun Ada 1.3, and DEC VAX Ada 1.5. The two VAX compilers raised a NUMERIC_ERROR and the Sun compiler returned an incorrect result without raising an exception. I have an ACVC style test program that I used to test these compiler and would be willing to provide it if requested. Is it acceptable to raise NUMERIC_ERROR in this situation, even though the mathematical result of the "rem" (or "mod") is in the range of the integer type? ***************************************************************************** !section 04.05.05 (12) B Wichmann 90-08-15 83-01395 !version 83 !topic Meaning of INTEGER'FIRST rem (-1) The referenced paragraph defines a relationship between INTEGER division and remainder. However, in the case of a 2's complement machine, INTEGER'FIRST/(-1) overflows. It is therefore not clear if: a) INTEGER'FIRST rem (-1) should raise CONSTRAINT_ERROR (AI-00387), given that there is no appeal to 11.6 b) The result 0 should be produced. Paragraph 4.5.5(14) states that: INTEGER'FIRST rem (-1) = INTEGER'FIRST rem 1, which is clearly 0; and also: INTEGER'FIRST rem (-1) = -((-INTEGER'FIRST) rem (-1)), which clearly overflows. Paragraph 4.5.5(12) does not help since it clearly does not give all the cases in which NUMERIC_ERROR (CONSTRAINT_ERROR, AI-00387), can DRAFT DRAFT DRAFT INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 5 91-02-11 pa WI arise, since INTEGER'FIRST / (-1) will raise an exception on a 2's complement machine (ignoring 11.6). The Language Compatible Arithmetic Standard defines the result to be zero. (This is because the rounding function rndI gives a result in Z, not in the integer type.) Note that this problem did not arise in the NPL report DITC 167/90, since 'rem' is not defined in Pascal and the coding produced to implement this (function remI, page 23), made a special case of this. ***************************************************************************** !section 04.05.05 (03) J. Goodenough 91-02-11 !version 1983 !topic Minutes from September 1990 ARG meeting Brian Wichmann noted that if the operators in 4.5.5(3) are taken to be Ada operators rather than mathematical notation, the value INTEGER'FIRST REM (-1) is not defined by the reference manual. Wichmann suggested that Ada semantics ought to be consistent with the proposed Language-Compatible Arithmetic Standard (LCAS). LCAS calls for X REM (-1) to complete normally and return zero. This approach was approved unanimously in a straw vote. Wichmann will write an AI of class "pathology." ***************************************************************************** !section 04.05.05 (03) B Wichmann 90-12-21 83-01405 !version 83 !topic Meaning of INTEGER'FIRST rem (-1) The referenced paragraph defines a relationship between INTEGER division and remainder. However, in the case of a 2's complement machine, INTEGER'FIRST/(-1) overflows. It is therefore not clear if: a) INTEGER'FIRST rem (-1) should raise CONSTRAINT_ERROR (AI-00387), given that there is no appeal to 11.6 b) The result 0 should be produced. Paragraph 4.5.5(14) states that: INTEGER'FIRST rem (-1) = INTEGER'FIRST rem 1, which is clearly 0; and also: INTEGER'FIRST rem (-1) = -((-INTEGER'FIRST) rem (-1)), which clearly overflows. Paragraph 4.5.5(12) does not help since it clearly does not give all the cases in which NUMERIC_ERROR (CONSTRAINT_ERROR, AI-00387), can arise, since DRAFT DRAFT DRAFT INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 6 91-02-11 pa WI INTEGER'FIRST / (-1) will raise an exception on a 2's complement machine (ignoring 11.6). The Language Compatible Arithmetic Standard defines the result to be zero. (This is because the rounding function rndI gives a result in Z, not in the integer type.) Note that this problem did not arise in the NPL report DITC 167/90, since 'rem' is not defined in Pascal and the coding produced to implement this (function remI, page 23), made a special case of this. This issue was orginally combined with other cases in which NUMERIC_ERROR is raised in performing various operations (AI-00159). However, it has been decided that this issue should be separated out. The tentative conclusion of a discussion of this at the ARG meeting in September 1990 was that implementation should be allowed to raise at exception, although the language requires that 0 be produced. The rationale for this is that adding a performance penalty for this one case did not seem reasonable. Note that the situation with INTEGER'LAST mod (-1) is somewhat different since the wording in 4.5.5(5) conjectures an 'integer value N' which could imply that the value need not be of the appropriate integer type (which it is not in this case, due to overflow). Implementation may well use similar code sequences for rem and mod and therefore the fact that the wording in the RM is different is not so relevant to the resolution. Since then, the only compiler known to NPL which gave NUMERIC_ERROR has been amended to give 0. Hence the case for raising an exception seems rather weak. The following compilers give 0: VADS (Sun/3), VAX (DEC), XD-68000 and Alsys (IBM-PC). One vendor made a decision to add one machine instruction to ensure that 0 was produced. I conclude from the above that the ARG should reconsider the issue and make it a requirement that the result be 0. I do not agree to the issue being regarded as a pathology for two reasons. Firstly, I do not think the performance penalty is too high, and secondly making this a special case would adversely effect program proof tools. In practice, and implementation for which the performance penalty was high would invoke the 'incorrect' optimization by a mode switch, not used for validation. Extract from Minutes of September 1990 ARG meeting The Raising of CONSTRAINT_ERROR by REM and MOD Brian Wichmann noted that if the operators in 4.5.5(3) are taken to be Ada operators rather than mathematical notation, the value INTEGER'FIRST REM -1 is not defined by the reference manual. Wichmann suggested that Ada semantics ought to be consistent with the proposed Language-Compatible Arithmetic Standard (LCAS). LCAS calls for X REM -1 to complete normally and return zero. This approach was approved unanimously in a straw vote. Wichmann will write an AI of class "pathology." DRAFT DRAFT DRAFT