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

Question

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

Мой вопрос просто в том, почему это?

Answer 1

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

Дивизия просто существенно медленнее, как, опять же, согласно Википедия;даже самые лучшие алгоритмы (некоторые из которых реализованы в 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

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

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