Если ваш компилятор C ориентирован на ЦП без инструкции деления, вы можете изменить свой код следующим образом:
mod(a, b) {
int s = b + b + b + b;
int r = a;
while(r >= s) {
r -= s;
}
while(r >= b) {
r -= b;
}
return r;
}
Это работает путем вычитания значений в кусках по четыре, а не в один, вплоть до последнего, затем переключается на вычитание кусков по одному.
Это должно заставить ваш код работать примерно в четыре раза быстрее (при условии, что 4*b не находится вне диапазона ваших целых чисел). Вы могли бы даже вставить больше петель (скажем, 8*b один) перед 4*b, чтобы увеличить скорость.
Кроме этого, ассемблер ручного кодирования может помочь, но я думаю, что вы найдете существенный эффект от приведенного выше кода без него.
Если вы знаете больше подробностей о том, как вы будете использовать вызов мод, вы можете оптимизировать его для ваших конкретных случаев. Например, если вы хотите знать только по модулю 25 16-разрядное целое число, следующий код будет намного быстрее, чем упрощенный цикл с переменным знаменателем.
int mod25 (int a) { // a has maximum value of 2^15-1 = 32767
while (a >= 15625) a-= 15625; // at most 2 times.
while (a >= 625) a-= 625; // at most 24 times.
while (a >= 25) a-= 25; // at most 24 times.
return a;
}
Выполняя тест, я обнаружил, что вам нужно сделать 10 миллионов итераций, прежде чем появится заметная разница между этим модулем кода и использованием оператора % (2 секунды против 0 секунд). До этого момента они оба составляли 0 секунд, хотя они выполнялись на быстрой машине (лучше для mod25) и с инструкцией a div (лучше для оператора %), так что вы ' мне нужно сравнить его на своем собственном оборудовании.
Это почти так же быстро, как вы, вероятно, получите, не делая ваш код нечитаемым (хотя даже это не должно вас останавливать, если вы хотите добавить множество комментариев, объясняющих, как он работает).
Более общее решение для любого знаменателя состоит в том, чтобы сначала удвоить знаменатель (с битовыми сдвигами для скорости) настолько, насколько это возможно, чтобы минимизировать последующие вычитания. Затем, по мере того как числитель уменьшается ниже увеличенного знаменателя, делите пополам знаменатель и продолжайте движение (пока знаменатель не вернется в начало).
int mod (int n, int d) {
/* dx is the adjusted denom, don't let it overflow though. */
int dx = d;
while (((dx << 1) >>1) == dx)
dx <<= 1;
/* This loop processes the dx values until they get too small. */
while (dx >= d) {
/* This loop subtracts the large dx value. */
while (n >= dx)
n -= dx;
dx >>= 1;
}
return n;
}
На самом деле это работает наравне с оптимизированной версией mod25 выше, обеспечивая более общее решение.