Research on Division and Remainder of Signed Integers

Division and remainder of signed integers – Chen Shuo.

Recently, while researching the conversion from integers to strings, I read Matthew Wilson’s series of articles titled Efficient Integer to String Conversions. (Search conversions at http://synesis.com.au/publications.html.) His cleverness lies in using a symmetric digits array to handle the boundary conditions for negative number conversions (the range of positive and negative integers in binary’s two’s complement representation is asymmetric). The code is roughly as follows, rewritten:

1. const char* convert(char buf[], int value)

2. {

3. static char digits[19] =

4. { ‘9’, ‘8’, ‘7’, ‘6’, ‘5’, ‘4’, ‘3’, ‘2’, ‘1’,

5. ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ };

6. static const char* zero = digits + 9; // zero points to ‘0’

7. // works for -2147483648 .. 2147483647

8. int i = value;

9. char* p = buf;

10. do {

11. int lsd = i % 10; // lsd may be less than 0

12. i /= 10; // does it round down or towards zero?

13. *p++ = zero[lsd]; // index may be negative

14. } while (i != 0);

15. if (value < 0) {

16. *p++ = ‘-‘;

17. }

18. *p = ‘/0’;

19. std::reverse(buf, p);

20. return p; // p – buf is the length of the integer

21. }

This short piece of code is correct for all values of 32-bit int (from -2147483648 to 2147483647). It can be seen as a reference implementation of itoa(), a standard answer in interviews.

Upon reading this code, a doubt arose in my mind: Section 7.7 of C Traps and Pitfalls mentions that the results of integer division (/) and modulus (%) operations in C are implementation-defined when the operands are negative. (A brief version available online also contains the same content, see Section 7.5 of http://www.literateprogramming.com/ctraps.pdf.)

In other words, if m and d are both integers, int q = m / d; int r = m % d; then C only guarantees m == q*d + r. If either m or d is negative, the signs of q and r are determined by the implementation. For example, both (-13)/4 == (-3) and (-13)/4 == (-4) are valid. If the latter implementation is used, this conversion code would be incorrect (because it would yield (-1) % 10 == 9). The code can only function correctly if the quotient rounds towards zero.

To clarify this issue, I conducted some research.

What the Language Standards Say

• C89

I do not have the ANSI C89 document at hand, so I had to refer to K&R88. On page 41, section 2.5 states that The direction of truncation for / and the sign of the result for % are machine-dependent for negative operands…. It is indeed implementation-related. For this reason, C89 specifically provides the div() function, which calculates the quotient rounded towards zero, making it easier to write portable programs. I need to check the C++ standard.

• C++98

Section 5.6.4 states that If the second operand of / or % is zero, the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative, then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined. C++ does not specify the sign of the remainder (the description in C++03 is identical).

However, there is a footnote mentioning that According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded towards zero. This suggests that the revised C language standard will adopt the same rounding algorithm as Fortran. I checked C99.

• C99

Section 6.5.5.6 states that When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. (Footnote: This is often called “truncation toward zero”.) C99 clearly specifies that the quotient is rounded towards zero, which means the sign of the remainder is the same as the dividend, allowing the previous conversion algorithm to work correctly. The C99 Rationale (http://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf) mentions the reason for this provision: In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C. Since Fortran has made such provisions in numerical computing, it indicates that any overhead (if any) is acceptable.

• C++0x (where x has been confirmed to be a hexadecimal number)

The recent n2800 draft, section 5.6.4, adopts a similar phrasing to C99: For integral operands, the / operator yields the algebraic quotient with any fractional part discarded; (This is often called truncation towards zero.) This shows that C++ still strives to maintain compatibility with C.

Summary: C89 and C++98 left the decision to the implementation, while C99 and C++0x mandated truncation towards zero for the quotient, marking a progress in the language.

Behavior of C/C++ Compilers

I am primarily concerned with G++ and VC++. It should be noted that using code examples to probe compiler behavior is unreliable, even though the previous code works correctly under both compilers. Unless explicitly stated in the documentation, compilers may change implementations at any time — after all, we are concerned with implementation-defined behavior.

• G++ 4.4

http://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html GCC always follows the C99 requirement that the result of division is truncated towards zero. G++ has consistently adhered to the C99 standard, and the algorithm works correctly.

• Visual C++ 2008

http://msdn.microsoft.com/en-us/library/eayc4fzk.aspx The sign of the remainder is the same as the sign of the dividend. This statement is equivalent to truncating the quotient towards zero, and the algorithm works correctly.

Regulations of Other Languages

Since C89/C++98/C99/C++0x already exhibit considerable diversity, I will clarify how other languages define integer division. Here, I will only list a few common languages I (Chen Shuo) have encountered.

• Java

http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.17.2 The Java language specification explicitly states that integer division rounds towards zero. Additionally, for integer division overflow, it is specifically stated that no exception is thrown, and -2147483648 / -1 = -2147483648 (as well as the corresponding long version).

• C#

http://msdn.microsoft.com/en-us/vcsharp/aa336809.aspx C# 3.0 language specifies that division rounds the result towards zero. In cases of overflow, it states that an ArithmeticException may be thrown in a checked context; in an unchecked context, it is not explicitly stated whether an exception may or may not be thrown. (It is understood that C# 1.0/2.0 may differ.)

• Python

Python prominently states in its language reference manual that the quotient is rounded towards negative infinity. Plain or long integer division yields an integer of the same type; the result is that of mathematical division with the floor function applied to the result. http://docs.python.org/reference/expressions.html#binary-arithmetic-operations

• Ruby

Ruby’s language manual does not explicitly state this, but the library manual mentions that division is also rounded towards negative infinity. The quotient is rounded toward -infinity. http://www.ruby-doc.org/docs/ProgrammingRuby/html/ref_c_numeric.html#Numeric.divmod

• Perl

Perl defaults to floating-point arithmetic for division, so this issue does not arise. Perl’s integer modulus operation rules are consistent with Python/Ruby. http://perldoc.perl.org/perlop.html#Multiplicative-Operators However, note that use integer; may change the operation results, for example:

1. print -10 % 3; // => 2

2. use integers;

3. print -10 % 3; // => -1

• Lua

Lua does not have an integer type by default, so division is always performed as floating-point, thus does not involve the issue of rounding the quotient.

It can be seen that in the issue of rounding in integer division, languages fall into two camps: scripting languages are similar to each other, while C99/C++0x/Java/C# belong to another camp. Since both Python and Ruby are implemented in C, but their operational rules are self-contained, evidence can surely be found in the code.

Python’s code is quite readable, and I quickly found the implementation function i_divmod() for integer division and modulus operations in version 2.6.4 http://svn.python.org/view/python/tags/r264/Objects/intobject.c?revision=75707&view=markup. It is worth noting that this code even considers the special case of -2147483648 / -1 overflowing in 32-bit, which surprised me. The macro definition UNARY_NEG_WOULD_OVERFLOW and the comments before the function int_mul() are also worth reading.

Ruby’s code is a bit messier, but with some time, I was able to find it; this is the implementation from version 1.8.7-p248, focusing on the fixdivmod() function. http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/tags/v1_8_7_248/numeric.c?view=markup It is noteworthy that Ruby’s Fixnum integer representation range is one bit smaller than the machine word length, directly avoiding the possibility of overflow.

Hardware Implementation

Since C/C++ is known for efficiency, it should be close to hardware implementation. I examined several familiar hardware platforms, and they basically support the semantics of C99/C++0x, meaning that the new provisions incur no additional overhead. Listed below (actually, we only care about signed division, but for completeness, both unsigned and signed integer division instructions are listed).

• Intel x86/x64

The Intel x86 series DIV/IDIV instructions explicitly mention that they truncate towards zero, consistent with C99/C++0x/Java/C#.

• MIPS

Interestingly, I could not find the truncation direction of the DIV/DIVU instructions in the MIPS reference manual, but based on Patterson & Hennessy’s explanations, truncating towards zero seems to be easier to implement in hardware. Perhaps I did not find the right place?

• ARM/Cortex-M3

ARM does not have hardware division instructions, so this issue does not arise. The Cortex-M3 has hardware division, and both SDIV/UDIV instructions truncate towards zero. The Cortex-M3’s division instruction cannot simultaneously compute the remainder, which is quite special.

• MMIX

MMIX is a 64-bit CPU designed by Knuth, replacing the original MIX machine. Both DIV and DIVU truncate towards negative infinity (according to the definition in TAOCP section 1.2.4, on page 40 of the first volume), which is the only hardware platform I know that supports Python/Ruby semantics.

Conclusion: I did not expect that such a small integer division would have such a grand reputation. A piece of code that only involves integer operations may run in various syntactically similar languages, yet yield completely different results.