[rust-dev] Division and modulo for signed numbers

swede at earthling.net swede at earthling.net
Tue Apr 23 07:48:12 PDT 2013


Hello,

I've been lurking on the Rust list for a while. The language looks very promising! However, Rust copies a misfeature in the division operator from C: truncating toward zero (T-division). A better definition of division is to round toward negative infinity (Flooring, or F-division).

A quick summary:
In truncating division (T-division) as used by C and current Rust:
 D / d is rounded toward zero
 D % d has the sign of the first argument

In flooring division (F-division):
 D / d is rounded toward negative infinity
 D % d has the sign of the second argument

Both definitions satisfy the "division rule":
 (D/d)*d + (D%d) = D

For a mathematical discussion of why F-division is better than T-division, see this paper:

"The Euclidean Definition of the Functions div and mod" by Raymond T. Boute
https://biblio.ugent.be/input/download?func=downloadFile&recordOId=314490&fileOId=452146    or    http://dx.doi.org/10.1145/128861.128862

>From a programming perspective, F-division has several benefits:

 1.  x % len is always in the range [0, len-1) if len is positive
 2.  x / k will return each quotient k times as x is incremented
 3.  x / (2^n) can be converted to a bitwise right shift for any x
 4.  x % (2^n) can be converted to a bitwise and for any x

None of these properties hold for T-division when x is negative.

Property 1 is the most important, since converting integers to array indexes is a common operation (probably the most common use of the % operator). This single use is a convincing reason to switch to the F-definition, in my opinion.
Property 2 is useful for things like sample-rate conversion or nearly-unbiased scaling of random numbers.
Properties 3 and 4 are simply performance optimizations.

While T-division is the most common choice (used by C, C++, etc) F-division is not uncommon. I've confirmed that Python and Ruby use F-division, and Wikipedia claims that TCL and D do too. F-division behavior won't be surprising or hard to explain to any users familiar with Python, which is most developers today.

Performance should be about the same when using F-division:
 * Performance will go up for division by constant powers of two.
 * Performance will stay the same for division by compile-time constants, since these are transformed by the compiler into multiplies. (I actually think performance will go up slightly in this case, but it's been a while since I looked at the algorithm.)
 * Performance on ARM will stay the same for divides by variables (not known at compile-time), since ARM does not have a hardware divider.
 * Performance on x86/x64 for divides by variables will go down slightly, since Intel's idiv instruction implements F-division.

So one already very slow operation (x86 idiv) gets slightly slower, one fast operation (divide by power-of-two) gets quite a bit faster. It probably nets out near zero.

The T-division operator would still be needed for compatibility with C, but it should be provided as a library function instead of as the standard definition of "/" and "%".

Thanks for your time,
Erik


More information about the Rust-dev mailing list