Есть ли альтернатива использованию% (модуль) в C / C ++?

Question

Я где-то однажды читал, что оператор модуля неэффективен на небольших встроенных устройствах, таких как 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;
    }
}

Answer 1

Ах, радости побитовой арифметики. Побочным эффектом многих процедур деления является модуль - поэтому в некоторых случаях деление должно быть быстрее, чем модуль. Мне интересно видеть источник, из которого вы получили эту информацию. У процессоров с множителями есть интересные процедуры деления, использующие множитель, но вы можете перейти от результата деления к модулю всего за два шага (умножить и вычесть), так что он все еще сопоставим. Если в процессоре есть встроенная подпрограмма деления, вы, вероятно, увидите, что он также предоставляет остаток.

Тем не менее, есть небольшая ветвь теории чисел, посвященная Модульная арифметика , которая требует изучения, если вы действительно хотите понять, как оптимизировать работу модуля. Например, модульная арифметика очень удобна для генерации магических квадратов .

Итак, в этом ключе очень низкоуровневый взгляд на математику модуля для примера x, который должен показать вам, насколько просто это можно сравнить с делением:

---

Может быть, лучший способ думать о проблеме с точки зрения числа основания и модульная арифметика. Например, ваша цель - вычислить DOW мод 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

Выраженные таким образом, вы можете отдельно вычислить по модулю 7 результат для старшего и младшего байтов. Умножьте результат для высокого на 4 и добавьте его к минимуму, а затем, наконец, вычислите результат по модулю 7.

Вычисление результата mod 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

Вот процедура liitle для проверки алгоритма

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

Scott

---

Answer 2

Если вы вычисляете числовую моду как некоторую степень двух, вы можете использовать побитовое и оператор. Просто вычтите одно из второго числа. Например:

x % 8 == x & 7
x % 256 == x & 255

Несколько предостережений:

1. работает только , если второе число является степенью двойки.
2. Это только эквивалентно, если модуль всегда положителен. Стандарты C и C ++ не определяют знак модуля, когда первое число отрицательное (до C ++ 11, которое делает гарантирующим, что оно будет отрицательным, что и делало большинство компиляторов) , Побитово и избавляется от знакового бита, так что оно всегда будет положительным (т.е. это истинный модуль, а не остаток). Похоже, это то, что вы все равно хотите.
3. Ваш компилятор, вероятно, уже делает это, когда может, поэтому в большинстве случаев не стоит делать это вручную.

Answer 3

Большую часть времени в использовании по модулю имеют издержки, не являющиеся степенями 2. Это независимо от процессора, поскольку (AFAIK) даже процессоры с операторами модулей делятся на несколько циклов медленнее для деления, чем для операций с маской.

В большинстве случаев это не та оптимизация, которую стоит рассмотреть, и, конечно, не стоит рассчитывать собственную операцию быстрого доступа (особенно, если она все еще включает деление или умножение).

Тем не менее, одним из практических правил является выбор размеров массива и т. Д. С степенями 2.

поэтому, если вычислять день недели, можно использовать% 7 независимо от того, если вы устанавливаете циклический буфер около 100 записей ... почему бы не сделать его 128. Затем вы можете написать% 128, и большинство (все) компиляторы сделают это & ​​0x7F

Answer 4

Если вам действительно не нужна высокая производительность на нескольких встроенных платформах, не меняйте способ кодирования по соображениям производительности, пока не профилируете!

Код, написанный неловко для оптимизации производительности, трудно отлаживать и поддерживать. Напишите тестовый пример и запишите его на своей цели. Как только вы узнаете фактическую стоимость модуля, решите, стоит ли кодировать альтернативное решение.

Answer 5

@ Мэтью прав. Попробуйте это:

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

Answer 6

x%y == (x-(x/y)*y)

Надеюсь, это поможет.

Answer 7

Вы должны действительно проверить необходимое встроенное устройство. Все языки ассемблера, которые я видел (x86, 68000), реализуют модуль, используя деление.

На самом деле, операция сборки деления возвращает результат деления и остаток в двух разных регистрах.

Answer 8

Есть ли у вас доступ к любому программируемому оборудованию на встроенном устройстве? Нравится счетчики и тому подобное? Если это так, вы можете написать аппаратный мод-модуль вместо использования имитированного%. (Я сделал это однажды в VHDL. Не уверен, что у меня все еще есть код.)

Имейте в виду, вы говорили, что деление было в 5-10 раз быстрее. Рассматривали ли вы деление, умножение и вычитание для моделирования мода? (Правка: неправильно истолковано оригинальное сообщение. Мне показалось странным, что деление было быстрее, чем мода, это одна и та же операция.)

В вашем конкретном случае, однако, вы проверяете мод 6. 6 = 2 * 3. Таким образом, вы МОЖЕТЕ получить небольшой выигрыш, если сначала проверите, был ли младший значащий бит 0. Что-то вроде:

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

Однако, если вы сделаете это, я бы порекомендовал подтвердить, что вы получаете какую-то выгоду для профилировщиков. И комментирую. Я бы чувствовал себя плохо из-за следующего парня, который должен смотреть на код иначе.

Answer 9

Во встроенном мире операции «модуля», которые вам нужно выполнять, часто делятся на битовые операции, которые вы можете выполнять с помощью «&» и «|». а иногда '>>'.

Answer 10

Для модуля 6 вы можете изменить код Python на C / C ++:

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number