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

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

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

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

Ответы

Ответ 1

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

Алгоритмы разделения не могут быть распараллелены так же эффективно. Наиболее эффективные алгоритмы деления довольно сложны (Ошибка Pentium FDIV демонстрирует уровень сложности). Как правило, они требуют больше тактовых циклов на бит. Если вы после получения дополнительной технической информации, здесь, это хорошее объяснение от Intel. Intel фактически запатентовал свой алгоритм деления.