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

Быстрые тесты на делимость (на 2,3,4,5,.., 16)?

Каковы самые быстрые тесты на делимость? Скажем, с учетом архитектуры little-endian и 32-разрядного целого числа со знаком: как рассчитать очень быстро, что число делится на 2,3,4,5,... до 16?

ПРЕДУПРЕЖДЕНИЕ: данный код является ПРИМЕРОМ. Каждая линия независима! Простое решение, использующее модульную работу, медленное на многих процессорах, у которых нет оборудования DIV (как и у многих ARM). Некоторые компиляторы также не могут делать такие оптимизации (например, если divisor является аргументом функции или что-то зависит от него).

Divisible_by_1 = do();
Divisible_by_2 = if (!(number & 1)) do();
Divisible_by_3 = ?
Divisible_by_4 = ?
Divisible_by_5 = ?
Divisible_by_6 = ?
Divisible_by_7 = ?
Divisible_by_8 = ?
Divisible_by_9 = ?
Divisible_by_10 = ?
Divisible_by_11 = ?
Divisible_by_12 = ?
Divisible_by_13 = ?
Divisible_by_14 = ?
Divisible_by_15 = ?
Divisible_by_16 = if(!number & 0x0000000F) do();

и специальные случаи:

Divisible_by_2k = if(number & (tk-1)) do();  //tk=2**k=(2*2*2*...) k times
4b9b3361

ОТВЕТЫ

Ответ 1

Неплохая идея AT ALL определить альтернативы инструкциям деления (которые включают по модулю на x86/x64), потому что они очень медленные. Медленнее (или даже намного медленнее), чем большинство людей понимают. Те, которые предлагают "% n", где n - переменная, дают глупый совет, потому что это неизбежно приведет к использованию инструкции деления. С другой стороны, "% c" (где c - константа) позволит компилятору определить лучший алгоритм, доступный в его репертуаре. Иногда это будет инструкция деления, но в большинстве случаев это не будет.

В этом документе Torbjörn Granlund показывает, что отношение тактовых циклов, необходимое для 32-битных мультисетей unsigned: divs составляет 4:26 (6.5x) на Sandybridge и 3: 45 (15x) на K10. для 64-бит соответствующие отношения составляют 4:92 (23x) и 5:77 (14.4x).

Столбцы "L" обозначают задержку. Столбцы "T" обозначают пропускную способность. Это связано с возможностью процессора обрабатывать несколько инструкций в параллельном режиме. Sandybridge может выпускать одно 32-битное умножение каждый другой цикл или один 64-бит каждого цикла. Для K10 соответствующая пропускная способность меняется на противоположную. Для делений K10 должен завершить всю последовательность, прежде чем она начнет другую. Я подозреваю, что это так же для Sandybridge.

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

Также интересно отметить, что divs стали менее эффективными с эволюцией от K8-K9 до K10: от 39 до 45 и от 71 до 77 тактов для 32- и 64-бит.

Granlund страница на gmplib.org и в Королевском технологическом институте в Стокгольме содержит больше положительных героев, некоторые из которых были включены в компилятор gcc.

Ответ 2

В каждом случае (включая делимый на 2):

if (number % n == 0) do();

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

Если вам нужно проверить все случаи, вы можете повысить производительность, поставив некоторые из случаев в if для другого: нет смысла тестировать делимость на 4, если делимость на 2 уже сработала, например.

Ответ 3

Как упоминалось @James, пусть компилятор упростит его для вас. Если n является константой, любой спуск-компилятор может распознать шаблон и изменить его на более эффективный эквивалент.

Например, код

#include <stdio.h>

int main() {
    size_t x;
    scanf("%u\n", &x);
    __asm__ volatile ("nop;nop;nop;nop;nop;");
    const char* volatile foo = (x%3 == 0) ? "yes" : "no";
    __asm__ volatile ("nop;nop;nop;nop;nop;");
    printf("%s\n", foo);
    return 0;
}

скомпилированный с g++ - 4.5 -O3, соответствующая часть x%3 == 0 станет

mov    rcx,QWORD PTR [rbp-0x8]   # rbp-0x8 = &x
mov    rdx,0xaaaaaaaaaaaaaaab
mov    rax,rcx
mul    rdx
lea    rax,"yes"
shr    rdx,1
lea    rdx,[rdx+rdx*2]
cmp    rcx,rdx
lea    rdx,"no"
cmovne rax,rdx
mov    QWORD PTR [rbp-0x10],rax

который, переведенный обратно на C-код, означает

(hi64bit(x * 0xaaaaaaaaaaaaaaab) / 2) * 3 == x ? "yes" : "no"
// equivalatent to:                 x % 3 == 0 ? "yes" : "no"

здесь нет подразделения. (Заметим, что 0xaaaaaaaaaaaaaaab == 0x20000000000000001L/3)

Edit:

Ответ 4

Немного языка в щеке, но при условии, что вы получите остальную часть ответов:

Divisible_by_6  = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;

Ответ 5

Предположим, что number unsigned (32 бита). Затем следующие очень быстрые способы вычисления делимости до 16. (Я не измерял, но код сборки указывает на это.)

bool divisible_by_2 = number % 2 == 0;
bool divisible_by_3 = number * 2863311531u <= 1431655765u;
bool divisible_by_4 = number % 4 == 0;
bool divisible_by_5 = number * 3435973837u <= 858993459u;
bool divisible_by_6 = divisible_by_2 && divisible_by_3;
bool divisible_by_7 = number * 3067833783u <= 613566756u;
bool divisible_by_8 = number % 8 == 0;
bool divisible_by_9 = number * 954437177u <= 477218588u;
bool divisible_by_10 = divisible_by_2 && divisible_by_5;
bool divisible_by_11 = number * 3123612579u <= 390451572u;
bool divisible_by_12 = divisible_by_3 && divisible_by_4;
bool divisible_by_13 = number * 3303820997u <= 330382099u;
bool divisible_by_14 = divisible_by_2 && divisible_by_7;
bool divisible_by_15 = number * 4008636143u <= 286331153u;
bool divisible_by_16 = number % 16 == 0;

Относительно делимости на d выполняются следующие правила:

  • Когда d является степенью 2:

    Как отметил Джеймс Канз, вы можете использовать is_divisible_by_d = (number % d == 0). Компиляторы достаточно умны, чтобы реализовать это как (number & (d - 1)) == 0 что очень эффективно, но запутано.

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

  • Когда d нечетно:

    Техника принимает форму is_divisible_by_d = number * a <= b где a и b - умно полученные константы. Обратите внимание, что все, что нам нужно, это 1 умножение и 1 сравнение:

  • Когда d четное, но не степень 2:

    Затем напишите d = p * q где p - степень 2, а q - нечетное число, и используйте "язык в щеке", предложенный unpythonic, то есть is_divisible_by_d = is_divisible_by_p && is_divisible_by_q. Опять же, только 1 умножение (в расчете is_divisible_by_q) выполняется.

Многие компиляторы (я тестировал clang 5.0.0, gcc 7.3, icc 18 и msvc 19 с использованием godbolt) заменяют number % d == 0 на (number/d) * d == number. Они используют умную технику (см. Ссылки в ответе Олофа Форшелла), чтобы заменить деление умножением и сдвигом битов. Они заканчивают тем, что делали 2 умножения. В отличие от вышеописанных методик выполняют только 1 умножение.

Обновление 01 октября 2018

Похоже, что приведенный выше алгоритм скоро поступит в GCC (уже в транке):

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853

Внедрение GCC кажется еще более эффективным. Действительно, реализация выше имеет три части: 1) делимость на четную часть делителя; 2) делимость на нечетную часть делителя; 3) && чтобы связать результаты двух предыдущих шагов. Используя инструкцию на ассемблере, которая не всегда доступна в стандарте C++ (ror), GCC объединяет три части в одну, что очень похоже на разделение на нечетную часть. Качественный товар! При наличии этой реализации лучше (как для ясности, так и для производительности) всегда возвращаться к %.

Ответ 6

LCM этих чисел кажется 720720. Его довольно мало, так что вы можете выполнить одну операцию модуля и использовать остаток в качестве индекса в предварительно вычисленном LUT.

Ответ 7

Прежде всего, напомню, что число в форме bn... b2b1b0 в двоичном выражении имеет значение:

number = bn*2^n+...+b2*4+b1*2+b0

Теперь, когда вы говорите номер% 3, у вас есть:

number%3 =3= bn*(2^n % 3)+...+b2*1+b1*2+b0

(я использовал = 3 = для обозначения конгруэнции по модулю 3). Заметим также, что b1*2 =3= -b1*1

Теперь я напишу все 16 делений, используя + и - и, возможно, умножение (обратите внимание, что умножение может быть записано как сдвиг или сумма того же значения, сдвинутого в разные местоположения. Например 5*x означает x+(x<<2), в котором вы вычисляете x только один раз)

Позвоните по номеру n и скажем Divisible_by_i - это булевское значение. В качестве промежуточного значения, представьте Congruence_by_i значение, сравнимое с n по модулю i.

Кроме того, скажем, n0 означает, что бит 0 n, n1 означает бит 1 и т.д., то есть

ni = (n >> i) & 1;

Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = n0-n1+n2-n3+n4-n5+n6-n7+n8-n9+n10-n11+n12-n13+n14-n15+n16-n17+n18-n19+n20-n21+n22-n23+n24-n25+n26-n27+n28-n29+n30-n31
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+2*n1-n2-2*n3+n4+2*n5-n6-2*n7+n8+2*n9-n10-2*n11+n12+2*n13-n14-2*n15+n16+2*n17-n18-2*n19+n20+2*n21-n22-2*n23+n24+2*n25-n26-2*n27+n28+2*n29-n30-2*n31
Congruence_by_7 = n0+2*n1+4*n2+n3+2*n4+4*n5+n6+2*n7+4*n8+n9+2*n10+4*n11+n12+2*n13+4*n14+n15+2*n16+4*n17+n18+2*n19+4*n20+n21+2*n22+4*n23+n24+2*n25+4*n26+n27+2*n28+4*n29+n30+2*n31
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+2*n1+4*n2-n3-2*n4-4*n5+n6+2*n7+4*n8-n9-2*n10-4*n11+n12+2*n13+4*n14-n15-2*n16-4*n17+n18+2*n19+4*n20-n21-2*n22-4*n23+n24+2*n25+4*n26-n27-2*n28-4*n29+n30+2*n31
Congruence_by_11 = n0+2*n1+4*n2+8*n3+5*n4-n5-2*n6-4*n7-8*n8-5*n9+n10+2*n11+4*n12+8*n13+5*n14-n15-2*n16-4*n17-8*n18-5*n19+n20+2*n21+4*n22+8*n23+5*n24-n25-2*n26-4*n27-8*n28-5*n29+n30+2*n31
Congruence_by_13 = n0+2*n1+4*n2+8*n3+3*n4+6*n5-n6-2*n7-4*n8-8*n9-3*n10-6*n11+n12+2*n13+4*n14+8*n15+3*n16+6*n17-n18-2*n19-4*n20-8*n21-3*n22-6*n3+n24+2*n25+4*n26+8*n27+3*n28+6*n29-n30-2*n31
Congruence_by_16 = n&0xF

Или при факторизации:

Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = (n0+n2+n4+n6+n8+n10+n12+n14+n16+n18+n20+n22+n24+n26+n28+n30)-(n1+n3+n5+n7+n9+n11+n13+n15+n17+n19+n21+n23+n25+n27+n29+n31)
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+n4+n8+n12+n16+n20+n24+n28-(n2+n6+n10+n14+n18+n22+n26+n30)+2*(n1+n5+n9+n13+n17+n21+n25+n29-(n3+n7+n11+n15+n19+n23+n27+n31))
Congruence_by_7 = n0+n3+n6+n9+n12+n15+n18+n21+n24+n27+n30+2*(n1+n4+n7+n10+n13+n16+n19+n22+n25+n28+n31)+4*(n2+n5+n8+n11+n14+n17+n20+n23+n26+n29)
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+n6+n12+n18+n24+n30-(n3+n9+n15+n21+n27)+2*(n1+n7+n13+n19+n25+n31-(n4+n10+n16+n22+n28))+4*(n2+n8+n14+n20+n26-(n5+n11+n17+n23+n29))
// and so on

Если эти значения оказываются отрицательными, добавьте их с помощью i, пока они не станут положительными.

Теперь вам нужно рекурсивно передать эти значения в том же процессе, который мы только что сделали, пока Congruence_by_i не станет меньше i (и, очевидно, >= 0). Это похоже на то, что мы делаем, когда хотим найти остаток от числа на 3 или 9, помните? Суммируйте цифры, если они имеют более одной цифры, некоторые цифры снова будут отображаться до тех пор, пока вы не получите только одну цифру.

Теперь для i = 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16:

Divisible_by_i = (Congruence_by_i == 0);

А для остальных:

Divisible_by_6 = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;

Изменить: обратите внимание, что некоторые дополнения можно было бы избежать с самого начала. Например, n0+2*n1+4*n2 совпадает с n&0x7, аналогично n3+2*n4+4*n5 является (n>>3)&0x7 и, следовательно, с каждой формулой вам не нужно получать каждый бит в отдельности, я написал его так, чтобы это было сделано для ясности и подобия в операции. Чтобы оптимизировать каждую формулу, вы должны работать над ней самостоятельно; групповые операнды и операции факторизации.

Ответ 8

Вы должны просто использовать (i% N) == 0 в качестве теста.

Мой компилятор (довольно старая версия gcc) создал хороший код для всех случаев, которые я пробовал. Когда тесты бит были подходящими, он это сделал. Где N была константой, она не создавала очевидного "разрыва" для любого случая, она всегда использовала "трюк".

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

Это интересный вопрос. Я не могу перечислить трюки, используемые компилятором для каждой константы, как я должен компилировать на другом компьютере. Но я позже обновлю этот ответ, если меня никто не будет бить:)

Ответ 9

Это, вероятно, не поможет вам в коде, но есть опрятный трюк, который может помочь сделать это в вашей голове в некоторых случаях:

Для деления на 3: для числа, представленного в десятичной форме, вы можете суммировать все цифры и проверить, делится ли сумма на 3.

Пример: 12345 => 1+2+3+4+5 = 15 => 1+5 = 6, который делится на 3 (3 x 4115 = 12345).

Более интересно тот же метод работает для всех факторов X-1, где X - база, в которой представлено число. Таким образом, для десятичного числа вы можете проверить деление на 3 или 9. Для hex вы можете проверить деление на 3,5 или 15. И для восьмеричных чисел вы можете проверить деление на 7.

Ответ 10

В предыдущем вопросе я показал быстрый алгоритм проверки базы N для делителей, которые являются факторами N-1. Базовые преобразования между разными степенями 2 тривиальны; это просто группировка бит.

Следовательно, проверка на 3 легко в базе 4; проверка на 5 легко в основании 16, и проверка на 7 (и 9) легко в базе 64.

Непрерывные делители тривиальны, поэтому только 11 и 13 являются трудными случаями. Для 11 вы можете использовать базу 1024, но в этот момент она не очень эффективна для небольших целых чисел.

Ответ 11

Вы можете заменить деление на константу non-power-of-a путем умножения, по существу, умножая на обратный ваш делитель. Детали для получения точного результата этим методом сложны.

Hacker Delight подробно обсуждает это в главе 10 (к сожалению, недоступно в Интернете).

Из частного можно получить модуль с помощью другого умножения и вычитания.

Ответ 12

Одна вещь, которую следует учитывать: поскольку вы только заботитесь о делимости до 16, вам действительно нужно только проверить делимость на простые числа до 16. Это 2, 3, 5, 7, 11 и 13.

Разделите свой номер на каждый из простых чисел, отслеживая логическое значение (например, div2 = true). Цифры два и три являются частными случаями. Если div3 истинно, попробуйте снова делить на 3, установив div9. Два и его полномочия очень просты (примечание: "&" - одна из самых быстрых вещей, которую может сделать процессор):

if n & 1 == 0:
    div2 = true
    if n & 3 == 0: 
        div4 = true
        if n & 7 == 0: 
            div8 = true
            if n & 15 == 0:
                div16 = true

Теперь у вас есть booleans div2, div3, div4, div5, div7, div8, div9, div11, div13 и div16. Все другие числа - это комбинации; например div6 совпадает с (div2 & div3)

Итак, вам нужно всего лишь 5 или 6 фактических делений (6, только если ваш номер делится на 3).

Для себя я, вероятно, использовал бы биты в одном регистре для своих логических операций; например бит_0 означает div2. Затем я могу использовать маски:

if (flags & (div2+div3)) == (div2 + div3): do_6()

Обратите внимание, что div2 + div3 может быть предварительно вычисленной константой. Если div2 - бит0, а div3 - бит1, то div2 + div3 == 3. Это делает выше, если "оптимизировать":

if (flags & 3) == 3: do_6()

Итак, теперь... mod без разрыва:

def mod(n,m):
    i = 0
        while m < n:
            m <<= 1
            i += 1
        while i > 0:
            m >>= 1
            if m <= n: n -= m
            i -= 1
     return n

div3 = mod(n,3) == 0
...

btw: наихудший случай для вышеуказанного кода 31 раз через любой цикл для 32-разрядного номера

FYI: Просто посмотрел на пост Мсальтера, выше. Его метод можно использовать вместо mod (...) для некоторых простых чисел.

Ответ 13

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

mod3 = pop(x & 0x55555555) + pop(x & 0xaaaaaaaa) << 1;  // <- one term is shared!
mod5 = pop(x & 0x99999999) + pop(x & 0xaaaaaaaa) << 1 + pop(x & 0x44444444) << 2;
mod7 = pop(x & 0x49249249) + pop(x & 0x92492492) << 1 + pop(x & 0x24924924) << 2;
modB = pop(x & 0x5d1745d1) + pop(x & 0xba2e8ba2) << 1 + 
       pop(x & 0x294a5294) << 2 + pop(x & 0x0681a068) << 3;
modD = pop(x & 0x91b91b91) + pop(x & 0xb2cb2cb2) << 1 +
       pop(x & 0x64a64a64) << 2 + pop(x & 0xc85c85c8) << 3;

Максимальные значения для этих переменных: 48, 80, 73, 168 и 203, которые все вписываются в 8-битные переменные. Второй раунд можно проводить параллельно (или может применяться какой-либо метод LUT)

      mod3 mod3 mod5 mod5 mod5 mod7 mod7 mod7 modB modB modB modB modD modD modD modD
mask  0x55 0xaa 0x99 0xaa 0x44 0x49 0x92 0x24 0xd1 0xa2 0x94 0x68 0x91 0xb2 0x64 0xc8
shift  *1   *2   *1   *2   *4   *1   *2   *4   *1   *2   *4   *8   *1   *2   *4   *8
sum   <-------> <------------> <----------->  <-----------------> <----------------->

Ответ 14

Быстрые тесты для делимости сильно зависят от базы, в которой представлено число. Если база равна 2, я думаю, что вы можете делать только "быстрые тесты" для делимости по степеням 2. Двоичное число делится на 2 n если последние n двоичных цифр этого числа равны 0. Для других тестов я не думаю, что вы можете найти что-нибудь быстрее, чем %.

Ответ 15

Немного зла, обфускации бит-twiddling может получить вас divisbility на 15.

Для 32-разрядного беззнакового числа:

def mod_15ish(unsigned int x) {
  // returns a number between 0 and 21 that is either x % 15
  // or 15 + (x % 15), and returns 0 only for x == 0
  x = (x & 0xF0F0F0F) + ((x >> 4) & 0xF0F0F0F);
  x = (x & 0xFF00FF) + ((x >> 8) & 0xFF00FF);  
  x = (x & 0xFFFF) + ((x >> 16) & 0xFFFF);
  // *1
  x = (x & 0xF) + ((x >> 4) & 0xF);
  return x;
}

def Divisible_by_15(unsigned int x) {
  return ((x == 0) || (mod_15ish(x) == 15));
}

Вы можете создавать похожие подпрограммы для 3 и 5 на основе mod_15ish.

Если у вас есть 64-разрядные беззнаковые ints для обработки, расширьте каждую константу выше строки *1 очевидным образом и добавьте строку над строкой *1, чтобы сделать правый сдвиг на 32 бита с помощью маски of 0xFFFFFFFF. (Последние две строки могут оставаться неизменными) mod_15ish затем подчиняется одному и тому же основному контракту, но возвращаемое значение теперь находится между 0 и 31. (так что поддерживается x % 15 == mod_15ish(x) % 15)

Ответ 16

Вот несколько советов, которые я еще не вижу:

Одна идея состоит в том, чтобы использовать оператор switch или прекомпретировать некоторый массив. Затем любой достойный оптимизатор может просто индексировать каждый случай напрямую. Например:

// tests for (2,3,4,5,6,7)
switch (n % 8)
{
case 0: break;
case 1: break;
case 2: do(2); break;
case 3: do(3); break;
case 4: do(2); do(4) break;
case 5: do(5); break;
case 6: do(2); do(3); do(4); break;
case 7: do(7); break;
}

Ваше приложение немного неоднозначно, но вам может потребоваться только проверить простые числа меньше n = 16. Это связано с тем, что все числа являются факторами текущего или предыдущего простых чисел. Итак, для n = 16 вы можете уйти, только проверив 2, 3, 5, 7, 11, 13 как-то. Просто мысль.