Почему подразделение плавающее является медленным?
Основываясь на ответе @ charles-burns, вот соответствующий исходный код для QImage:
QImageData *d = 0;
if (format == QImage::Format_Invalid)
return d;
const int depth = qt_depthForFormat(format);
const int calc_bytes_per_line = ((width * depth + 31)/32) * 4;
const int min_bytes_per_line = (width * depth + 7)/8;
if (bpl <= 0)
bpl = calc_bytes_per_line;
if (width <= 0 || height <= 0 || !data
|| INT_MAX/sizeof(uchar *) < uint(height)
|| INT_MAX/uint(depth) < uint(width)
|| bpl <= 0
|| height <= 0
|| bpl < min_bytes_per_line
|| INT_MAX/uint(bpl) < uint(height))
return d; // invalid parameter(s)
Итак, bpl - это количество байт на строку, что эффективно width * depth_in_bytes. Используя алгебру в этом последнем недействительном тесте:
-
INT_MAX/uint(bpl) < uint(height) -
INT_MAX < uint(height) * uint(bpl) -
INT_MAX < height * width * depth_in_bytes
Итак, ваш общий размер изображения должен быть меньше, чем 2147483647 (для 32-битных ints).
6 ответов
От аппаратных средств подразделение точки зрения является итеративным алгоритмом, и время этим, взятия пропорциональны числу битов. Самое быстрое подразделение, которое в настоящее время является вокруг использования radix4 алгоритмом, который генерирует 4 бита результата на повторение. Для деления на 32 бита Вам нужны 8 шагов, по крайней мере.
Умножение может быть сделано параллельно до известной степени. Не вдаваясь в подробности можно разбить большое умножение в несколько меньших, независимых. Это умножение может снова быть сломано, пока Вы не на разрядном уровне, или Вы останавливаетесь ранее и используете маленькую справочную таблицу в аппаратных средствах. Это делает аппаратные средства умножения тяжелыми с кремниевой точки зрения недвижимости, но очень быстро также. Это - классический компромисс размера/скорости.
Вам нужны шаги log2 для объединения, параллель вычислила результаты, таким образом, 32 бита умножают потребность 5 логических шагов (при снижении до минимума). К счастью, эти 5 шагов намного более просты, чем шаги подразделения (это - просто дополнения). Это означает, на практике умножается, еще быстрее.
Подразделение FPU часто в основном использует Ньютон-Raphson (или некоторый другой алгоритм) для получения обратной величины затем умножается той обратной величиной. Вот почему взаимная операция немного быстрее, чем общая операция деления.
Эта газета HP (который на самом деле более понятен, чем большинство бумаг, я сталкиваюсь с разговором о Ньютоне-Raphson) говорит следующее о делении с плавающей точкой:
Деление с плавающей точкой и квадратный корень берут значительно дольше для вычислений, чем дополнение и умножение. Последние два вычисляются непосредственно, в то время как первый обычно вычисляется с итеративным алгоритмом. Наиболее распространенный подход должен использовать повторение Ньютона-Raphson без подразделений, чтобы получить приближение к обратной величине знаменателя (подразделение) или взаимный квадратный корень, и затем умножиться числителем (подразделение) или входной параметр (квадратный корень).
Как описано в алгоритме Подразделения статьи Wikipedia , существует два основных подхода к подразделению в компьютерах:
Медленное Подразделение
Использование следующее повторение и находит одну цифру на повторение:
partialRemainder[j+1] = radix * partialRemainder[j] - quotientDigit[n-(j+1)]*denominator
Быстрое Подразделение
Запускается с оценки и сходится на частном. То, насколько точный Вы, зависит от количества повторений.
подразделение Ньютона-Raphson (очень кратко):
- Вычисляют оценку обратной величины.
- Вычисляют более точные оценки обратной величины.
- Вычисляют частное путем умножения дивиденда на обратную величину.
Вы не получите производительность путем выполнения
d = 1 / c
a = b * d
, Вы, вероятно, имеете в виду:
d = 1 / c
a1 = b1 * d
a2 = b2 * d
Этот путь подразделение сделано только однажды.
Подразделение по сути медленнее, чем умножение, однако, я не знаю детали. Основная причина состоит в том, что, подобный функциям, таким как грех или sqrt, это просто математически более сложно. IIRC, умножение берет приблизительно 10 циклов на среднем ЦП, в то время как подразделение берет приблизительно 50 или больше.
то, Как это на самом деле сделано, было приятно объяснено John Mulder.
Думайте об аппаратных средствах, включенных, и Вы поймете намного лучше, почему они берут настолько дольше для деления, чем умножаются. Обе операции недооценены на уровне Сопроцессора для операций с плавающей точкой (FPU), и даже в мире интегрального ALUs, схема подразделения является намного более оживленным местом, чем схема умножения. Я подозревал бы, что это только более болезненно в мире плавающей точки, поскольку теперь данные не просто наименьшее к старшей значащей заказанной цифре, но и вместо этого заказаны стандартом IEEE 754.
Что касается раунда прочь, это действительно о том, везде, где сигналы, перемещающиеся между логическими элементами, спаяны для основания; где это происходит, Вы теряете цифры. Не округляясь, так как усечение.
Или Вы спрашивали о моделировании арифметики с плавающей точкой, использующей просто целые числа?
Подразделение плавающее не намного медленнее, чем целочисленное деление, но компилятор может не мочь сделать ту же оптимизацию.
, Например, компилятор может заменить целочисленное деление между 3 с умножением и двоичным сдвигом. Также это может заменить подразделение плавающее между 2,0 с multipliation 0,5, но это не может заменить подразделение между 3,0 с умножением 1/3.0, поскольку 1/3.0 не может быть представлен точно с помощью двоичных чисел, поэтому погрешности округления могут изменить результат подразделения.
, Поскольку компилятор не знает, насколько чувствительный Ваше приложение к погрешностям округления (скажите, что Вы делали погодное моделирование, видите эффект Бабочки ), это не может сделать оптимизации.