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

Question

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

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

Answer 1

Подумайте об этом с точки зрения элементарных операций, которые можно с легкостью реализовать в оборудовании - добавьте, вычтите, сдвиньте, сравните. Умножение даже в тривиальной настройке требует меньше таких элементарных шагов - плюс, это позволяет ускорить алгоритмы, которые еще быстрее - например, here ... но аппаратное обеспечение обычно не использует их (кроме, может быть, чрезвычайно специализированного оборудования). Например, как указывает 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] - и Хорнера scheme для полиномиального вычисления намного предпочтительнее к повторным действиям с повышением мощности! -).

Answer 2

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

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

Answer 3

Если вы вернетесь в классную школу, вы вспомните, что умножение было сложнее, чем сложение, и разделение было труднее, чем умножение. Для CPU все не так.

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