Подтвердить что ты не робот

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

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

ОТВЕТЫ

Ответ 1

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

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

Итак, в этом ключе, здесь очень низкий уровень просмотра по математике по модулю для примера 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

Выраженный таким образом, вы можете отдельно вычислить модуль 7 результат для высоких и низких байтов. Умножьте результат на высокий 4 и добавьте его к минимуму, а затем окончательно вычислите результат по модулю 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;
}

Я провел несколько минут, написав версию ПОС. Фактическая реализация немного отличается от описанного выше

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

Скотт

Ответ 2

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

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

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

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

Ответ 3

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

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

Однако одно правило состоит в том, чтобы выбрать размеры массива и т.д., чтобы они были равны 2.

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

Ответ 4

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

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

Ответ 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);
  }
}

Ответ 6

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

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

Ответ 7

Во встроенном мире операции "модуля", которые вам нужно выполнять, часто являются теми, которые хорошо разбиваются на операции с битами, которые вы можете делать с помощью & и '|' и иногда " → ".

Ответ 8

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

Помните, вы сказали, что деление было в 5-10 раз быстрее. Вы рассматривали возможность деления, умножения и вычитания на моделирование мода? (Edit: Misunderstood the original post. Я действительно думал, что было странно, что деление было быстрее, чем мода, это одна и та же операция.)

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

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

Если вы это сделаете, я бы рекомендовал подтвердить, что вы получаете прибыль, yay for profilers. И делать некоторые комментарии. Мне было бы плохо для следующего парня, который должен смотреть на код иначе.

Ответ 9

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

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

Ответ 10

Не то, чтобы это было обязательно лучше, но вы могли бы иметь внутренний цикл, который всегда поднимается до FIZZ, и внешний цикл, который повторяет все это определенное количество раз. Тогда вы, возможно, попали в специальный случай в последние несколько шагов, если MAXCOUNT не равномерно делится на FIZZ.

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

Ответ 11

@Jeff V: Я вижу проблему с этим! (Помимо того, что ваш оригинальный код искал мод 6, и теперь вы, по сути, ищете мод 8). Вы продолжаете делать дополнительный +1! Надеюсь, ваш компилятор оптимизирует это, но почему бы просто не начать тестирование с 2 и перейти к MAXCOUNT включительно? Наконец, вы возвращаете true каждый раз, когда (x + 1) НЕ делится на 8. Это то, что вы хотите? (Я предполагаю, что это так, но просто хочу подтвердить.)

Ответ 12

Оператор печати займет порядки больше, чем даже самая медленная реализация модуля модуля. Поэтому в основном комментарий "медленный на некоторых системах" должен быть "медленным во всех системах".

Кроме того, два предоставленных фрагмента кода не делают то же самое. Во второй строке

if(fizzcount >= FIZZ)

всегда false, поэтому "FIZZ\n" никогда не печатается.