[rust-dev] Division and modulo for signed numbers
swede at earthling.net
swede at earthling.net
Tue Apr 23 07:48:12 PDT 2013
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,
More information about the Rust-dev