Algorithms

5-Jul-11 1:44

I have made a lot of modulo things last days and it's totally blowing my mind. Dead | X|

Could somebody give me a hand with this one?
I'd like to replace this snippet:

while (x < -7)
    x += 12;
while (x > 7)
    x -= 12;

with some smart modulo one-liner. Any ideas?

Greetings - Jacek

David19875-Jul-11 2:05

5-Jul-11 2:05

Are you sure it is correct? Shouldn't it be

while (x <= -7)
    x += 12;
while (x >= 7)
    x -= 12;

If indeed it should be that, maybe x = ((x + 6) % 12) - 6; would work (not tested)

BobJanova5-Jul-11 2:38

5-Jul-11 2:38

I agree that the question was probably meant to constrain to ±6. ~~I would use ((x+18)%12)-6 because mod with negative numbers doesn't do what you expect, in some languages at least.~~
Edit: that sentence was rubbish, the number needs to be brought into [-18,] before that is useful.

This has a potential overflow if x can be near the top of the range for the numeric type in question. To avoid that you can do something like

x = x % 12; // -11 to +11
if(x < 0) x += 12; // 0 to +11
if(x > 6) x -= 12; // -5 to +6

(You can one line it: x = (((x%12)+18)%12) - 6 ... but two mods is likely to be slower than the branched version. You can also one line the branches:

x = (x = (x = x % 12) < 0 ? x + 12 : x) > 6 ? x - 12 : x;

... but your manager is likely to shoot you and it is no faster.)

David19875-Jul-11 3:13

5-Jul-11 3:13

You're right of course, so have your 5 Smile | :)

Lutosław5-Jul-11 2:47

5-Jul-11 2:47

No, it shouldn't. The original post was correct.

Greetings - Jacek

David19875-Jul-11 3:06

5-Jul-11 3:06

That's unusual and I couldn't find a simple solution, but I found a way that at least removes the loops.

static int SpecialModulo(int x)
{
    x = x % 12;
    if (x < 0)
        return x < -7 ? x + 12 : x;
    else
        return (x & 7) - ((x & 8) >> 1);
}

Lutosław5-Jul-11 5:19

5-Jul-11 5:19

(x & 7) - ((x & 8) >> 1);

Could you explain this line of code? I seriously don't know what does it do.

Greetings - Jacek

BobJanova5-Jul-11 5:45

5-Jul-11 5:45

If it's above 7 (well, 7-15, but we have done mod 12 already), i.e. it has an 8 bit set, it drops the 8 bit (via the &7) and subtracts 4 (x&8 will be 8), i.e. subtracts 12. I would think that x-12 would be faster though so I'm not sure why it's written this way.

David19875-Jul-11 6:03

5-Jul-11 6:03

Because you shouldn't Always subtract 12, but only when it is bigger than 7. Of course a conditional would also work

BobJanova5-Jul-11 7:13

5-Jul-11 7:13

Yes, I meant

if(x > 7) x -= 12;

... apologies for missing the first part. I still think that will be faster than the ands, shift and subtract, though it would be close.

BobJanova5-Jul-11 3:13

5-Jul-11 3:13

Ok, so what you want to do is map numbers over 7 onto [-5, 7], and those below -7 onto [-7, 5]. Your modulo is 12 but the range size is 14, so there won't be a one liner with mod. I can make one with a ternary:

x += 12 * (((x < -7) ? 5 - x : (x > 7) ? -5 - x : 0) / 12);

... though, as above, this can overflow, and it is probably better to do

if(x < -7){
  x = (x + 7) % 12; // -11 to 0
  if(x < -7) x += 12;
} else if(x > 7) {
  x = (x - 7) % 12; // 0 to 11
  if(x > 7) x -= 12;
}

David19875-Jul-11 3:14

5-Jul-11 3:14

Yea that's probably better than mine..

Lutosław5-Jul-11 5:13

5-Jul-11 5:13

Actually, it is impossible for x to exceed range (-12,12). I have changed from if to while "just in case", but I doubt there would be more than one iteration. So, since a solution with modulo seems to be very sophisticated and not clear then I decide to use a more readable form with while "loops".
I just though that there is a simple solution in form (x - a)%b+c which I missed.

Anyway, thanks for help. Sincerely, your modulo skills impressed me (that ternary thing is awbeatyful).

Greetings - Jacek

BobJanova5-Jul-11 5:43

5-Jul-11 5:43

For a constrained range the simple version with ifs (I don't really recommend the ternary approach in production code, it's just fun to see what you can do with it) will be faster than any 'clever' approach with a modulo. Mod and div are extremely slow and a couple of branches to do the same task as one should win.

You shouldn't use the while loops if you have set your domain to (-12,12). They are adding an extra test for nothing, but worse, they are confusing to people reading the code (including yourself in three months) because it looks like the domain is unconstrained. If you're concerned you can put a range check and throw an exception (or language equivalent, this could be any C family language) if the input is outside the domain.

David19875-Jul-11 6:19

5-Jul-11 6:19

I started doing crazy things such as:

static int SpecialModulo(int x)
{
    return (x & 7) - ((x & 8) >> 1) - ((x >> 31) & 4);
}

Trying to make a branchless version..

And then I realized.. why not just use a lookup table?

int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };

x = table[x + 12]; // that's all

Lutosław5-Jul-11 6:46

5-Jul-11 6:46

int[] table = new int[] { 0, 1, 2, 3, 4, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, -4, -3, -2, -1 };
 
x = table[x + 12]; // that's all

Nice. I think you missed %table.Length though.

Greetings - Jacek

David19875-Jul-11 6:53

5-Jul-11 6:53

Not if x is only in [-12, 12], which you said at some point..

As an alternative I have a slower way that only uses arithmetic (I just like doing that)

(((abs(x)+4)%12)-4)*sign(x)

int abs(int x)
{
    int t = x >> 31;
    return (x + t) ^ t;
}

int sign(int x)
{
    // -1 for x < 0, 1 for x >= 0
    return 1 | (x >> 31);
}

Lutosław5-Jul-11 7:24

5-Jul-11 7:24

If x==12 then table[x+12]=table[24] is out of bounds. Also, without %, most of the "lookup table" would be wasted.

David1987 wrote:
(I just like doing that)

Which is noticable. Laugh | :laugh:

Greetings - Jacek

David19875-Jul-11 7:40

5-Jul-11 7:40

Jacek Gajek wrote:
If x==12 then table[x+12]=table[24] is out of bounds.

Okay.. add one more item.

Jacek Gajek wrote:
Also, without %, most of the "lookup table" would be wasted.

Would it be? x can be any value in [-12,12], right? That's pretty much all items in that table .. and one more yes, I missed the last one

Lutosław5-Jul-11 10:47