Мне нужно оптимизировать эту действительно крошечную, но надоедливую функцию.
unsigned umod(int a, unsigned b)
{
while(a < 0)
a += b;
return a % b;
}
Прежде чем вы начнете кричать "Вам не нужно его оптимизировать", имейте в виду, что эта функция называется 50% всей продолжительности жизни программы, так как она называется 21495808 раз для самого маленького теста.
Эта функция уже встроена в компилятор, поэтому не предлагайте добавить ключевое слово inline.
Это должно сделать это:
unsigned umod(int a, unsigned b)
{
if (a < 0)
{
unsigned r = (-a % b);
if (r)
return b - r;
else
return 0;
}
else
return a % b;
}
Протестировано для соответствия оригиналу. Ограничение заключается в том, что a > INT_MIN на машинах с дополнением 2s.
Это позволяет избежать цикла:
int tmp = a % b;
if (tmp < 0) tmp += b;
Обратите внимание, что должны быть подписаны как a, так и b.
Использование символа ~:)
unsigned umod(int a, unsigned b)
{
if (a<0) return b-1-~a%b;
return a%b;
}
% имеет более высокий приоритет, чем -
Если это нормально, чтобы вернуть b вместо 0, когда -a кратно b, вы можете сохранить некоторые операционные системы
unsigned umod(int a, unsigned b)
{
if (a<0) return b - (-a % b);
return a%b;
}
слегка голая версия:)
unsigned umod(int a, unsigned b)
{
return(a<0)?b-(-a%b):a%b;
}
Вот результирующая сборка
1 .globl umod3
2 .type umod3, @function
3 umod3:
4 .LFB3:
5 .cfi_startproc
6 testl %edi, %edi
7 js .L18
8 movl %edi, %eax
9 xorl %edx, %edx
10 divl %esi
11 movl %edx, %eax
12 ret
13 .p2align 4,,10
14 .p2align 3
15 .L18:
16 movl %edi, %eax
17 xorl %edx, %edx
18 negl %eax
19 divl %esi
20 subl %edx, %esi
21 movl %esi, %edx
22 movl %edx, %eax
23 ret
Так как циклическая версия кажется довольно быстрой, попробуйте исключить разделение:)
unsigned umod(int a, unsigned b){
while(a>0)a-=b;
while(a<0)a+=b;
return a;
}
Портативная версия, все еще с одним делением, без ветвления и без умножения:
unsigned umod(int a, unsigned b) {
int rem = a % (int) b;
return rem + (-(rem < 0) & b);
}
В исходной функции вы могли бы вернуться после завершения цикла while для отрицательных чисел, тем самым пропустив мод. Это в том же духе, заменив цикл на умножение - хотя его можно было бы сделать с меньшим количеством символов...
unsigned int umod2(int a, unsigned int b)
{
return (a < 0) ? a + ((-a/b)+1)*b : a % b;
}
Здесь версия цикла:
unsigned int umod2_works(int a, unsigned int b)
{
if (a < 0)
{
while (a < 0)
a += b;
return a;
} else {
return a % b;
}
}
Оба были протестированы в соответствии с исходной функцией OP.
В a % b, если какой-либо из операндов unsigned, оба преобразуются в unsigned. Это означает, что если a отрицательно, вы получите значение modulo UINT_MAX + 1 вместо a. Если UINT_MAX+1 равномерно делится на b, тогда все будет хорошо, и вы можете просто вернуть a % b. Если нет, вы делаете modulo в типе int.
unsigned int umod(int a, unsigned int b)
{
int ret;
if (a >= 0) return a % b;
if (b > INT_MAX) return a + b;
ret = a % (int)b;
if (ret < 0) ret += b;
return ret;
}
Изменить: обновлено, но вы должны использовать ответы в качестве более простого (или, может быть, нет?!). Это здесь для записи.
int temp;
temp= (a > 0)? ( a % b ) : b -( (-a) % b ) ;
ниже:
int main()
{
int a;
unsigned b;
int temp;
printf("please enter an int and a unsigned number\n");
scanf("%d",&a);
scanf("%u",&b);
modulus(a,b);
temp= (a > 0)? ( a % b ) : b -( (-a) % b ) ;
printf("\n temp is %d", temp);
return 0;
}
void modulus(int x,unsigned y)
{
int c;
if(x>0)
{
c=x%y;
printf("\n%d\n",c);}
else
{
while(x<0)
x+=y;
printf("\n%d\n",x);}
}
./a.out
please enter an int and a unsigned number
-8 3
1
temp is 1
Здесь, который работает во всем диапазоне без знака без ветвления, но использует умножения и 2 деления
unsigned umod(int a, unsigned b)
{
return (a>0)*a%b+(a<0)*(b-1-~a%b);
}
Если a и b оба намного меньше, чем int, тогда вы можете просто добавить достаточно большой кратный b для каждого значения до вашего мода.
unsigned umod(int a, unsigned b)
{
return (unsigned)(a + (int)(b * 256)) % b;
}
Конечно, этот трюк не работает, если + (b * 256) может переполняться, но для многих видов использования, которые я вижу для этого кода, вы можете быть уверены, что он никогда не будет.
Кроме цикла while, не уверен, может ли операция% быть оптимизирована в целом, но оптимизация может произойти по шаблону значений для a и b.
Если в течение этих 21495808 раз выполняется операция.
Если вероятность передачи значения для a, которое меньше b (a < b), составляет по меньшей мере половину этого. Добавление следующего утверждения, безусловно, улучшит общую производительность функции.
if ( abs(a) < b ) // not specifically the abs function, can be your own implementation.
return 0;
else
return a%b;
Если b является степенью 2 для не более 80% случаев, мы можем использовать побитовые операторы, как в
return ( abs(a) & (b-1) );
Если ожидается, что числа будут чем-то меньшим, это снизит производительность, так как нам нужно проверить, является ли b мощностью 2 [даже после использования побитовых операторов для того же самого] для всего.
Даже функциональность для достижения абс (а) может быть оптимизирована с использованием побитовых операторов с их собственными ограничениями, но быстрее, чем проверка того, является ли значение < 0.
n = (a ^ (a >> 31)) - (a >> 31); // instead of n = a < 0 ? -a : a;
Было бы больше таких вещей, если вы можете исследовать.
Мое предпочтительное решение - в два раза. Я не пробовал это в C/С++ или с unsigned, но мои тестовые примеры работают на Java:
((a % b) + b) % b
Преимущество - это не ветвление и простота. Недостатком является двойной мод. Я не сравнивал производительность, но я понимаю, что это ветвление, которое вредит производительности в наши дни.