Операция MOD более интенсивна, чем умножение?

Question

Почему операция MOD стоит дороже, чем multiplication, чуть больше, чем factor of 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.
}

Answer 1

MOD - это операция деления, а не операция умножения.Деление обходится дороже, чем умножение.

Более подробную информацию об операции MOD можно получить здесь: http://en.wikipedia.org/wiki/Modulo_operation

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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