Почему плавающее деление замедляется?

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

Почему результат медленнее, чем говорят, умножение?

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

Кроме того, почему мы получаем прибыль, если вместо

a = b / c

делаем

d = 1 / c
a = b * d

Изменить: В основном я спрашивал, потому что кто-то попросил меня распределить ценность среди соперников на основе назначения весов. Я сделал все это в целых числах и позже попросил конвертировать в float, что вызвало замедление производительности. Мне просто интересно узнать, как C или С++ выполняют эти операции, которые могут вызвать медленность.

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

Как описано в статье Wikipedia алгоритм разделения, есть два основных подхода к делению на компьютерах:

Медленное разделение

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

Fast Division

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

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

Ответ 4

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

d = 1 / c
a = b * d

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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