C arithmetic question.

[Michael Press]

$cat hunh.c
#include <stdio.h>

int
main(void)
{
long int a = -58;
unsigned long int b = 37;

a %= b;
printf("%ld\n", a);
return 0;
}
$cc -std=c99 -Wall -pedantic -o hunh hunh.c
$./hunh
23
$ cc -v
Using built-in specs.
Target: i686-apple-darwin9
Configured with: /var/tmp/gcc/gcc-5465~16/src/configure --disable-checking -enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.0/ --with-gxx-include-dir=/include/c++/4.0.0 --with-slibdir=/usr/lib --build=i686-apple-darwin9 --with-arch=apple --with-tune=generic --host=i686-apple-darwin9 --target=i686-apple-darwin9
Thread model: posix
gcc version 4.0.1 (Apple Inc. build 5465)

---

23 cannot be the right answer because
37 does not divide -58 - 23 = -81.

Is this a bug in the compiler or a problem with the C standard?

 

[James Kuyper]

$cat hunh.c
#include <stdio.h>

int
main(void)
{
long int a = -58;
unsigned long int b = 37;

a %= b;
printf("%ld\n", a);
return 0;
}
$cc -std=c99 -Wall -pedantic -o hunh hunh.c
$./hunh
23
$ cc -v
Using built-in specs.
Target: i686-apple-darwin9
Configured with: /var/tmp/gcc/gcc-5465~16/src/configure --disable-checking -enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.0/ --with-gxx-include-dir=/include/c++/4.0.0 --with-slibdir=/usr/lib --build=i686-apple-darwin9 --with-arch=apple --with-tune=generic --host=i686-apple-darwin9 --target=i686-apple-darwin9
Thread model: posix
gcc version 4.0.1 (Apple Inc. build 5465)

---

23 cannot be the right answer because
37 does not divide -58 - 23 = -81.

Is this a bug in the compiler or a problem with the C standard?

The C standard defines the behavior of the modulus operator in 6.5.5p6:

When integers are divided, the result of the / operator is the algebraic quotient with any
fractional part discarded.90) If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

The first clause tells us that (-58)/37 is -1. The second clause says that
(-1)*37+ (-58)%37 = -58
(-53)%37 = -58 + 37 = -21

However, that leave out one important issue: b is unsigned. As a
result, -58 gets convert to ULONG_MAX-57 before applying the modulus
operator. If unsigned long is 32 bit, then (unsigned long)-58 is
4294967238 = 116081095*37 + 23.

 

[Markus Wichmann]

$cat hunh.c
#include <stdio.h>

int
main(void)
{
long int a = -58;
unsigned long int b = 37;

a %= b;
printf("%ld\n", a);
return 0;
}
$cc -std=c99 -Wall -pedantic -o hunh hunh.c
$./hunh
23 [...]

23 cannot be the right answer because
37 does not divide -58 - 23 = -81.

Is this a bug in the compiler or a problem with the C standard?

You have hit a signed/unsigned issue.

The C standard states in section 6.5.5 (Multiplicative operators),
sentence 3 that "the usual arithmetic conversions are performed on the
operands". These get defined earlier and in the context of this snippet
amount to "a" being converted to unsigned long int. That means on a
two's-complement-machine that the bits of a get reinterpreted as
unsigned long int. (The real definition is that one more than the
maximum possible value of the unsigned type is added to the negative
value until the result is representable, which leads to what I just wrote.)

So, in the end, in the assignment line, the value of a gets converted to
unsigned long, the modulo of that number to the value of b is calculated
and then the result of this gets converted to signed long int again and
assigned to a.

So, you are not calculating -28 % 37, but (ULONG_MAX + 1 - 28) % 37.

HTH,
Markus

 

[Peter Nilsson]

[-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!

 

[Michael Press]

[-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.

 

[James Kuyper]

[-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.

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

Do you really believe that a%(long)b is so much more complicated than
a%b that a special library is called for?

I would guess that you are probably thinking of this as just one issue
among many, the totality of which justifies use of a special library -
so what are those other issues? How would the behavior of that library
differ from that of ordinary C arithmetic?

 

[Ben Bacarisse]

[-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.

I don't think it's reasonable to expect C to do arithmetic in the usual
sense of the word. Very few programing languages even try, and those
that do are not C-like at all (Haskell and Lisp come to mind as examples
of those that make the effort).

Like the vast majority of languages, C has rules about expressions that
mix types and that produce seemingly unrepresentable results. Some of
these are a little surprising, but I'm not confident I could come up
with a set of more reasonable rules without losing the essence of the
language.

 

[Joe Pfeiffer]

[-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.

 

[Michael Press]

[-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.

 

[Ike Naar]

[-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.

The mod operator does not violate that law.
Your problem is not with the mod operator, it's
that the numbers that are given to the mod operator
are not what you think they are.

 

[Keith Thompson]

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

You could gain the ability to write C code that does arithmetic. The
vast majority of people have chosen not to learn it, but your presence
in this newsgroup suggests that you might find it useful.

 

[BartC]

On 18.01.2012 19:32, Michael Press wrote:

You have hit a signed/unsigned issue.

So, in the end, in the assignment line, the value of a gets converted to
unsigned long

That sounds wrong. A small unsigned value can easily be converted to signed
format, of the same int width, without losses.

A small signed, negative value *can't* be converted to unsigned format, no
matter how wide the number.

It would be more useful to convert both to signed format when the numbers
are mixed.

(And in the case of 32-bit values, then unsigned values up to 2147483647,
for example, can be expressed in 32-bit signed format. Yet not even
something as small as -3 can be expressed as unsigned. Although it's
possible unsigned format has been chosen *because* the number will be above
that limit.)

 

[Nomen Nescio]

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.

I don't think it violates any law. You need to understand your tools and how
computers work, or you should probably quit programming.

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

It has nothing to do with C, it has to do with your lack of understanding of
signed and unsigned values and how hardware and software work with them.

 

[James Kuyper]

$cat hunh.c
#include <stdio.h>

int
main(void)
{
long int a = -58;
unsigned long int b = 37;

a %= b;
printf("%ld\n", a);
return 0;
}
$cc -std=c99 -Wall -pedantic -o hunh hunh.c
$./hunh
23
$ cc -v
Using built-in specs.
Target: i686-apple-darwin9
Configured with: /var/tmp/gcc/gcc-5465~16/src/configure --disable-checking -enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.0/ --with-gxx-include-dir=/include/c++/4.0.0 --with-slibdir=/usr/lib --build=i686-apple-darwin9 --with-arch=apple --with-tune=generic --host=i686-apple-darwin9 --target=i686-apple-darwin9
Thread model: posix
gcc version 4.0.1 (Apple Inc. build 5465)

---

23 cannot be the right answer because
37 does not divide -58 - 23 = -81.

Is this a bug in the compiler or a problem with the C standard?

The C standard defines the behavior of the modulus operator in 6.5.5p6:

When integers are divided, the result of the / operator is the algebraic quotient with any
fractional part discarded.90) If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

The first clause tells us that (-58)/37 is -1. The second clause says that
(-1)*37+ (-58)%37 = -58
(-53)%37 = -58 + 37 = -21

However, that leave out one important issue: b is unsigned. As a
result, -58 gets convert to ULONG_MAX-57 before applying the modulus
operator. If unsigned long is 32 bit, then (unsigned long)-58 is
4294967238 = 116081095*37 + 23.

Should have just said the 'BUG' was in his program.

Why? There's no bug in his program; just unexpected output, because he
forgot to take into consideration C's rules for operations that involve
a combination of signed and unsigned types. From his point of view, the
fact that the result of expression was not what he expected means that
the correct answer is "a problem with the C standard".
He'd be happier if the C standard were changed to match his
expectations, though he's not yet made it clear what changes would be
required to achieve that goal. The fact that he was surprised by this
result suggests that he's not sufficiently familiar with the current
specifications to make specific suggestions for how they should be
changed. However, unless and until they are changed, I would recommend
changing his expectations to match the standard.

 

[James Kuyper]

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.

No, it does not. The C standard mandates that if a/b is representable in
the appropriate type, then (a/b)*b + (a%b) = a, from which it can easily
be shown that a-(a%b) == (a/b)*b, a number divisible by b.

Insert the following line in your program:
printf("%lu\n", a - (a%b));
You should find that it prints out a number exactly divisible by 37.

Your problem has nothing to do with the modulus operator, but only with
your failure to realize that your code involved an implicit conversion
to unsigned long before the modulus operator was even applied.

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

Other than the ability to write C code making use of those rules. That
might not be of any interest to you.

 

[osmium]

[-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!

This post seems to have triggered a hornet's nest of issues. How to design
a computer language, when the use of a "raw" computer language is advisable,
some fundamentals of number theory, and on and on and on.

The message I got was "If you think there is a compiler bug, you are
probably wrong". Some of the rules imposed by the standard are, IMO,
esoteric and might violate your notion of what makes sense. The moral is
most likely there is a bug in your program than the two options given by the
OP; keep in mind that the compiler designers get to decide what a bug *is*.

 

[Dr Nick]

You could gain the ability to write C code that does arithmetic. The
vast majority of people have chosen not to learn it, but your presence
in this newsgroup suggests that you might find it useful.

The main thing is that there aren't that many occasions when you need to
mix signed and unsigned numbers, and that's when unexpected - to the
naive programmer - things can happen.

The rest of the time there's nothing special going on.

I tend to use the odd (probably) superfluous cast in those
circumstances: it makes it clear to me what I wanted to happen and to
anyone else reading the code. I'd need to double check what I wanted,
and document it with a comment anyway.

But even in programs using both signed and unsigned numbers the two mix
only infrequently. GCC is pretty good at warning when you've written
something that doesn't do what you might have thought it would.

 

[Michael Press]

[-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.

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

Do you really believe that a%(long)b is so much more complicated than
a%b that a special library is called for?

I would guess that you are probably thinking of this as just one issue
among many, the totality of which justifies use of a special library -
so what are those other issues? How would the behavior of that library
differ from that of ordinary C arithmetic?

I already said what I expect from the % operation.

 

[Michael Press]

[-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.

The mod operator does not violate that law.
Your problem is not with the mod operator, it's
that the numbers that are given to the mod operator
are not what you think they are.

You consider that more important than
the mod operator being consistent. I do not.

 

[Michael Press]

I don't think it violates any law.

It does.