Является ли операция MOD более интенсивной для ЦП, чем умножение?

Почему операция mod (%) дороже операции умножения (*) чуть более чем в множитель 2?

Уточните, пожалуйста, как ЦП выполняет операцию деления и возвращает результат для операции MOD.

В следующем примере каждый поток выполняется в течение секунды. Тест проводился на процессоре SPARC.

// multiplication
void someThread() {

    int a = 10234;
    while (true) {
        opers++;
        a = a * a;
        a++;
    }

    // opers ~ 26 * 10^6 in a sec.
}

// MOD
void someThread() {

    int a = 10234;
    while (true) {
        opers++;
        a = a % 10000007;
        a++;
    }

    // opers ~ 12 * 10^6 in a sec.
}

c++ multiplication division cpu-architecture
person Leonid    schedule 05.11.2010    source источник
comment
Оба примера кода одинаковы.   -  person Robert Harvey    schedule 05.11.2010
comment
Где версия с +? ^^   -  person    schedule 05.11.2010
comment
Сравните алгоритмы умножения (en.wikipedia.org/wiki/Binary_multiplier) с алгоритмами целочисленного деления (en.wikipedia.org/wiki/Division_(digital)). Я не знаю, что sparc реализует для деления. Может невосстанавливающий алгоритм.   -  person indiv    schedule 05.11.2010
comment
-1 балл за этот вопрос? Могут ли downvoters объяснить / прокомментировать?   -  person Rajan    schedule 04.08.2011
comment
Отвечает ли это на ваш вопрос? Почему деление дороже умножения?   -  person phuclv    schedule 08.04.2020
comment
хотя деление на константу, подобное этому случаю, может быть преобразовано в умножение, но оно все же намного сложнее, чем одна инструкция деления, поэтому гораздо медленнее   -  person phuclv    schedule 08.04.2020
comment
Этот код не использует результат a. При компиляции с оптимизацией ни один из циклов не работает. Если без оптимизации, то это не очень значимый бенчмарк.   -  person Peter Cordes    schedule 04.02.2021

Ответы (5)


arrow_upward
5
arrow_downward

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

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

person AProgrammer    schedule 05.11.2010

arrow_upward
11
arrow_downward

MOD — это операция деления, а не умножения. Деление дороже умножения.

Подробнее об операции MOD здесь: http://en.wikipedia.org/wiki/Modulo_operation

person Robert Harvey    schedule 05.11.2010
comment
Роберт: То же самое можно сказать и о делении, т.е. деление дороже, потому что это операция MOD, а MOD дороже умножения. Я хотел бы знать больше деталей на уровне процессора, почему деление/модификация дороже, чем умножение. Этот ответ повторяет мой вопрос. - person Leonid; 05.11.2010
comment
Это правильный ответ, очевидно, ОП не воспринял его достаточно серьезно, чтобы сравнить мод с div. Где-то в Интернете должен быть пыльный уголок, где рассказывается о внутренностях процессора sparc. - person Hans Passant; 06.11.2010
comment
Тогда вопрос должен быть плохим, если правильный ответ не говорит ничего, кроме очевидного. После этого я улучшил вопрос и попросил предоставить более подробную информацию об использовании ЦП. - person Leonid; 06.11.2010

arrow_upward
5
arrow_downward

Задержка инструкций и пропускная способность для процессоров AMD и Intel x86

Одна операция просто по своей природе медленнее на процессоре :)

person Community    schedule 05.11.2010

arrow_upward
1
arrow_downward

Да, мод дороже умножения, так как реализуется через деление. (ЦП обычно возвращают как частное, так и остаток от деления.) Но оба ваших потока используют умножение. ошибка копирования/вставки?

person zvrba    schedule 05.11.2010

arrow_upward
0
arrow_downward

mod — это, по сути, тот же процесс, что и деление (по этой причине некоторые системы предоставляют «divmod»).

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

Это означает, что вы можете легко переставить и распараллелить сложения в длинном умножении, но вы не можете сделать то же самое для длинного деления. Я написал более длинный ответ об этом на https://stackoverflow.com/a/53346554/5083516.

person plugwash    schedule 01.03.2019