Реализовать по модулю, используя битовые сдвиги?

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

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

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

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

 Mysticial18 июн. 2012 г., 04:08
Удовлетворяет ли модуль каким-либо свойствам? Вы используете один и тот же модуль много раз. Если это не так, я сомневаюсь, что вы можете сделать что-то лучше, чем инструкция по аппаратному разделению.
 Mysticial18 июн. 2012 г., 04:02
180 раз в секунду ... на каком оборудовании? Это ничего не значит для современного не встроенного процессора.
 PgrAm18 июн. 2012 г., 04:05
На 16-битном процессоре. Я знаю, что нет ничего, кроме большого количества другого кода, который необходимо завершить за 1/60 секунды, и по модулю это должно происходить три раза за каждый цикл основного цикла. Я хочу выжать как можно больше скорости.
 ildjarn18 июн. 2012 г., 05:23
@PgrAm: & quot;I need 286 support& Quot; Какие? Зачем? На какой планете ты живешь?
 std''OrgnlDave18 июн. 2012 г., 05:29
40 цифр? 64-разрядное число - только 19,1 цифры. как ваш номер может быть 40 цифр?

Ответы на вопрос(5)

Решение Вопроса

simple побитовые операции принимают степень двойки по модулю (делителю) значения (дивиденд), используя AND с делителем-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). 

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

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

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

 17 окт. 2015 г., 20:37
У меня был похожий вопрос относительно того, почему только «(Степень 2) - 1» работает по модулю. Спасибо за объяснение!

как сумму степеней 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's place */ ) % 10
            = 28 % 10

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

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

 18 июн. 2012 г., 12:51
DAA - Decimal Adjust for Addition и другие. должно пригодиться
 18 июн. 2012 г., 20:39
Хм, 286 имеет22 cycle 16-битное деление. Это будет трудно победить таким образом, особенно без бочкообразного переключателя (!). Может быть, это все еще полезно, в зависимости от того, что OP означает «40 цифрами». Кроме того, не ясно, как 180 раз в секунду будет проблемой в первую очередь.

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

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

  out += tab[out]

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

 18 июн. 2012 г., 05:04
Вы хотите снова обдумать это.
 18 июн. 2012 г., 05:18
Вы можете разбить его на два байта, так как модуль является дистрибутивным по сложению. Им нужна таблица всего из 512 записей для 16-битного целого числа.
 PgrAm18 июн. 2012 г., 04:18
Я не забочусь о сложности или уродстве, только о скорости. Однако таблица будет тратить слишком много моей памяти, поскольку таблица должна иметь размер 40 ^ 10 элементов.
 18 июн. 2012 г., 08:00
Поскольку 10 делится на 2, вам нужно всего 128 записей для LSB. После этого все еще эффективно разбивать его на любое количество более мелких частей, но в какой-то момент вычисление будет больше, чем алгоритм деления-умножения-вычитания. Следует отметить, что он является дистрибутивным, но преобразование суммы обратно в модуль требует второй операции модуля, поэтому алгоритм становится рекурсивным.

для компиляторов, и фактически, 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, в основном два мулла (действительно, на x86 нам повезло, и мы можем использовать lea для одного) и некоторые сдвиги и добавления / переходы. Я знаю, что где-то уже объяснял теорию, лежащую в основе этой оптимизации, поэтому я посмотрю, смогу ли я найти этот пост, прежде чем объяснять его еще раз.

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

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

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

Ваш ответ на вопрос