C arithmetic question.

[Seebs]

I don't think this is true. The problematic conversions are part of the
definition of the % operator. Not all operators include it in their
definition (for example, << and >> only do integer promotions) and %
could have been defined differently. That would have been odd, to say
the least, but it's the C definition of % that was causing the OP's
surprise, arithmetic conversions and all.

Hmm. See, I distinguish between the definition of the operation, and the
way in which it gets its operands.

-s

 

[Ben Bacarisse]

Hmm. See, I distinguish between the definition of the operation, and the
way in which it gets its operands.

That would be more reasonable if there were more consistency between
operators, but since some do integer promotions and some do arithmetic
conversions you have to know the rules, and those rule are, at the very
least, "attached" to the definitions of the operators. Some operators
(+ and - for example) have very complex rules depending on the operand
types.

On a related note. What's the point of requiring a common type for the
operands of %? It makes sense for * and / (and for + and - when the
operands are arithmetic) but % is not symmetric and I can't see any
cases where saying

"The integer promotions are performed on the operands. The type of
the result is that of the promoted left operand."

would be complicated to implement, but I am not knowledgeable about
the semantics of machine "remainder" operations.

 

[Ben Bacarisse]

Perhaps I'm missing something, but other than the modest difference in
wording, how are:

"Each of the operands shall have integer type / integer promotions are
performed on each of the operands" (shift operators)

"Each of the operands shall have integer type / The usual arithmetic
conversions are performed on the operands" (and/or/xor)

and "The operands of the % operator shall have integer type / The
usual arithmetic conversions are performed on the operands" ( % )

any different in result?

Yes, the usual arithmetic conversions determine (and convert to) a
*common* type after doing the integer promotions. As a result, you
can't tell what -1 % x is unless you know the type of x.

If % did only arithmetic promotions, the result would be calculated from
the original values of the operands. The usual arithmetic conversions
can change the sign of one or other operand and thus also change the
result.

<snip>

 

[James Kuyper]

On 01/23/2012 06:06 AM, Ben Bacarisse wrote:
....

On a related note. What's the point of requiring a common type for the
operands of %? It makes sense for * and / (and for + and - when the
operands are arithmetic) but % is not symmetric and I can't see any
cases where saying

The key reason is that the definitions of *, / and % are all tied
together. If they didn't all handle their operands the same way, the
requirement that (a/b)*b + (a%b) == a wouldn't work.

 

[Ben Bacarisse]

On 01/23/2012 06:06 AM, Ben Bacarisse wrote:
...

The key reason is that the definitions of *, / and % are all tied
together. If they didn't all handle their operands the same way, the
requirement that (a/b)*b + (a%b) == a wouldn't work.

Right.

There's no practical reason to continue this (that equality has been
fixed since ANSI C so it won't change) but if % behaved as I suggested,
I think that expression would be mathematically true, rather than 'C'
true (if you see what I mean). It's not clear to me that that
expression needs to be a true C expression rather than a true
mathematical expression.

There may be C programs that rely on (a/b)*b + (a%b) == a remaining true
when a and b are of mixed signed/unsigned types, but I'd bet that there
are more programs that have had to be fixed because it's not
mathematically true.

 

[Chad]

[-58ul % 37 == 23]
...
23 cannot be the right answer because
37 does not divide -58 - 23 = -81.
You have the explanation in the other posts. I just wanted to say...
Is this a bug in the compiler or a problem with the C standard?
From experience, I can tell you that you're in for a lifetime of pain
and embarrassment if these continue to be your first thoughts every
time you encounter unexplained output!
I am not embarrassed; the pain is slight.
The lesson is to use a library designed to
do arithmetic rather than expecting it from C.

Of course, there are several lessons possible from any example.  But I
think "understand how unsigneds work" might be a better one in this
case.

I prefer mine. C does not have a consistent approach to arithmetic.
The soi disant mod operator violates the fundamental law:

x = y (mod m) if and only if x - y  is divisible by m.

There is nothing to gain by learning C's idiosyncratic
rules on integer types for the purpose of doing arithmetic.

I've seen some Math definitions that place the additional restriction
that the remainder r and divisor d is such that

0 <=r < d

It looks like the mod operator in this case accounting for such a
restriction.

 

[James Kuyper]

I've seen some Math definitions that place the additional restriction
that the remainder r and divisor d is such that

0 <=r < d

It looks like the mod operator in this case accounting for such a
restriction.

No, that's not what's going on. C's definition for the modulus operator
contains no such restriction. In fact, it requires that a%b be negative
if a and b are both signed, and a is negative, unless 'a' is a multiple
of b.

What's causing this C code to correctly produce a value other than the
one Michael was expecting is the fact that 'a' has the type 'long',
while 'b' has the type 'unsigned long', with the result that 'a' is
converted to the 'unsigned long' before evaluating the modulus. The
conversion produces the value ULONG_MAX-57, which is positive, so that
a%b produces a value of 21. Michael's assertion to the contrary
notwithstanding, a - a%b is in fact divisible by b (because the same
conversion occurs to both occurrences of 'a'). If Michael had written

a %= (long)b;

b would have been converted to long, without change of value, and he
would have gotten a result of -21, which violates the requirement you
mention, but satisfies the one he mentions. Whether that's the value he
was expecting is unclear; he might have been expecting 16.cd

 

[Chad]

No, that's not what's going on. C's definition for the modulus operator
contains no such restriction. In fact, it requires that a%b be negative
if a and b are both signed, and a is negative, unless 'a' is a multiple
of b.

What's causing this C code to correctly produce a value other than the
one Michael was expecting is the fact that 'a' has the type 'long',
while 'b' has the type 'unsigned long', with the result that 'a' is
converted to the 'unsigned long' before evaluating the modulus. The
conversion produces the value ULONG_MAX-57, which is positive, so that
a%b produces a value of 21.  Michael's assertion to the contrary
notwithstanding, a - a%b is in fact divisible by b (because the same
conversion occurs to both occurrences of 'a'). If Michael had written

        a %= (long)b;

b would have been converted to long, without change of value, and he
would have gotten a result of -21, which violates the requirement you
mention, but satisfies the one he mentions. Whether that's the value he
was expecting is unclear; he might have been expecting 16.cd- Hide quotedtext -

Maybe I'm being a bit daft, but your explanation sort of mirrors how
you would go about dividing something like -11 by 3 when the remainder
can't be negative.

 

[James Kuyper]

Maybe I'm being a bit daft, but your explanation sort of mirrors how
you would go about dividing something like -11 by 3 when the remainder
can't be negative.

I'm not sure exactly what you're saying. The C standard requires
a) (-11)/3 == -3
b) ((-11)/3)*3 + (-11)%3 == -11

which means that (-11)%3 == -2.

It also requires that, on a system where ULONG_MAX == 4294967295, that
a) (-11UL)/3 == 1431655761
b) ((-11UL)/3)*3 + (-11UL)%3 == -11UL
which means that (-11UL)%3 == 2.

That's because the expression -11UL has a value of 4294967285. Michael
didn't realize that he was writing the equivalent of such an expression,
because he wasn't paying attention to the usual arithmetic conversions.

 

[Chad]

I'm not sure exactly what you're saying. The C standard requires
a) (-11)/3 == -3
b) ((-11)/3)*3 + (-11)%3 == -11

which means that (-11)%3 == -2.

It also requires that, on a system where ULONG_MAX == 4294967295, that
a) (-11UL)/3 == 1431655761
b) ((-11UL)/3)*3 + (-11UL)%3 == -11UL
which means that (-11UL)%3 == 2.

That's because the expression -11UL has a value of 4294967285. Michael
didn't realize that he was writing the equivalent of such an expression,
because he wasn't paying attention to the usual arithmetic conversions.- Hide quoted text -

In Michael's example, the conversion of unsigned long before
evaluating the modulus operator is ULONG_MAX-57. What I noticed was
that -57 was converted to a positive number. This in turn reminded me
of a definition of division that I saw a long time agon. This
definition was

Let a be an integer and d be a positive integer. Then there are unique
integers q and r, with 0 <= r < d such that a = dq + r.

Using the above definition, one can't divide something like -11 by 3
because it would produce a negative remainder. So what happens is the
remainder would get converted to a positive number. In other words,
something like

-11 = 3 * (-3) - 2

would become

-11 = 3 * (-4) + 1

And for whatever reasons, it just appeared to me that this math
definition applied to this particular situation.

 

[James Kuyper]

On 01/24/2012 01:03 PM, Chad wrote:
....

In Michael's example, the conversion of unsigned long before
evaluating the modulus operator is ULONG_MAX-57. What I noticed was
that -57 was converted to a positive number. This in turn reminded me

Actually, it's a value of -58L that gets converted to ULONG_MAX - 57.
The number that gets added to negative values, as many times as needed
to produce a value in range for the new type, is "one more than the
maximum value that can be represented in the new type" (6.3.1.3p2).

of a definition of division that I saw a long time agon. This
definition was

Let a be an integer and d be a positive integer. Then there are unique
integers q and r, with 0 <= r < d such that a = dq + r.

Using the above definition, one can't divide something like -11 by 3
because it would produce a negative remainder. So what happens is the
remainder would get converted to a positive number. In other words,
something like

-11 = 3 * (-3) - 2

would become

-11 = 3 * (-4) + 1

And for whatever reasons, it just appeared to me that this math
definition applied to this particular situation.

Well, it doesn't. ULONG_MAX-57 is positive, so rules covering negative
numbers aren't relevant.

More importantly, the C standard mandates that integer division must
truncate the value, removing the fractional part, so (-11)/3 must be
truncated to -3, not rounded downward to -4. In combination with the
requirement that (a/b)*b+a%b == a, that means that (-11)%3 must give a
value of -2, not 1.

 

[Chad]

On 01/24/2012 01:03 PM, Chad wrote:
...


Actually, it's a value of -58L that gets converted to ULONG_MAX - 57.
The number that gets added to negative values, as many times as needed
to produce a value in range for the new type, is "one more than the
maximum value that can be represented in the new type" (6.3.1.3p2).












Well, it doesn't. ULONG_MAX-57 is positive, so rules covering negative
numbers aren't relevant.

Yes. This is why I said for this particular case.

More importantly, the C standard mandates that integer division must
truncate the value, removing the fractional part, so (-11)/3 must be
truncated to -3, not rounded downward to -4. In combination with the
requirement that (a/b)*b+a%b == a, that means that (-11)%3 must give a
value of -2, not 1.- Hide quoted text -

What I'm trying to get at is that this math defintion seems to apply
to Michael's case and not the case in general.

 

[Rui Maciel]

The lesson is to use a library designed to
do arithmetic rather than expecting it from C.

What leads you to believe that using such a library would eliminate any
problem which the user might have regarding his understanding of how a
computer program (or even a computer) operates?


Rui Maciel

 

[Rui Maciel]

I already said what I expect from the % operation.

Do you believe that replacing a standard tool with some ad-hoc solution
represents a better option than simply taking the time to learn how the
standard tool actually works?

And what will you do when the ad-hoc solution exhibits some behavour which
goes against what you expected from it?


Rui Maciel

 

[James Kuyper]

Yes. This is why I said for this particular case.

Which is "this particular case" if it doesn't involve ULONG_MAX-57?

What I'm trying to get at is that this math defintion seems to apply
to Michael's case and not the case in general.

OK - I'm confused. What do you think Michael's case is? I thought it was
(ULONG_MAX-57)%37.

Alternatively, you could be referring to the case he mistakenly thought
was relevant, (-58)%37? C requires a value of -21 for that case, while
the rule you describe requires 16. However, both of those values satisfy
the criterion he complained about being violated:

x = y (mod m) if and only if x - y is divisible by m.

-58 - (-21) = -37 == -1*37
-58 - (16) = -74 == -2*37

So the issue you raise is irrelevant to his complaint.

 

[Chad]

Which is "this particular case" if it doesn't involve ULONG_MAX-57?



OK - I'm confused. What do you think Michael's case is? I thought it was
(ULONG_MAX-57)%37.

Alternatively, you could be referring to the case he mistakenly thought
was relevant, (-58)%37? C requires a value of -21 for that case, while
the rule you describe requires 16. However, both of those values satisfy
the criterion he complained about being violated:


        -58 - (-21) = -37 == -1*37
        -58 - (16) = -74 == -2*37

So the issue you raise is irrelevant to his complaint.

I'm going to sidestep your question for a minute...

I interpret something like a = mq + r as being equivalent to

a mod m = r

This means that Michael's example becomes

-58 % 37 = r

-58 = 37q + r

if the remainder is allowed to be negative, this expression could
become something like

-58 = 37 * (-1) + (-21)


However, you clearly showed that the correct answer is..

4294967238 = 116081095*37 + 23.


This in turn would lead me to believe there is the additional
restriction to the math forumla (definition) that the remainder has to
be positive.

 

[Chad]

Which is "this particular case" if it doesn't involve ULONG_MAX-57?



OK - I'm confused. What do you think Michael's case is? I thought it was
(ULONG_MAX-57)%37.

Alternatively, you could be referring to the case he mistakenly thought
was relevant, (-58)%37? C requires a value of -21 for that case, while
the rule you describe requires 16. However, both of those values satisfy
the criterion he complained about being violated:


        -58 - (-21) = -37 == -1*37
        -58 - (16) = -74 == -2*37

So the issue you raise is irrelevant to his complaint.

I think I just hit the wrong reply button.

 

[Chad]

Which is "this particular case" if it doesn't involve ULONG_MAX-57?



OK - I'm confused. What do you think Michael's case is? I thought it was
(ULONG_MAX-57)%37.

Alternatively, you could be referring to the case he mistakenly thought
was relevant, (-58)%37? C requires a value of -21 for that case, while
the rule you describe requires 16. However, both of those values satisfy
the criterion he complained about being violated:


        -58 - (-21) = -37 == -1*37
        -58 - (16) = -74 == -2*37

So the issue you raise is irrelevant to his complaint.

I'm going to sidestep your question for a minute.....


I interpret something like a = mq +r as being equivalent to

a mod m = r

Going on this definition, something like -58 % 37 becomes

-58 mod 37 = r

-58 = 37 *q + r


Now if I allow for the possiblity of a negative remainder, the above
expression could possibly reduce to something like

-58 = 37 * (-1) + (-21)

However, you showed that in fact the result was

4294967238 = 116081095*37 + 23.


This would lead to me to believe that there is the additional
restriction to the math definition that the remainder has to be
positive.

 

[Kleuske]

I'm going to sidestep your question for a minute...

I interpret something like a = mq + r as being equivalent to

a mod m = r

This means that Michael's example becomes

-58 % 37 = r

-58 = 37q + r

if the remainder is allowed to be negative, this expression could become
something like

-58 = 37 * (-1) + (-21)


However, you clearly showed that the correct answer is..

4294967238 = 116081095*37 + 23.


This in turn would lead me to believe there is the additional
restriction to the math forumla (definition) that the remainder has to
be positive.

Problem is here are several definitions of the modulo operation. They all
agree on what happens when operands are positive, but disagree what
happens when one of the operands is negative.

I'm not a standards-jockey, but i'd be interested what the experts have
to say.

See also http://en.wikipedia.org/wiki/Modulo_operator

 

[James Kuyper]

I'm going to sidestep your question for a minute...

I interpret something like a = mq + r as being equivalent to

a mod m = r

This means that Michael's example becomes

-58 % 37 = r

-58 = 37q + r

if the remainder is allowed to be negative, this expression could
become something like

-58 = 37 * (-1) + (-21)


However, you clearly showed that the correct answer is..

4294967238 = 116081095*37 + 23.

This in turn would lead me to believe there is the additional
restriction to the math forumla (definition) that the remainder has to
be positive.

In so far as there's an official "math definition" of the modulus
operator, what I "clearly showed" doesn't tell you anything about that
definition. I was using C rules for the % operator, not "math" rules for
the modulus operator. Those C rules specified that, in this context, -58
gets converted to ULONG_MAX-57. The C result is non-negative only
because ULONG_MAX-57 is positive, it has nothing to do with any general
requirement that a%b be non-negative.

a%b is not merely allowed to be negative; If a is negative, larger than
b and not a multiple of b, a%b is required to be negative. However,
because 'a' was ULONG_MAX-57, that doesn't apply