Почему умножение дешевле, чем деление?

Question

Недавно я написал класс Vector 3 и отправил свою функцию normalize () для ознакомления другу. Он сказал, что это хорошо, но я должен умножать на взаимные, где это возможно, потому что «умножение дешевле, чем деление» во время процессора.

У меня просто вопрос: почему?

Answer 1

Думайте об этом с точки зрения элементарных операций, которые аппаратные средства могут легче реализовать - сложение, вычитание, сдвиг, сравнение. Умножение даже в тривиальной установке требует меньше таких элементарных шагов - плюс, это позволяет продвигать алгоритмы, которые еще быстрее - см., Например, здесь ... но аппаратное обеспечение обычно не использует их (кроме может быть, очень специализированное оборудование). Например, как говорится в URL-адресе википедии, «Toom – Cook может выполнять умножение в кубе размера N за цену пяти умножений размера N» - это довольно быстро для очень больших чисел (алгоритм Фюрера, довольно недавняя разработка, можно сделать Θ(n ln(n) 2Θ(ln*(n))) - снова, см. страницу википедии и ссылки оттуда).

Подразделение просто невероятно медленнее, как - снова - за wikipedia ; даже самые лучшие алгоритмы (некоторые из которых реализованы в HW, просто потому, что они нигде не так сложны и сложны, как самые лучшие алгоритмы умножения ;-) не могут удержать свечу перед умножением.

Просто для количественной оценки проблемы с не очень большими числами, вот некоторые результаты с gmpy , простой в использовании оболочкой Python для GMP , которая имеет тенденцию иметь довольно хорошие реализации арифметики, хотя не обязательно самые последние и хрипящие. На медленном (первом поколении ;-) Macbook Pro:

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib'
1000000 loops, best of 3: 0.186 usec per loop
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b'
1000000 loops, best of 3: 0.276 usec per loop

Как видите, даже при таком небольшом размере (число битов в числах) и с библиотеками, оптимизированными точно такими же одержимыми людьми, умножение на обратную величину может сэкономить 1/3 времени, которое занимает деление.

Это может быть только в редких случаях, когда эти несколько наносекунд являются вопросом жизни или смерти, но когда они равны , и, конечно, ЕСЛИ вы неоднократно делитесь на одно и то же значение (для амортизации откажитесь от операции 1.0/b!), тогда это знание поможет вам спасти жизнь.

(Многое в том же духе - x*x часто экономит время по сравнению с x**2 [в языках с оператором ** "повышение власти", таких как Python и Fortran] - и у Хорнера схема для полиномиальных вычислений ОЧЕНЬ предпочтительнее повторяющихся операций повышения мощности! -).

Answer 2

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

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

Answer 3

Операция ЦП для деления с плавающей запятой намного сложнее, чем умножение. Процессор должен делать больше. Я далеко не разбираюсь в оборудовании, но вы можете найти много информации о реализации общего деления (например, на основе алгоритмов newton-raphson ).

Я бы также старался всегда использовать умножение обратной величины вместо деления для увеличения производительности ЦП: они могут не давать одинаковых результатов. Это может иметь или не иметь значения в зависимости от вашего приложения.