10

I'm trying to write a function that answers the question: if you start counting at a and stop counting at b, is c in that range (aka is c between a and b).

Normally a < c && c < b would suffice, but I'm in modular arithmetic:

(Diagram)

Counter-clockwise is increasing.

Green colors: are values for c where the algorithm should indicate true (where c is between a and b)

Blue colors: are values for c where the algorithm should indicate false (where c is not between a and b) (which happens to be the same as where c is between b and a)

The simple a < c && c < b fails where the range of a and b crosses over 0.

For example, say A = 300 and B = 45. If C is 10 then the function should return true: 300, 301, 302 ... 359, 0, 1, 2, 3 ... 8, 9, 10, 11, 12 ... 43, 44, 45. Therefore, 10 is between 300 and 45 in mod 360.

Ultimately, what I'm trying to determine is if one hue is between two other hues, where hues are specified in degrees around a color wheel (which is a mod 360 system). It would be great if the answer was in terms of mod n so it would solve the general case and not be specific to my problem though.

Kevin Johnson
  • 913
  • 7
  • 24

3 Answers3

7

First calculate a mod n, b mod n, and c mod n.

If a < b then we need to check that a < c && c < b. This is the simple case where modular arithmetic doesn't play a huge role.

Because [a, b] and [b, a] form disjoint regions, instead of trying to deal with the problem of crossing 0, we can test the reverse for cases where b < a. If b < c && c < a is true, c is actually between b and a and therefore not between a and b.

Code sample:

a = a % n;  // % = mod
b = b % n;
c = c % n;

if (a < b) {
    if (a < c && c < b) return true;
    else return false;
} else { // b < a
    if (b < c && c < a) return false;   // if in [b, a] then not in [a, b]
    else return true;
}
Kevin Johnson
  • 913
  • 7
  • 24
xashru
  • 3,400
  • 2
  • 17
  • 30
  • One-liner (assuming _a_, _b_ and _c_ are already in _[0,n)_ ): `return (a < b) ? (a < c && c < b) : !(b < c && c < a);` – kassiopeia Nov 18 '18 at 20:06
3
bool between = C<A ^ C<B ^ B<A;
I. J. Kennedy
  • 24,725
  • 16
  • 62
  • 87
1

The number will be between the given two numbers if either of following three conditions is satisfied.

Condition 1:

c mod n > a mod n && c mod n < b mod n

Condition 2:

a mod n > b mod n && c mod n < b mod n.

Condition 3:

a mod n > b mod n && c mod n > a mod n.
Sumeet
  • 8,086
  • 3
  • 25
  • 45
  • @KevinJohnson The first condition is straight forward. – Sumeet Aug 07 '15 at 08:38
  • @KevinJohnson The second and third condition handles the case of modulo arithmetic. Just take some examples and it will be clear. – Sumeet Aug 07 '15 at 08:39