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.