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

StackOverflow https://stackoverflow.com/questions/4109330

  •  29-09-2019
  •  | 
  •  

Вопрос

Почему MOD операция дороже, чем multiplication чуть больше, чем factor of 2? Пожалуйста, будьте более конкретны о том, как CPU выполняет операцию разделения и возвращает результат для работы мод.

В следующем примере потоки каждый запускается на секунду. Тест был выполнен на 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.
}
Это было полезно?

Решение

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

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

Другие советы

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

Дополнительная информация о операции мода здесь: http://en.wikipedia.org/wiki/modulo_operation

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top