Почему деление поплавка медленное?

Question

Какие шаги в алгоритме для деления с плавающей запятой?

Почему результат медленнее, чем, скажем, умножение?

Это делается так же, как мы делим вручную? Путем многократного деления на делитель, вычитания результата для получения остатка, повторного выравнивания числа и продолжения до тех пор, пока остаток не станет меньше определенного значения?

Кроме того, почему мы выигрываем в производительности, если вместо этого делаем

a = b / c 

мы делаем

d = 1 / c
a = b * d

Edit: По сути, я спрашивал, потому что кто-то просил меня распределить ценность среди претендентов на основе присвоения весов. Я сделал все это в целых числах, и позже меня попросили преобразовать в число с плавающей точкой, что привело к снижению производительности. Мне просто было интересно узнать, как С или С ++ будут выполнять эти операции, которые вызовут медлительность.

Answer 1

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

Эта статья HP (которая на самом деле более понятна, чем большинство работ, с которыми я сталкиваюсь, говоря о Ньютоне-Рафсоне), говорит о разделении с плавающей запятой:

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

Answer 2

С аппаратной точки зрения разделение является итеративным алгоритмом, и время, которое оно занимает, пропорционально количеству битов. Самое быстрое деление, которое в настоящее время существует, использует алгоритм radix4, который генерирует 4-битный результат за итерацию. Для 32-битного деления вам нужно минимум 8 шагов.

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

Вам нужны шаги log2 для объединения результатов параллельного вычисления, поэтому для 32-битного умножения нужно 5 логических шагов (если вы опуститесь до минимума). К счастью, эти 5 шагов намного проще, чем этапы деления (это просто дополнения). Это означает, что на практике умножение еще быстрее.

Answer 3

Как описано в статье Википедии Алгоритм деления , существует два основных подхода к делению в компьютерах:

Медленное деление

Использует следующее повторение и находит одну цифру за итерацию: partialRemainder[j+1] = radix * partialRemainder[j] - quotientDigit[n-(j+1)]*denominator

Быстрое деление

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

деление Ньютона-Рафсона (очень кратко):

1. Рассчитать оценку обратной.
2. Вычислите более точные оценки обратной величины.
3. Вычислить частное, умножив дивиденд на обратную величину.

Answer 4

Вы не достигнете производительности, выполнив

d = 1 / c
a = b * d

Вы, вероятно, имеете в виду:

d = 1 / c
a1 = b1 * d
a2 = b2 * d

Таким образом, деление выполняется только один раз.

Деление само по себе медленнее, чем умножение, однако я не знаю деталей. Основная причина в том, что, подобно функциям типа sin или sqrt, это просто математически сложнее. IIRC, умножение занимает около 10 циклов на среднем процессоре, а деление - около 50 и более.

Как это на самом деле было хорошо объяснено Джоном Малдером.

Answer 5

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

Например, компилятор может заменить целочисленное деление между 3 умножением и двоичным сдвигом. Также он может заменить деление числа с плавающей запятой на 2,0 с умножением на 0,5, но не может заменить деление на 3,0 умножением на 1 / 3,0, поскольку 1 / 3.0 не может быть точно представлено с помощью двоичных чисел, поэтому ошибки округления могут изменить результат деления.
Поскольку компилятор не знает, насколько чувствительно ваше приложение к ошибкам округления (например, вы выполняли имитацию погоды, см. Эффект бабочки ), он не может выполнить оптимизацию.

Answer 6

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

Что касается закругления, то это действительно о том, где сигналы, проходящие между воротами, спаяны с землей; где это происходит, вы теряете цифры. Не округление, а усечение.

Или вы спрашивали об имитации арифметики с плавающей запятой, используя только целые числа?