Является ли режим MOD более интенсивным, чем умножение?

Почему операция MOD более дорогая, чем multiplication более чем на factor of 2? Пожалуйста, уточните, как CPU выполняет операцию деления и возвращает результат для работы 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.
}

Ответы

Ответ 1

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

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

Ответ 2

MOD - операция деления, а не операция умножения. Подразделение дороже, чем умножение.

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

Ответ 4

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