Можно ли катиться значительно быстрее версию SQRT

Question

В приложении я профилирует, я обнаружил, что в некоторых сценариях эта функция может занять более 10% от общего времени выполнения.

Я видел обсуждение в течение многих лет более быстрых реализаций SQRT, используя Sloky Floating-Point Chickery, но я не знаю, если такие вещи устарели на современных процессорах.

Компилятор MSVC ++ 2008 используется для справки ... хотя бы я предположил, что SQRT не собирается добавлять много накладных расходов.

Смотрите также здесь для подобного обсуждения на модф функция.

Редактировать: для справки, это Это один широко используемый метод, но на самом деле это намного быстрее? Сколько циклов SQRT в любом случае в эти дни?

Answer 1

Да, можно даже без обмана:

1) жертва точностью для скорости: алгоритм SQRT является итеративным, повторно реализовать с меньшим количеством итераций.

2) Таблицы поиска: либо только для начальной точки итерации, либо в сочетании с интерполяцией, чтобы добраться до вас.

3) Кэширование: Вы всегда SQRTTE тот же ограниченный набор значений? Если это так, кэширование может работать хорошо. Я нашел это полезное в графических приложениях, где то же самое рассчитывается для многих форм того же размера, поэтому результаты могут быть использованы.

Answer 2

Здесь есть большой сравнительный стол:http://assemblyrequired.crashworks.org/timing-square-root/

Короче говоря, SSQRTS SSE2 SSE2 составляет около 2 раза быстрее, чем FPU FSQRT, а приближение + итерация составляет около 4 раза быстрее, чем это (8x в целом).

Кроме того, если вы пытаетесь взять одноточную SQRT, убедитесь, что это на самом деле то, что вы получаете. Я слышал, по крайней мере, один компилятор, который бы преобразул аргумент поплавка к двойному, позвоните в двойную точность SQRT, затем преобразуйте обратно в Float.

Answer 3

Вы очень, вероятно, получите больше улучшений скорости, изменив свой алгоритмы чем изменив их реализации: Попробуй позвонить sqrt() меньше вместо того, чтобы делать звонки быстрее. (И если вы думаете, что это невозможно - улучшения для sqrt() Вы упомянули только что: улучшения алгоритм используется для расчета квадратного корня.)

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

Обратите внимание, что, поскольку эта функция использует 10% времени вашего исполнения, даже если вам удается придумать реализацию, что требуется всего 75% времени std::sqrt(), это все еще принесет только время вашего исполнения 2,5%. Отказ Для большинства приложений пользователи даже не замечают это, за исключением случаев, если они используют часы для измерения.

Answer 4

Насколько точно вам нужно sqrt быть? Вы можете очень быстро получать разумные приближения: см. Отличное Quake3 обратный квадратный корень Функция для вдохновения (обратите внимание, что код GPL'ED, так что вы не захотите интегрировать его напрямую).

Answer 5

Не знаю, если вы исправили это, но я прочитал об этом раньше, и кажется, что самое быстрое сделать, это заменить sqrt функция с встроенной монтажной версией;

Вы можете увидеть описание нагрузки альтернатив здесь.

Лучший это фрагмент магии:

double inline __declspec (naked) __fastcall sqrt(double n)
{
    _asm fld qword ptr [esp+4]
    _asm fsqrt
    _asm ret 8
} 

Это около 4,7х быстрее, чем стандарт sqrt Позвоните с такой же точностью.

Answer 6

Вот быстрый способ с посмотрим столик только 8 КБ. Ошибка составляет ~ 0,5% от результата. Вы можете легко увеличить стол, тем самым уменьшая ошибку. Работает примерно в 5 раз быстрее, чем обычный SQRT ()

// LUT for fast sqrt of floats. Table will be consist of 2 parts, half for sqrt(X) and half for sqrt(2X).
const int nBitsForSQRTprecision = 11;                       // Use only 11 most sagnificant bits from the 23 of float. We can use 15 bits instead. It will produce less error but take more place in a memory. 
const int nUnusedBits   = 23 - nBitsForSQRTprecision;       // Amount of bits we will disregard
const int tableSize     = (1 << (nBitsForSQRTprecision+1)); // 2^nBits*2 because we have 2 halves of the table.
static short sqrtTab[tableSize]; 
static unsigned char is_sqrttab_initialized = FALSE;        // Once initialized will be true

// Table of precalculated sqrt() for future fast calculation. Approximates the exact with an error of about 0.5%
// Note: To access the bits of a float in C quickly we must misuse pointers.
// More info in: http://en.wikipedia.org/wiki/Single_precision
void build_fsqrt_table(void){
    unsigned short i;
    float f;
    UINT32 *fi = (UINT32*)&f;

    if (is_sqrttab_initialized)
        return;

    const int halfTableSize = (tableSize>>1);
    for (i=0; i < halfTableSize; i++){
         *fi = 0;
         *fi = (i << nUnusedBits) | (127 << 23); // Build a float with the bit pattern i as mantissa, and an exponent of 0, stored as 127

         // Take the square root then strip the first 'nBitsForSQRTprecision' bits of the mantissa into the table
         f = sqrtf(f);
         sqrtTab[i] = (short)((*fi & 0x7fffff) >> nUnusedBits);

         // Repeat the process, this time with an exponent of 1, stored as 128
         *fi = 0;
         *fi = (i << nUnusedBits) | (128 << 23);
         f = sqrtf(f);
         sqrtTab[i+halfTableSize] = (short)((*fi & 0x7fffff) >> nUnusedBits);
    }
    is_sqrttab_initialized = TRUE;
}

// Calculation of a square root. Divide the exponent of float by 2 and sqrt() its mantissa using the precalculated table.
float fast_float_sqrt(float n){
    if (n <= 0.f) 
        return 0.f;                           // On 0 or negative return 0.
    UINT32 *num = (UINT32*)&n;
    short e;                                  // Exponent
    e = (*num >> 23) - 127;                   // In 'float' the exponent is stored with 127 added.
    *num &= 0x7fffff;                         // leave only the mantissa 

    // If the exponent is odd so we have to look it up in the second half of the lookup table, so we set the high bit.
    const int halfTableSize = (tableSize>>1);
    const int secondHalphTableIdBit = halfTableSize << nUnusedBits;
    if (e & 0x01) 
        *num |= secondHalphTableIdBit;  
    e >>= 1;                                  // Divide the exponent by two (note that in C the shift operators are sign preserving for signed operands

    // Do the table lookup, based on the quaternary mantissa, then reconstruct the result back into a float
    *num = ((sqrtTab[*num >> nUnusedBits]) << nUnusedBits) | ((e + 127) << 23);
    return n;
}