 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Ganny
Guest
|
 Posted: Tue Mar 07, 2006 12:06 pm Post subject: Modulus operation on negative numbers |
 |
|
This is regarding the computation of modulus operation in C/C++ for
negative numbers. Irrespective of the value (positive or negative) of
the integer, C/C++ follows the rule "(a/b)*b + a%b shall equal a" (C99
- 6.5.5[6]). For negative numbers, it is different from the
mathematical interpretation of the modulus/remainder operation:
http://mathforum.org/library/drmath/view/52343.html
Probably, there should have been two operators, mod and div as in Ada:
http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html
Does anybody know why it wasn't done (for C/C++)?
Thanks!
-Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Rob
Guest
|
| Posted: Wed Mar 08, 2006 1:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
Ganny wrote:
| Quote: | This is regarding the computation of modulus operation in C/C++ for
negative numbers. Irrespective of the value (positive or negative) of
the integer, C/C++ follows the rule "(a/b)*b + a%b shall equal a" (C99
- 6.5.5[6]). For negative numbers, it is different from the
mathematical interpretation of the modulus/remainder operation:
http://mathforum.org/library/drmath/view/52343.html
Probably, there should have been two operators, mod and div as in Ada:
http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html
Does anybody know why it wasn't done (for C/C++)?
|
The way C (particularly up to and including the 1989 standard)
supported anything mathematical or numerical left a fair bit to be
desired. The support (other than some basic operations) was more an
afterthought than a carefully considered part of the language. The
rule you quote for the modulo operator is something that is more
convenient for compiler writers and computer scientists (it is a valid
operation with a clean definition) than it is concerned with being
mathematically correct.
So, to answer you question, it probably wasn't "done" for C/C++ because
it wasn't thought of, rather than because of a deliberate design
decision.
You will find that people who do a lot of mathematical work in C/C++
will often write a small math library to do the jobs required
(fortunately, although the language and library is mathematically
incorrect in a number of ways, it is not particularly difficult to
implement correct functions).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Alberto Ganesh Barbati
Guest
|
| Posted: Wed Mar 08, 2006 1:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
Ganny ha scritto:
| Quote: | This is regarding the computation of modulus operation in C/C++ for
negative numbers. Irrespective of the value (positive or negative) of
the integer, C/C++ follows the rule "(a/b)*b + a%b shall equal a" (C99
- 6.5.5[6]). For negative numbers, it is different from the
mathematical interpretation of the modulus/remainder operation:
http://mathforum.org/library/drmath/view/52343.html
|
In fact in the C Standard the operator % is always called "remainder"
and never "modulus". The C++ standard makes a bit of confusion, because
§5.6 uses the word "remainder" but in the index the word "modulus" is
used instead. It's worth mentioning that there exist a std::modulus
functor in the standard library that computes a%b. It should have been
called std::remainder, IMHO.
(I guess you meant rem and mod). Probably. I guess it's too late to add
it now... We have to stick to a library-based solution, I suppose.
| Quote: | Does anybody know why it wasn't done (for C/C++)?
|
No idea...
Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Jack Klein
Guest
|
|
| Back to top |
|
|
John G Harris
Guest
|
| Posted: Thu Mar 09, 2006 11:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
In message <1141705516.093941.74740 (AT) p10g2000cwp (DOT) googlegroups.com>, Ganny
<sgganesh (AT) gmail (DOT) com> writes
| Quote: | This is regarding the computation of modulus operation in C/C++ for
negative numbers. Irrespective of the value (positive or negative) of
the integer, C/C++ follows the rule "(a/b)*b + a%b shall equal a" (C99
- 6.5.5[6]). For negative numbers, it is different from the
mathematical interpretation of the modulus/remainder operation:
http://mathforum.org/library/drmath/view/52343.html
Probably, there should have been two operators, mod and div as in Ada:
http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html
Does anybody know why it wasn't done (for C/C++)?
|
For integers the equation
a = q*b + r
has an infinite number of solutions. Even if you want r to be close to
zero (and b non-zero) there are several reasonable solutions. One will
be right for your project, one will be right for mine, and neither will
be right for someone else. It doesn't matter what rule for / and % the
standard defines : it is going to be 'right' in some contexts and wrong
in others.
As for modulus, you might think that mod 12 should give a number in the
range 0..11, but then you look at a few clocks and see that many people
prefer 1..12. Again it's a matter of which definition is more
appropriate in which context.
John
--
John Harris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Thant Tessman
Guest
|
| Posted: Thu Mar 09, 2006 7:06 pm Post subject: Re: Modulus operation on negative numbers |
|
|
John G Harris wrote:
| Quote: | For integers the equation
a = q*b + r
has an infinite number of solutions. Even if you want r to be close to
zero (and b non-zero) there are several reasonable solutions. One will
be right for your project, one will be right for mine, and neither will
be right for someone else. It doesn't matter what rule for / and % the
standard defines : it is going to be 'right' in some contexts and wrong
in others.
|
So describe for us a problem for which the solution typically chosen by
hardware implementors is the 'right' solution (beyond the case where a,
b, and r are all positive that is).
[...]
-thant
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
John G Harris
Guest
|
| Posted: Sat Mar 11, 2006 2:06 pm Post subject: Re: Modulus operation on negative numbers |
|
|
In message <dupn5j$r5g$1 (AT) news (DOT) xmission.com>, Thant Tessman
<adm (AT) standarddeviance (DOT) com> writes
| Quote: | John G Harris wrote:
For integers the equation
a = q*b + r
has an infinite number of solutions. Even if you want r to be close to
zero (and b non-zero) there are several reasonable solutions. One will
be right for your project, one will be right for mine, and neither will
be right for someone else. It doesn't matter what rule for / and % the
standard defines : it is going to be 'right' in some contexts and wrong
in others.
So describe for us a problem for which the solution typically chosen by
hardware implementors is the 'right' solution (beyond the case where a,
b, and r are all positive that is).
|
As a one-time mainframe designer I think I can give an honest answer to
that. The hardware is designed to go as fast as possible without adding
extra clock cycles and extra hardware for uninteresting cases. The
result is that negative numbers do whatever they do. If you're lucky q
and r are always coherent. If you're *very* lucky the rules are
documented accurately, but I wouldn't want to bet on it.
Sometimes there are explicit requirements aimed at facilitating
multi-word arithmetic. In that case you are at the mercy of the
specifier, right or wrong.
John
--
John Harris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Thant Tessman
Guest
|
| Posted: Sat Mar 11, 2006 6:06 pm Post subject: Re: Modulus operation on negative numbers |
|
|
[...deliberately leaving much quoted material...]
John G Harris wrote:
| Quote: | In message <dupn5j$r5g$1 (AT) news (DOT) xmission.com>, Thant Tessman
adm (AT) standarddeviance (DOT) com> writes
John G Harris wrote:
For integers the equation
a = q*b + r
has an infinite number of solutions. Even if you want r to be close to
zero (and b non-zero) there are several reasonable solutions. One will
be right for your project, one will be right for mine, and neither will
be right for someone else. It doesn't matter what rule for / and % the
standard defines : it is going to be 'right' in some contexts and wrong
in others.
So describe for us a problem for which the solution typically chosen by
hardware implementors is the 'right' solution (beyond the case where a,
b, and r are all positive that is).
As a one-time mainframe designer I think I can give an honest answer to
that. The hardware is designed to go as fast as possible without adding
extra clock cycles and extra hardware for uninteresting cases. The
result is that negative numbers do whatever they do. If you're lucky q
and r are always coherent. If you're *very* lucky the rules are
documented accurately, but I wouldn't want to bet on it.
|
Given that so many other languages provide functions that deliberately
don't match the behavior of '/' and '%' in the "uninteresting" cases, it
might be that they're not so uninteresting after all.
To elaborate for other readers, the "correct" behavior is for the sign
of the remainder to match the sign of the denominator. This is (almost?)
always the behavior you want when you're doing real math. Hardware
typically makes the sign of the remainder match the sign of the
numerator, which is (almost?) always an outright bug in the case where
the numerator and denominator aren't expected to be always positive.
inline div_t divmod(int n, int d) {
div_t qr = div(n, d);
if ((qr.rem<0 && d>0) ||
(qr.rem>0 && d<0)) {
--qr.quot;
qr.rem += d;
}
return qr;
}
-thant
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
John G Harris
Guest
|
| Posted: Sun Mar 12, 2006 9:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
In message <duupgh$9e0$1 (AT) news (DOT) xmission.com>, Thant Tessman
<adm (AT) standarddeviance (DOT) com> writes
To recap, a = q*b + r
<snip>
| Quote: | To elaborate for other readers, the "correct" behavior is for the sign
of the remainder to match the sign of the denominator. This is (almost?)
always the behavior you want when you're doing real math. Hardware
typically makes the sign of the remainder match the sign of the
numerator, which is (almost?) always an outright bug in the case where
the numerator and denominator aren't expected to be always positive.
snip |
When a, b are non-negative and b non-zero the C++ standard requires that
0 <= r < b .
We are both happy about this case.
In other cases, with b non-zero, the standard allows any answer provided
-abs(b) <= r <= abs(b)
(though it's not said as clearly as that).
When a is negative and b is positive you want
0 <= r < b .
Unfortunately for you, footnote 74 of the standard says
"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 toward zero."
This means that when a is negative and b is positive you might one day
get
-abs(b) < r <= 0
because this make a negative quotient more positive, so closer to zero.
This is the opposite of what you would like. Any comments ?
John
--
John Harris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Alberto Ganesh Barbati
Guest
|
| Posted: Sun Mar 12, 2006 4:06 pm Post subject: Re: Modulus operation on negative numbers |
|
|
Thant Tessman ha scritto:
| Quote: |
To elaborate for other readers, the "correct" behavior is for the sign
of the remainder to match the sign of the denominator. This is (almost?)
always the behavior you want when you're doing real math. Hardware
typically makes the sign of the remainder match the sign of the
numerator, which is (almost?) always an outright bug in the case where
the numerator and denominator aren't expected to be always positive.
|
The remainder operation is strictly tied to the division operation. Your
behavior is equivalent to saying that the result of the division is to
be rounded towards minus infinity, so while it gives "correct" results
for the remainders (according to some definition of "correct"), it gives
"wrong" (according to some definition of "wrong") results for the
division. For example, with your behavior:
6 / 5 = 1 * 5 + 1
6 / -5 = -2 * -5 - 4
-6 / 5 = -2 * 5 + 4
-6 / -5 = 1 * -5 - 1
Some people finds that (-a/b) != -(a/b) is not "correct". You might
disagree, but they have their reasons.
With the rounding-towards-zero approach, the results would be:
6 / 5 = 1 * 5 + 1
6 / -5 = -1 * -5 + 1
-6 / 5 = -1 * 5 - 1
-6 / -5 = 1 * -5 - 1
I don't think there really is a "mathematically correct" behavior among
the two, but, if I had to choose, I'd choose the latter. It seems that
I'm not the only one that shares this opinion, as the ISO Fortran
standard (ISO/IEC 1539:1991) specifically chooses the
rounding-towards-zero approach and the C standard adopted this decision
in its latest revision (ISO/IEC 9899:1999). According to the footnote to
5.6/4 in the C++ standard, it seems quite probable that the next
revision of C++ will also follow this route.
Regards,
Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Thant Tessman
Guest
|
| Posted: Sun Mar 12, 2006 6:06 pm Post subject: Re: Modulus operation on negative numbers |
|
|
John G Harris wrote:
[...]
| Quote: | Unfortunately for you, footnote 74 of the standard says
"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 toward zero."
This means that when a is negative and b is positive you might one day
get
-abs(b) < r <= 0
because this make a negative quotient more positive, so closer to zero.
This is the opposite of what you would like. Any comments ?
|
A couple of languages with which I'm familiar provide both the "correct"
version, and the "fast" version. The "fast" version doesn't promise to
round toward zero. It merely promises to match the behavior of the
hardware--which usually rounds toward zero.
Clearly the designers of these other languages don't value the promise
of a consistently incorrect answer. They apparently merely want to take
into account that people sometimes might value the performance of the
"fast" version in the use cases where the "fast" version can be trusted.
-thant
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Andrei Alexandrescu (See
Guest
|
| Posted: Mon Mar 13, 2006 10:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
Thant Tessman wrote:
| Quote: | John G Harris wrote:
[...]
Unfortunately for you, footnote 74 of the standard says
"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 toward zero."
This means that when a is negative and b is positive you might one day
get
-abs(b) < r <= 0
because this make a negative quotient more positive, so closer to zero.
This is the opposite of what you would like. Any comments ?
A couple of languages with which I'm familiar provide both the "correct"
version, and the "fast" version. The "fast" version doesn't promise to
round toward zero. It merely promises to match the behavior of the
hardware--which usually rounds toward zero.
Clearly the designers of these other languages don't value the promise
of a consistently incorrect answer. They apparently merely want to take
into account that people sometimes might value the performance of the
"fast" version in the use cases where the "fast" version can be trusted.
|
One thing I never understood was why the heck they turned the problem on
its head. So they say: "We give you a correct version with predictable
behavior, and whatever the hardware does."
Given that there are two choices anyway (round towards zero or towards
infinity), why in the world don't they give you the two versions, both
with predictable behavior, and let you choose the one that you need?
Then, if the machine happens to implement what you needed, it's fast. If
not, it's slower but you needed that behavior anyway.
I must be missing something.
Andrei
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Thant Tessman
Guest
|
| Posted: Mon Mar 13, 2006 10:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
Alberto Ganesh Barbati wrote:
[...]
| Quote: | Some people finds that (-a/b) != -(a/b) is not "correct". You might
disagree, but they have their reasons. [...]
|
Okay, who are they, and what are their reasons?
That's the problem. People simply assume that there's a reason these
functions behave the way they do, but no one seems to know what it is
(beyond being easier to implement in hardware).
-thant
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
John G Harris
Guest
|
| Posted: Tue Mar 14, 2006 12:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
In message <4414612E.9040505 (AT) erdani (DOT) org>, "Andrei Alexandrescu (See
Website For Email)" <SeeWebsiteForEmail (AT) erdani (DOT) org> writes
Recap : a = q*b + r
<snip>
| Quote: | Given that there are two choices anyway (round towards zero or towards
infinity), why in the world don't they give you the two versions, both
with predictable behavior, and let you choose the one that you need?
Then, if the machine happens to implement what you needed, it's fast. If
not, it's slower but you needed that behavior anyway.
I must be missing something.
snip |
That's the problem with this subject; it's nearly as emotional as GC :-)
There are more than two reasonable specs for (q,r). Which is most
appropriate depends on the application domain : modulo arithmetic, paper
and pencil simulation, general financial, fixed point banking
arithmetic, to name a few.
As it happens, both of the two rules you quote have been flagged as
wrong by Thant.
John
--
John Harris
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Alberto Ganesh Barbati
Guest
|
| Posted: Wed Mar 15, 2006 11:06 am Post subject: Re: Modulus operation on negative numbers |
|
|
Thant Tessman ha scritto:
| Quote: | Alberto Ganesh Barbati wrote:
[...]
Some people finds that (-a/b) != -(a/b) is not "correct". You might
disagree, but they have their reasons. [...]
Okay, who are they, and what are their reasons?
|
For example the people of the Fortran committee (or at least the
majority of them) that approved in 1991 the ISO Fortran Standard. For
example the people of C committee (or at least the majority of them)
that approved in 1998 the C standard. It seems a bunch of very
representative people to me. The reasons? You ask them.
| Quote: | That's the problem. People simply assume that there's a reason these
functions behave the way they do, but no one seems to know what it is
(beyond being easier to implement in hardware).
|
That's the problem. People simply assume that they are the first ones in
the history of computer science to think about a problem. People don't
realize that the problem might have been discussed ad nauseam in 1991
(well... most probably long before, since Fortran dates back to the
'50). People don't think that this kind of things do not "happen"
spontaneously but decisions were made and there were rationales behind
them. Even the QWERTY layout has a rationale behind it! (Although very
objectionable in this case... ;)
Do you realize that maybe rounding-toward-zero is easier to implement in
hardware because of the decision of the Fortran committee and not the
other way round? Not that I pretend to know how thing went exactly, but
that's a possibility. What do you think is the difference, measured in
number of transistors, between the hardware implementations of
rounding-towards-zero and rounding-towards-minus-infinity? I bet it's
negligible, so it makes perfect sense for chip-makers to follow what the
industry required, not the opposite.
Just my opinion,
Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Powered by phpBB © 2001, 2006 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
