9

I'm a little freaked out by the results I'm getting when I do modulo arithmetic in Objective-C. -1 % 3 is coming out to be -1, which isn't the right answer: according to my understanding, it should be 2. -2 % 3 is coming out to -2, which also isn't right: it should be 1.

Is there another method I should be using besides the % operator to get the correct result?

Greg Maletic
  • 6,225
  • 8
  • 54
  • 73
  • curious if any of these answers re modulo were what you were looking for – kris Nov 10 '11 at 16:02
  • 1
    Use frem(a,b) — the modulo you are expecting (which is the kind used in standard math) is called "remainder" in coding. C has fmod() and frem(), you are using mod (aka "%"), you need to use rem. Modulo in Math === Remainder (rem) in code. Dumb, I know. – Albert Renshaw Jul 07 '16 at 07:36
  • It's been brought to my attention that frem(a,b) was in GNU C only and not carried into Obj-C. The equivalent would be this: `a-b*floor((float)a/(float)b)` – Albert Renshaw Jul 07 '16 at 07:44

5 Answers5

7

Objective-C is a superset of C99 and C99 defines a % b to be negative when a is negative. See also the Wikipedia entry on the Modulo operation and this StackOverflow question.

Something like (a >= 0) ? (a % b) : ((a % b) + b) (which hasn't been tested and probably has unnecessary parentheses) should give you the result you want.

Community
  • 1
  • 1
Isaac
  • 10,668
  • 5
  • 59
  • 68
  • Great! It worked for me, however I encountred 2 situations that caused me error: (1) -n mod n gives n instead of 0. (2) when defining it as a macro, some parenthesis where confused. I end up doing: #define module(a, b) (a >= 0 || -(a) == (b)) ? (a)%(b) : ((a)%(b) + b) – kahlo Aug 25 '13 at 20:10
3

Spencer, there is a simple way to think about mods (the way it's defined in mathematics, not programming). It's actually rather straightforward:

Take all the integers:

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

Now let's think about multiples of 3 (if you are considering mod 3). Let's start with 0 and the positive multiples of 3:

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

These are all the numbers that have a remainder of zero when divided by 3, i.e. these are all the ones that mod to zero.

Now let's shift this whole group up by one.

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

These are all the numbers that have a remainder of 1 when divided by 3, i.e. these are all the ones that mod to 1.

Now let's shift this whole group up again by one.

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

These are all the numbers that have a remainder of 2 when divided by 3, i.e. these are all the ones that mod to 2.

You'll notice that in each of these cases, the selected numbers are spaced out by 3. We always take every third number because we're considering modulo 3. (If we were doing mod 5, we'd take every fifth number).

So, you can carry this pattern backwards into the negative numbers. Just keep the spacing of 3. You'll get these three congruence classes (a special type of equivalence classes, as they're called in mathematics):

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

...-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...

The standard mathematical representation of all of these equivalent numbers is to use the residue of the class, which just means take the smallest non-negative number.

So usually, when I'm thinking about mods and I'm dealing with a negative number, I just think of successively adding the modulo number again and again until I get the first 0 or positive number:

If we're doing mod 3, then with -1, just add 3 once: -1 + 3 = 2. With -4, add 3 twice because once isn't enough. If we add +3 once, we get -4 + 3 = -1, which is still negative. So We'll add +3 again: -1 + 3 = 2.

Let's try a larger negative number, like -23. If you keep adding +3, you'll get:

-23, -20, -17, -14, -11, -8, -5, -2, 1. We got a positive number, so we stop. The residue is 1, and this is the form that mathematicians typically use.

Dave
  • 41
  • 2
2

ANSI C99 6.5.5 Multiplicative operators-

6.5.5.5: The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.

6.5.5.6: 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.

*90: This is often called "truncation toward zero".

The type of modulo behavior you're thinking of is called "modular arithmetic" or "number theory" style modulo / remainder. Using the modular arithmetic / number theory definition of the modulo operator, it is non-sensical to have a negative result. This is (obviously) not the style of modulo behavior defined and used by C99. There's nothing "wrong" with the C99 way, it's just not what you were expecting. :)

johne
  • 6,760
  • 2
  • 24
  • 25
1

I had the same problem, but I worked it out! All you need to do is check if the number is positive or negative and if it's negative, you need to add one more number:

//neg 
// -6 % 7 = 1
int testCount = (4 - 10);
if (testCount < 0) {
  int  moduloInt = (testCount % 7) + 7; // add 7
    NSLog(@"\ntest modulo: %d",moduloInt);
}
else{
  int moduloInt = testCount % 7;
    NSLog(@"\ntest modulo: %d",moduloInt);
}

// pos
// 1 % 7 = 1
int testCount = (6 - 5);
if (testCount < 0) {
  int  moduloInt = (testCount % 7) + 7; // add 7
    NSLog(@"\ntest modulo: %d",moduloInt);
}
else{
  int moduloInt = testCount % 7;
    NSLog(@"\ntest modulo: %d",moduloInt);
}

Hope that helps! A.

Alessign
  • 768
  • 9
  • 17
0

An explicit function that will give you the correct answer is at the end, but first, here is an explanation of some of the other ideas that were discussed:

Actually, (a >= 0) ? (a % b) : ((a % b) + b) will only result in the correct answer if the negative number, a, is within one multiple of b.

In other words: If you want to find: -1 % 3, then sure, (a >= 0) ? (a % b) : ((a % b)+ b) will work because you added back at the end in ((a % b) + b).

-1 % 3 = -1 and -1 + 3 = 2, which is the correct answer.

However, if you try it with a = -4 and b = 3, then it won't work:

-4 % 3 = -4 but -4 + 3 = -1.

While this is technically, also equivalent to 2 (modulo 3), I don't think this is the answer you are looking for. You're probably expecting the canonical form: which is that the answer should always be a non-negative number between 0 and n-1.

You'd have to add +3 twice to get the answer:

-4 + 3 = -1
-1 + 3 = 2

Here is an explicit way to do it:

a - floor((float) a/b)*b

** Be careful! Make sure you keep the (float) cast in there. Otherwise, it will divide a/b as integers and you'll get an unexpected answer for negatives. Of course this means that your result will be a float, too. It will be an integer written as a float, like 2.000000, so you might want to convert the whole answer back to an integer.

(int) (a - floor((float) a/b)*b)
Dave
  • 41
  • 2