Почему деление более дорогое, чем умножение?

Question

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

Но мне интересно, почему деление фактически медленнее, чем умножение? Разве это не просто прославленное вычитание, а умножение - это прославленное дополнение? Поэтому математически я не понимаю, почему идти так или иначе имеет вычислительно разные затраты.

Может кто-нибудь может прояснить причину/причину этого, поэтому я знаю, вместо того, что я слышал от других программистов, о которых я спросил, перед которым: «потому что».

Answer 1

CPU ALU (Арифметико-логический блок) выполняет алгоритмы, хотя они реализованы в аппаратном обеспечении. Классические алгоритмы умножения включают Wallace tree и Dadda tree. Дополнительная информация доступна here. Более современные методы доступны в новых процессорах. Как правило, процессоры стремятся распараллелить операции бит-пар, чтобы минимизировать тактовые циклы. Алгоритмы умножения можно распараллелить достаточно эффективно (хотя требуется больше транзисторов).

Division algorithms не может быть распараллелен так эффективно. Наиболее эффективные алгоритмы деления довольно сложны (The Pentium FDIV bug демонстрирует уровень сложности). Как правило, они требуют больше тактовых циклов на бит. Если вам нужны дополнительные технические данные, here - это отличное объяснение от Intel. Intel фактически patented их алгоритм деления.