Efficient (cycles wise) algorithm to compute modulo 25?

Question

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

Answer 1

I suggest reading Hacker's Delight. It describes very fast remainder algorithms for constant divisors. They would almost certainly beat a general algorithm.

Update: Here is some example code... It can probably be reworked to avoid the temporary long long.

unsigned mod25(unsigned n)
{
    unsigned reciprocal = 1374389535; // 2^35 / 25
    unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
    return n - div25 * 25;
}