Efficient (cycles wise) algorithm to compute modulo 25?

Asked 2009-06-11T12:01:38.043

I have a code in which i am computing x % 25. x always takes a positive value but its dynamic range is large.

I found out that this particular code piece of computing a x % 25 is taking large cycles. I need to optimize it.

Pre-computed lookup table is ruled out due to the possible large memory size of the table.

As second approach i coded a fragment below(C code) -

mod(a, b)
{   
    int r = a;  
    while(r >= b)
    {      
        r = r - b;
    }   
    return r;
}

1.) How can i optimize this code further for cycles(squeeze it to max)?

2.) Is there any entirely different optimized way to achieve x % 25( i know its not a common operation, but still, looking for clever inputs people might have used in their experience which might nelp me.).

Thank you.

-AD

EDIT:

I think using a native modulo operator % in C , internally uses a division operation (/) which is costly on the processor i am using.(No div instruction). hence trying to see if custom implemetation can beat the inherent computation using % operator.

-AD

c optimization modulo

Edit Report

4 Answers

Oh my <deity of choice>. I can't believe some of these answers.

First thing, repeated subtraction, even Pax's version, will never, ever be optimal. Consider, the following:

20 % 25

that's easy and fast using repeated subtraction, but:

65535 % 25

will be horribly slow, 600+ iterations. That's an average of 300 iterations for 16 bit numbers. As for 32 bit number, well, just don't even go there.

The fastest way to do this is to use long division. See Niki's answer.

But, this is what the compiler will be generating anyway, at least, one would hope it is what the compiler is generating. It's always best to check if you're using a compiler for a niche processor.

The best way to speed this up is to not do the modulus in the first place. Why do you need to get the modulus and can you re-factor the code / algorithm to avoid the modulus, or at least, make the modulus trivial.

answered 2009-06-11T12:46:40.947

On many processors, integer multiplication is faster than integer division. This blog post shows how to replace a constant integer division with a constant integer multiplication. By rearranging the maths a bit you can get the remainder instead of the quotient. Note, however, that if you are using a moderately sophisticated compiler, then this is already done for you. You just write x % 25 and the compiler works out the rest. You should check the generated assembly code for your code, verifying that the compiler has not done this already, before doing this optimisation in C. Also, you should measure (profile) the performance before and after to ensure that you really are making things faster.

Looping will be far slower than doing the division using the native instruction for reasonably large operands.

Edit: see also this paper.

answered 2009-06-11T13:10:09.050

Is there a reason why you cant use C's built in modulus operator?

int a = x % 25;

Following your edit;

If your rpocessor does not have built in modulo support then I would still use the % operator for the simple reason that your compiler will know that the processor in question doesnt have a native % function, and will likely produce asm code to optimally emulate it.

Put it this way - I'd be fascinated if you can come up with a genarl algorithm that outperforms whatevr the compiler produces from using the built in operator, notwithsatanding specific cases (such as simply taking the 2 lowest digits for modulo 100 etc)

answered 2009-06-11T12:10:23.123

If you kept your numbers in BCD or a byte array of digits, this would be pretty easy. Unfortunately, I have no idea what else you're doing in your program with these numbers. Sometimes it pays to look at how you represent your data rather than just bang away at algorithms.

answered 2009-06-12T00:28:05.160

Efficient (cycles wise) algorithm to compute modulo 25?

4 Answers

Your Answer