The Fugue Counterpoint by Hans Fugal

5Apr/063

% for Remainder

I had my lunch handed to me today because some C DSP code I had written was
wrong:

/* M is the size of the buffer,
 * w is the base pointer,
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;
}

What I did not realize is that the % operator in C does not wrap negative
numbers into the positive range like you would expect if you were a
mathemtician. i.e. -7 % 8 == -7 in C, where in mathematics -7 = 1 mod 8.

I can hear you now: "Didn't you test it, you fool?" Well, yes, I tested the
algorithm in Ruby, where mathematics hold true:

rb(main):001:0> -7 % 8
=> 1

How was I to know the C version was braindead?

So which is right? Well you can probably guess my bias by now. But inquiring
minds want to know, and no other type reads this blog so I did some research.

First, the mathematics. Wolfram has a dizzying
explanation
. Search for
modular
arithmetic

for any number of treatments of the subject. Too lazy for that? Fine, look at
your watch. If it's 10:05 and you go back in time 10 minutes, is it -5 past
10? Arguably so ("5 to"), but most people would agree that it's actually 9:55
by canon.

Now for the C argument. The 1999 ISO C Standard says:

If the quotient a/b is representable, the expression (a/b)*b + a%b shall
equal a.

So my compiler is fine. It's C that's broken. Before C99 the use of % on
negative numbers was IMPLEMENTATION DEPENDENT, which if you know anything about
C history means they didn't think it through well enough, or they made a
decision based on speed or ease of implementation. The C99 definition was
probably chosen either for ease of implementation or for the most common case.
Not exactly good enough to convince me.

Naturally, there's no going back now, so if you find yourself possibly needing
to do modular arithmetic on negative numbers in C, be sure to add again if
negative:

/* M is the size of the buffer,
 * w is the base pointer,
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;

if (*p - w < 0)
    *p += M;
}

Here's a coherent post
to the gcc-help list about the subject. Now, I don't want to hear anyone saying
that % is the modulus operator from now on. It's the remainder operator.

Comments (3) Trackbacks (0)
  1. Boo and shame on C. I assume it’s this way in C++ as well?

    What really gets me is the misnomers on the ‘fmod’ and ‘remainder’ functions. The behavior of ‘fmod’ is equivalent to the % operator, while ‘remainder’ does what you (and I) expected of the % operator (cf. the “coherent post”).

    Having that inane behavior for the % operator can be forgiven by claiming it is the “remainder” operator instead of the “modulo” operator, but having ‘fmod’ — whose name implies modulo — follow suite is just wrong. Then backstepping and providing the missing correct behavior through a method named ‘remainder’?! That makes it kind of hard to claim that % is the remainder operator.

    Whoever wrote the 1999 standard obviously didn’t do their math homework…

  2. It’s the same in C++, yes.

  3. Incidentally, looks like Java follows suit.


Leave a comment

No trackbacks yet.