Efficient (cycles wise) algorithm to compute modulo 25?

c, modulo, optimization

Solution

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;
}

Problem

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

Original source