Re реализовать modulo с помощью бит сдвигов?

Я пишу код для очень ограниченной системы, в которой оператор mod работает очень медленно. В моем коде модулю нужно использовать примерно 180 раз в секунду, и я решил, что удаление его в максимально возможной степени значительно увеличит скорость моего кода, так как теперь один цикл моего mainloop не работает в 1/60 вторых, как следует. Мне было интересно, возможно ли повторное внедрение модуля, используя только бит-сдвиги, как это возможно при умножении и делении. Итак, вот мой код до сих пор в С++ (если я смогу выполнить модульную сборку, было бы еще лучше). Как удалить модуль без использования деления или умножения?

    while(input > 0)
{
    out = (out << 3) + (out << 1);
    out += input % 10;

    input = (input >> 8) + (input >> 1);
}

EDIT: На самом деле я понял, что мне нужно делать это более 180 раз в секунду. Увидев, что значение ввода может быть очень большим числом до 40 цифр.

Ответ 1

Что вы можете сделать с помощью простых побитовых операций, это взять по модулю (делитель) значение (divend) по модулю (2) по модулю (divend) с помощью AND'ing с делителем-1. Несколько примеров:

unsigned int val = 123; // initial value
unsigned int rem;

rem = val & 0x3; // remainder after value is divided by 4. 
                 // Equivalent to 'val % 4'
rem = val % 5;   // remainder after value is divided by 5.
                 // Because 5 isn't power of two, we can't simply AND it with 5-1(=4).

Почему это работает? Рассмотрим рассмотренный битовый шаблон для значения 123, который является 1111011, а затем делителем 4, который имеет бит-шаблон 00000100. Как мы уже знаем, дивизор должен быть степенным из двух (как 4), и нам нужно уменьшить его на единицу (от 4 до 3 в десятичной), что дает нам бит-шаблон 00000011. После того, как мы побитовым - и как оригинальные 123, так и 3, результирующий битовый шаблон будет 00000011. Это оказывается равным 3 в десятичном значении. Причина, по которой нам нужен делитель power-of-two, состоит в том, что, когда мы уменьшаем их на единицу, мы получаем все менее значимые биты, установленные на 1, а остальные 0. Как только мы выполняем побитовое-И, оно "отменяет" более значимые биты от исходного значения и оставляет нас просто с остатком исходного значения, деленным на делитель.

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

Также есть предыдущий вопрос, связанный с предметом, который, вероятно, имеет интересную информацию по этому вопросу с разных точек зрения.

Ответ 2

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

Но есть очевидная сделка пространства-времени, которую вы можете сделать здесь: настройте таблицу значений для out и out % 10 и найдите ее. Тогда линия становится

  out += tab[out]

и с какой-либо удачей, это окажется одной из 16-разрядных операций добавления и хранения.

Ответ 3

Если вы хотите сделать modulo 10 и смены, возможно, вы можете адаптировать двойной алгоритм поиска к вашим потребностям?

Этот алгоритм используется для преобразования двоичных чисел в десятичные без использования модуля или деления.

Ответ 4

Каждая степень 16 заканчивается на 6. Если вы представляете число как сумму степеней 16 (т.е. разбиваете его на nybbles), то каждый член вносит последнюю цифру таким же образом, за исключением одного места.

0x481A % 10 = ( 0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA ) % 10

Заметим, что 6 = 5 + 1, а 5 будет отменено, если их четное число. Поэтому просто суммируйте nybbles (кроме последнего) и добавьте 5, если результат нечетный.

0x481A % 10 = ( 0x4 + 0x8 + 0x1 /* sum = 13 */
                + 5 /* so add 5 */ + 0xA /* and the one place */ ) % 10
            = 28 % 10

Это уменьшает 16-битный, 4-nybble по модулю до числа не более 0xF * 4 + 5 = 65. В двоичном, это досадно еще 3 nybbles, поэтому вам нужно будет повторить алгоритм (хотя один из них действительно не учитывается).

Но у 286 должно быть достаточно эффективное добавление BCD, которое вы можете использовать для выполнения суммы и получения результата за один проход. (Это требует преобразования каждого nybble в BCD вручную, я недостаточно знаю о платформе, чтобы сказать, как оптимизировать это или проблематично.)

Ответ 5

Фактически деление на константы является хорошо известной оптимизацией для компиляторов, и на самом деле gcc уже делает это.

Этот простой фрагмент кода:

int mod(int val) {
   return val % 10;
}

Создает следующий код на моем довольно старом gcc с -O3:

_mod:
        push    ebp
        mov     edx, 1717986919
        mov     ebp, esp
        mov     ecx, DWORD PTR [ebp+8]
        pop     ebp
        mov     eax, ecx
        imul    edx
        mov     eax, ecx
        sar     eax, 31
        sar     edx, 2
        sub     edx, eax
        lea     eax, [edx+edx*4]
        mov     edx, ecx
        add     eax, eax
        sub     edx, eax
        mov     eax, edx
        ret

Если вы игнорируете функцию epilogue/prologue, в основном два muls (действительно, на x86 нам повезло и я могу использовать lea для одного) и некоторые смены и добавляет /subs. Я знаю, что я уже объяснил теорию, лежащую в основе этой оптимизации, поэтому я посмотрю, смогу ли я найти этот пост, прежде чем объяснять его еще раз.

Теперь на современных процессорах, которые, безусловно, быстрее, чем доступ к памяти (даже если вы попали в кеш), но будет ли это быстрее для вашего явно более древнего процессора - вопрос, на который можно ответить только с помощью бенчмаркинга (а также убедитесь, что ваш компилятор делает эту оптимизацию, иначе вы всегда можете просто "украсть" версию gcc здесь;)). Особенно учитывая, что это зависит от эффективных муллов (т.е. более высоких бит команды умножения), чтобы быть эффективными. Обратите внимание, что этот код не не зависит от размера - точнее, изменяется магическое число (а может быть, и части добавления/сдвига), но это может быть адаптировано.

Ответ 6

Получите копию Jon Bentley "Написание эффективных программ" (печально печатается, резюме в его "Programming Pearls" ). В нем обсуждается, как (и когда!) Выжать последнюю каплю производительности из программ. Простые изменения, которые обсуждаются здесь, сделаны, конечно, текущими компиляторами, проверяют код ассемблера альтернативных источников и сохраняем все более четкое.