Операция модов больше процессора интенсивного, чем умножение?
-
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.