Есть ли способ написать «mod 31» без операторов модуля/деления?

Question

Получение модуля числа можно легко выполнить без оператора или деления модуля, если ваш операнд имеет мощность 2. В этом случае выполняется следующая формула: x % y = (x & (y − 1)). Это часто бывает много во многих архитектурах. Можно ли сделать то же самое для mod 31?

int mod31(int a){ return a % 31; }; 

Answer 1

Вы можете использовать последовательное сложение/вычитание. Другого трюка нет, так как 31 - простое число, чтобы увидеть, что модуль числа N - это мода 31, вам придется разделить и найти остаток.

int mode(int number, int modulus) { 
    int result = number; 

    if (number >= 0) { 
     while(result > modulus) { result = result - modulus;} 
    } else { 
     while (result < 0) { result = result + modulus;) 
    } 
} 

Answer 2

int mod31(int a){ 
    while(a >= 31) { 
     a -= 31; 
    } 
    return a; 
}; 

Это работает, если a > 0, но я сомневаюсь, что это будет быстрее, чем % оператора.

Answer 3

Вот два способа подойти к этой проблеме. Первый, использующий общую технику бит-скручивания, и, если тщательно оптимизирован, может побить аппаратное разделение. Другой заменяет умножение для деления, аналогично оптимизации, выполняемой gcc, и является самым быстрым. Суть в том, что нет смысла пытаться избежать оператора , если второй аргумент постоянный, потому что gcc его покрыл. (И, вероятно, другие компиляторы тоже.)

Следующая функция основана на том, что x - это то же самое (mod 31) как сумма базовых 32 цифр x. Это верно, потому что 32 - 1 mod 31, и, следовательно, любая мощность 32 равна 1 mod 31. Таким образом, каждая позиция «цифры» в номере базы-32 вносит цифру * 1 в сумму мод 31. И легко получить представление base-32: мы просто берем биты по пять за раз.

(Как и все остальные функции этого ответа, он будет работать только для неотрицательных x).

unsigned mod31(unsigned x) { 
    unsigned tmp; 
    for (tmp = 0; x; x >>= 5) { 
    tmp += x & 31; 
    } 
    // Here we assume that there are at most 160 bits in x 
    tmp = (tmp >> 5) + (tmp & 31); 
    return tmp >= 31 ? tmp - 31 : tmp; 
} 

Для конкретного целочисленного размера вы можете развернуть цикл и, вполне возможно, разбить деление. (И см @chux's answer способ, чтобы преобразовать контур в O(log bits) операций вместо O(bits) Труднее бить gcc, что позволяет избежать деления, когда делимое постоянная известно во время компиляции.

В очень быстром тесте с использованием знака 32-битные целые числа, наивный развернутый цикл занял 19 секунд, а версия, основанная на ответе @ chux, заняла всего 13 секунд, но gcc x%31 заняла 9,7 секунды. Принуждение gcc к использованию аппаратного разрыва (путем создания деления непостоянно) заняло 23,4 секунды , а код, показанный выше, занял 25,6 секунды. Эти цифры должны быть взяты с несколькими зернами соли. Время для вычисления i%31 для всех возможных значений i на моем ноутбуке с использованием -O3 -march=native.

gcc избегает 32-разрядного деления на константу, заменив его тем, что по существу является 64-разрядным умножением на инверсию константы, за которой следует правый сдвиг. (Фактический алгоритм делает немного больше работы, чтобы избежать переполнения.) Эта процедура была реализована более 20 лет назад в gcc v2.6, а документ, описывающий алгоритм, доступен на gmp site. (GMP также использует этот трюк.)

Вот упрощенная версия: Скажем, мы хотим вычислить n // 31 для некоторого беззнаковое 32-битное целое число n (с использованием вещий // указать усеченный целочисленное деление). Мы используем «магическую константу» m = 232 // 31, которая составляет 138547332. Теперь стало ясно, что для любого n:

m * n <= 232 * n/31 < m * n + n ⇒ m * n // 232 <= n//31 <= (m * n + n) // 232

(Здесь мы используем тот факт, что если a < b затем floor(a) <= floor(b).)

Кроме того, поскольку n < 232, m * n // 232 и (m * n + n) // 232 либо одного целого или два последовательных целых числа. Следовательно, один (или оба) этих двух является фактическим значением n//31.

Теперь мы действительно хотим вычислить n%31. Поэтому нам нужно умножить (предполагаемое) значение на 31 и вычесть из n. Если мы будем использовать меньшее из двух возможных дробей, может оказаться, что вычисленное значение по модулю слишком велика, но она может быть слишком большой по 31.

Или, выражаясь в коде:

static unsigned long long magic = 138547332; 
unsigned mod31g(unsigned x) { 
    unsigned q = (x * magic) >> 32; 
    // To multiply by 31, we multiply by 32 and subtract 
    unsigned mod = x - ((q << 5) - q); 
    return mod < 31 ? mod : mod - 31; 
} 

Фактический алгоритм, используемый gcc, избегает теста в конце, используя несколько более точные вычисления, основанные на умножении на 237//31 + 1. Это всегда дает правильный коэффициент, но за счет некоторых дополнительных сдвигов и добавляет, чтобы избежать переполнения целых чисел. Как оказалось, версия выше немного быстрее - в том же тесте, что и выше, потребовалось всего 6,3 секунды.

---

Другие протестированные функции, для полноты:

Наивные развернутый петли

unsigned mod31b(unsigned x) { 
    unsigned tmp = x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; 

    tmp = (tmp >> 5) + (tmp & 31); 
    return tmp >= 31 ? tmp - 31 : tmp; 
} 

@ улучшение chux в, слегка Оптимизированные

static const unsigned mask1 = (31U << 0) | (31U << 10) | (31U << 20) | (31U << 30); 
static const unsigned mask2 = (31U << 5) | (31U << 15) | (31U << 25); 
unsigned mod31c(unsigned x) { 
    x = (x & mask1) + ((x & mask2) >> 5); 
    x += x >> 20; 
    x += x >> 10; 

    x = (x & 31) + ((x >> 5) & 31); 
    return x >= 31 ? x - 31: x; 
} 

Answer 4

Если вы хотите получить модуль деления на знаменатель d такой, что d = (1 << e) - 1, где e является некоторой степенью экспоненты, вы можете использовать тот факт, что двоичное расширение 1/d является повторяющейся долей с битами, установленными каждые e цифр. Например, для e = 5, d = 31 и 1/d = 0.0000100001....

rici’s answer Аналогично, этот алгоритм эффективно вычисляет сумму base- (1 << e) цифр a:

uint16_t mod31(uint16_t a) { 
    uint16_t b; 
    for (b = a; a > 31; a = b) 
     for (b = 0; a != 0; a >>= 5) 
      b += a & 31; 
    return b == 31 ? 0 : b; 
} 

Вы можете раскатать эту петлю, так как знаменатель и число битов в числителе являются постоянными , но, вероятно, лучше позволить компилятору это сделать. И, конечно, вы можете изменить 5 на входной параметр и 31 на переменную, вычисленную из этого.

Answer 5

[Edit2] ниже производительность отмечает

Попытка только с 1 if состояния.

Этот подход - O (log2 (sizeof без знака)). Время выполнения увеличилось бы на 1 набор и/смещений/добавлений, а не в два раза по времени с использованием подхода цикла, чтобы код использовал uint64_t.

unsigned mod31(uint32_t x) { 
    #define m31 (31lu) 
    #define m3131 ((m31 << 5) | m31) 
    #define m31313131 ((m3131 << 10) | m3131) 

    static const uint32_t mask1 = (m31 << 0) | (m31 << 10) | (m31 << 20) | (m31 << 30); 
    static const uint32_t mask2 = (m31 << 5) | (m31 << 15) | (m31 << 25); 
    uint32_t a = x & mask1; 
    uint32_t b = x & mask2; 
    x = a + (b >> 5); 
    // x = xx 0000x xxxxx 0000x xxxxx 0000x xxxxx 

    a = x & m31313131; 
    b = x & (m31313131 << 20); 
    x = a + (b >> 20); 
    // x = 00 00000 00000 000xx xxxxx 000xx xxxxx 

    a = x & m3131; 
    b = x & (m3131 << 10); 
    x = a + (b >> 10); 
    // x = 00 00000 00000 00000 00000 00xxx xxxxx 

    a = x & m31; 
    b = x & (m31 << 5); 
    x = a + (b >> 5); 
    // x = 00 00000 00000 00000 00000 0000x xxxxx 

    return x >= 31 ? x-31 : x; 
} 

[Редактировать]

Первый способ добавления суммирует индивидуальные 7 групп из пяти бит параллельно. Последующие добавления приносят 7 групп в 4, затем 2, затем 1. Эта окончательная 7-битная сумма затем добавляет свою верхнюю половину (2 бита) в ее нижнюю половину (5 бит). Затем код использует один тест для выполнения окончательного «мод».

Этот метод весит более широкий unsigned по меньшей мере uint165_t log2 (31 + 1) * (31 + 2). Передайте это, потребуется немного больше кода.

См. @rici для некоторых хороших оптимизаций. По-прежнему рекомендую использовать uint32_t против unsigned и 31UL сменами, такими как 31U << 15 как unsigned 31U может быть только 16 бит. (16 бит int популярный во встроенном мире в 2014 году).

---

[Edit2]

Кроме того, позволяя использовать компилятор оптимизатора, 2 дополнительные методы ускорило производительность. Это более незначительные трюки, которые принесли скромное улучшение. Имейте в виду YMMV, и это для 32-битного unsigned.

Использование таблицы для просмотра последних modulo улучшено 10-20%. Использование таблицы unsigned t, а не unsigned char t, тоже помогло. Оказалось, что длина таблицы, как и ожидалось, должна быть 2 * 31, нужна только 31 + 5.

Использование локальной переменной, а не всегда вызывающее функциональный параметр неожиданно помогло. Вероятно, это слабость в моем компиляторе gcc.

Найденные неразветвляющиеся решения, не показаны, для замены x >= 31 ? x-31 : x. но их сложность кодирования была больше, а производительность была медленнее.

Всеобъемлющее мероприятие.

unsigned mod31quik(unsigned xx) { 
    #define mask (31u | (31u << 10) | (31u << 20) | (31u << 30)) 
    unsigned x = (xx & mask) + ((xx >> 5) & mask); 
    x += x >> 20; 
    x += x >> 10; 
    x = (x & 31u) + ((x >> 5) & 31u); 

    static const unsigned char t[31 * 2 /* 36 */] = { 0, 1, 2, 3, 4, 5, 6, 
     7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
     25, 26, 27, 28, 29, 30, 0, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 
    return t[x]; 
}