Есть ли альтернатива использованию % (модуля) в C/C++?
https://stackoverflow.com/questions/48053
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Однажды я где-то прочитал, что оператор модуля неэффективен на небольших встроенных устройствах, таких как 8-битные микроконтроллеры, которые не имеют инструкции целочисленного деления.Возможно, кто-то сможет это подтвердить, но я думал, что разница в 5-10 раз медленнее, чем при операции целочисленного деления.
Есть ли другой способ сделать это, кроме сохранения переменной счетчика и ручного переполнения до 0 в точке модирования?
const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
против:
Как я это делаю сейчас:
const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
Решение
Ах, радости побитовой арифметики.Побочным эффектом многих процедур деления является модуль, поэтому в некоторых случаях деление должно происходить быстрее, чем модуль.Мне интересно узнать источник, из которого вы получили эту информацию.Процессоры с множителями имеют интересные процедуры деления с использованием множителя, но вы можете получить результат деления по модулю всего за два дополнительных шага (умножить и вычесть), так что результат по-прежнему будет сравним.Если процессор имеет встроенную процедуру деления, вы, вероятно, увидите, что она также вычисляет остаток.
Тем не менее, существует небольшой раздел теории чисел, посвященный Модульная арифметика который требует изучения, если вы действительно хотите понять, как оптимизировать операцию с модулем.Например, модульная арифметика очень удобна для генерации магические квадраты.
Итак, в этом духе, вот внешний вид очень низкого уровня по математике модуля на примере x, который должен показать вам, насколько просто его можно сравнить с делением:
Возможно, лучший способ подумать о проблеме - это число баз и арифметики модуля.Например, ваша цель-вычислить Dow Mod 7, где Dow-16-битное представление дня недели.Вы можете написать это как:
DOW = DOW_HI*256 + DOW_LO
DOW%7 = (DOW_HI*256 + DOW_LO) % 7
= ((DOW_HI*256)%7 + (DOW_LO % 7)) %7
= ((DOW_HI%7 * 256%7) + (DOW_LO%7)) %7
= ((DOW_HI%7 * 4) + (DOW_LO%7)) %7
Выражаемый таким образом, вы можете отдельно вычислить результат Modulo 7 для высоких и низких байтов.Умножьте результат для High на 4 и добавьте его в минимум, а затем, наконец, вычислите результат Modulo 7.
Вычисление мод 7 результат 8-битного числа может быть выполнена аналогичным образом.Вы можете записать 8-битное число в восьмеричном формате следующим образом:
X = a*64 + b*8 + c
Где a, b и c — 3-битные числа.
X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
= (a%7 + b%7 + c%7) % 7
= (a + b + c) % 7
с 64%7 = 8%7 = 1
Конечно, a, b и c
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 // (actually, a is only 2-bits).
Максимально возможное значение для a+b+c является 7+7+3 = 17.Итак, вам понадобится еще один восьмиурочный шаг.Полная (непроверенная) версия C может быть написана как:
unsigned char Mod7Byte(unsigned char X)
{
X = (X&7) + ((X>>3)&7) + (X>>6);
X = (X&7) + (X>>3);
return X==7 ? 0 : X;
}
Я потратил несколько минут на написание PIC-версии.Фактическая реализация немного отличается от описанной выше
Mod7Byte:
movwf temp1 ;
andlw 7 ;W=c
movwf temp2 ;temp2=c
rlncf temp1,F ;
swapf temp1,W ;W= a*8+b
andlw 0x1F
addwf temp2,W ;W= a*8+b+c
movwf temp2 ;temp2 is now a 6-bit number
andlw 0x38 ;get the high 3 bits == a'
xorwf temp2,F ;temp2 now has the 3 low bits == b'
rlncf WREG,F ;shift the high bits right 4
swapf WREG,F ;
addwf temp2,W ;W = a' + b'
; at this point, W is between 0 and 10
addlw -7
bc Mod7Byte_L2
Mod7Byte_L1:
addlw 7
Mod7Byte_L2:
return
Вот небольшая процедура для проверки алгоритма
clrf x
clrf count
TestLoop:
movf x,W
RCALL Mod7Byte
cpfseq count
bra fail
incf count,W
xorlw 7
skpz
xorlw 7
movwf count
incfsz x,F
bra TestLoop
passed:
Наконец, для 16-битного результата (который я не тестировал), вы можете написать:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Скотт
Другие советы
Если вы вычисляете число по модулю некоторой степени двойки, вы можете использовать побитовый оператор и.Просто вычтите единицу из второго числа.Например:
x % 8 == x & 7
x % 256 == x & 255
Несколько предостережений:
- Этот работает только если второе число является степенью двойки.
- Это эквивалентно только в том случае, если модуль всегда положителен.Стандарты C и C++ не указывают знак модуля, если первое число отрицательно (до C++11, который делает гарантировать, что оно будет отрицательным, что уже делало большинство компиляторов).Побитовый и избавляется от знакового бита, поэтому он всегда будет положительным (т. е.это истинный модуль, а не остаток).Хотя, похоже, это то, чего вы хотите.
- Ваш компилятор, вероятно, уже делает это, когда может, поэтому в большинстве случаев делать это вручную не стоит.
В большинстве случаев при использовании модулей, не являющихся степенями 2, возникают накладные расходы.Это независимо от процессора, поскольку (AFAIK) даже процессоры с операторами модуля работают на несколько циклов медленнее для операций деления, чем для операций маски.
В большинстве случаев это не та оптимизация, которую стоит учитывать, и, конечно же, не стоит рассчитывать собственную операцию быстрого доступа (особенно, если она все еще включает в себя деление или умножение).
Однако одно практическое правило — выбирать размеры массива и т. д.быть степенями 2.
Поэтому, если расчет день недели, может также использовать %7 независимо от того, настройка кругового буфера из около 100 записей ...почему бы не сделать это 128.Затем вы можете написать % 128, и большинство (всех) компиляторов сделают это & 0x7F.
Если вам действительно не нужна высокая производительность на нескольких встроенных платформах, не меняйте свой код из соображений производительности, пока не профилируете!
Код, который неуклюже написан для оптимизации производительности, сложно отлаживать и сложно поддерживать.Напишите тестовый пример и профилируйте его для своей цели.Как только вы узнаете фактическую стоимость модуля, решите, стоит ли кодировать альтернативное решение.
@Мэтью прав.Попробуй это:
int main() {
int i;
for(i = 0; i<=1024; i++) {
if (!(i & 0xFF)) printf("& i = %d\n", i);
if (!(i % 0x100)) printf("mod i = %d\n", i);
}
}
x%y == (x-(x/y)*y)
Надеюсь это поможет.
В встроенном мире операции «модуль», которые вам нужно сделать, часто бывают те, которые прекрасно распадаются в битовых операциях, которые вы можете сделать с '&' и '|' '' ' а иногда '>>'.
Есть ли у вас доступ к какому-либо программируемому оборудованию встроенного устройства?Типа счетчиков и прочего?Если да, то вы можете написать аппаратный модуль мода вместо использования имитируемого %.(Я сделал это однажды в VHDL.Не уверен, что у меня все еще есть код.)
Заметьте, вы же сказали, что деление происходит в 5-10 раз быстрее.Рассматривали ли вы возможность деления, умножения и вычитания для имитации мода?(Редактировать:Неправильно понял исходный пост.Мне показалось странным, что деление происходит быстрее, чем модификация, это одна и та же операция.)
Однако в вашем конкретном случае вы проверяете мод 6.6 = 2*3.Таким образом, вы МОЖЕТЕ получить небольшой выигрыш, если сначала проверите, равен ли младший бит 0.Что-то вроде:
if((!(x & 1)) && (x % 3))
{
print("Fizz\n");
}
Однако если вы это сделаете, я бы порекомендовал подтвердить, что вы получите какую-либо выгоду, ура профайлерам.И немного комментирую.Мне было бы жаль следующего парня, которому в противном случае придется смотреть на код.
Вам действительно следует проверить необходимое вам встроенное устройство.Все ассемблерные языки, которые я видел (x86, 68000), реализуют модуль с помощью деления.
Собственно, операция сборки деления возвращает результат деления и остаток в два разных регистра.
Не то чтобы это обязательно было лучше, но вы могли бы иметь внутренний цикл, который всегда доходит до FIZZ, и внешний цикл, который повторяет все это определенное количество раз.Тогда, возможно, вам придется выполнить особый случай на последних нескольких шагах, если MAXCOUNT не делится на FIZZ без остатка.
Тем не менее, я бы посоветовал провести небольшое исследование и профилирование производительности на ваших предполагаемых платформах, чтобы получить четкое представление об ограничениях производительности, с которыми вы столкнулись.Возможно, есть гораздо более продуктивные места, на которые можно потратить усилия по оптимизации.
@Джефф В:Я вижу в этом проблему!(Кроме того, ваш исходный код искал мод 6, а теперь вы, по сути, ищете мод 8).Вы продолжаете делать дополнительный +1!Надеюсь, ваш компилятор оптимизирует это, но почему бы просто не начать с 2 и не перейти к MAXCOUNT включительно?Наконец, вы возвращаете true каждый раз, когда (x+1) НЕ делится на 8.Это то что ты хочешь?(Я предполагаю, что да, но просто хочу подтвердить.)
Для модуля 6 вы можете изменить код Python на C/C++:
def mod6(number):
while number > 7:
number = (number >> 3 << 1) + (number & 0x7)
if number > 5:
number -= 6
return number
Оператор печати займет на порядки больше времени, чем даже самая медленная реализация оператора модуля.Таким образом, по сути комментарий «медленно на некоторых системах» должен быть «медленно на всех системах».
Кроме того, два предоставленных фрагмента кода не делают одно и то же.Во втором строка
if(fizzcount >= FIZZ)
всегда ложно, поэтому «FIZZ » никогда не выводится.
