Имеет ли смысл вычисление Sqrt (x) как x * InvSqrt (x) в BFG-коде Doom 3?
Я просмотрел недавно выпущенный Doom 3 BFG исходный код, когда я наткнулся на то, что, кажется, не имеет никакого смысла. Doom 3 оборачивает математические функции в idMath учебный класс. Некоторые из функций просто направлены на соответствующие функции из math.h, но некоторые являются повторными реализациями (например, idMath :: EXP16 ()) что я предполагаю, имеют более высокую производительность, чем их math.h аналоги (возможно за счет точности).
Однако меня смущает то, как они float idMath::Sqrt(float x) функция:
ID_INLINE float idMath::InvSqrt( float x ) {
return ( x > FLT_SMALLEST_NON_DENORMAL ) ? sqrtf( 1.0f / x ) : INFINITY;
}
ID_INLINE float idMath::Sqrt( float x ) {
return ( x >= 0.0f ) ? x * InvSqrt( x ) : 0.0f;
}
Похоже, что он выполняет две ненужные операции с плавающей запятой: сначала деление, а затем умножение.
Интересно отметить, что оригинальный исходный код Doom 3 также реализовал функцию квадратного корня таким образом, но обратный квадратный корень использует быстрый алгоритм обратного квадратного корня.
ID_INLINE float idMath::InvSqrt( float x ) {
dword a = ((union _flint*)(&x))->i;
union _flint seed;
assert( initialized );
double y = x * 0.5f;
seed.i = (( ( (3*EXP_BIAS-1) - ( (a >> EXP_POS) & 0xFF) ) >> 1)<<EXP_POS) | iSqrt[(a >> (EXP_POS-LOOKUP_BITS)) & LOOKUP_MASK];
double r = seed.f;
r = r * ( 1.5f - r * r * y );
r = r * ( 1.5f - r * r * y );
return (float) r;
}ID_INLINE float idMath::Sqrt( float x ) {
return x * InvSqrt( x );
}
Видите ли вы какие-либо преимущества в расчете Sqrt(x) как x * InvSqrt(x) если InvSqrt(x) внутренне просто звонки math.h«s fsqrt(1.f/x)? Может быть, я упускаю что-то важное о денормализованных числах с плавающей запятой здесь или это просто неряшливость со стороны программного обеспечения id?
Решение
Я вижу две причины сделать это таким образом: во-первых, метод «fast invSqrt» (на самом деле Newton Raphson) теперь является методом, используемым во многих аппаратных средствах, поэтому такой подход оставляет возможность использовать преимущества такого аппаратного обеспечения (и выполнение потенциально четырех или более таких операций одновременно). Эта статья обсуждает это немного:
Насколько медленно (сколько циклов) вычисляется квадратный корень?
Вторая причина для совместимости. Если вы измените путь к коду для вычисления квадратных корней, вы можете получить другие результаты (особенно для нулей, NaN и т. Д.) И потерять совместимость с кодом, который зависел от старой системы.
Другие решения
Насколько я знаю, InvSqrt используется для вычисления цветов в том смысле, что цвет зависит от угла, под которым свет отражается от поверхности, что дает вам некоторую функцию с использованием обратного корня квадратного.
В их случае им не нужна огромная точность при вычислении этих чисел, поэтому инженеры, работающие над кодом Doom 3 (первоначально из Quake III), придумали очень очень быстрый метод вычисления приближения для InvSqrt используя только несколько итераций Ньютона-Рафсона.
Вот почему они используют InvSqrt во всем их коде вместо использования встроенных (более медленных) функций. Я предполагаю использование x * InvSqrt(x) чтобы избежать умножения работы на два (имея два очень эффективные функции, один для InvSqrt и еще один для Sqrt).
Вы должны прочитать этот статья, может пролить свет на эту проблему.
Когда код был изменен несколькими людьми, становится трудно ответить на вопросы о том, почему он имеет свою текущую форму, особенно без истории изменений.
Однако, учитывая треть опыта в программировании, этот код соответствует шаблону, который упоминали другие: InvSqrt был быстрый, и имело смысл использовать его для вычисления квадратного корня. затем InvSqrt изменилось, и никто не обновлялся Sqrt,
Также возможно, что они натолкнулись на относительно наивную версию sqrtf который был заметно медленнее для больших чисел.