Как медленно (сколько циклов) вычисляется квадратный корень?

Ответ 1

Из таблиц инструкций Agner Fog:

В Core2 65nm FSQRT занимает от 9 до 69 куб. см (с почти равной обратной пропускной способностью), в зависимости от битов значения и точности. Для сравнения, FDIV занимает от 9 до 38 куб. См (с почти равной обратной пропускной способностью), FMUL принимает 5 (recipthroughput = 2) и FADD занимает 3 (recipthroughput = 1). Производительность SSE примерно одинакова, но выглядит быстрее, потому что она не может делать 80-битную математику. SSE имеет супер быстрый приближенный взаимный и приблизительный взаимный sqrt, хотя.

На Core2 45nm, деление и квадратный корень стали быстрее; FSQRT занимает от 6 до 20 куб. См, FDIV занимает от 6 до 21 куб. См, FADD и FMUL не изменились. Еще раз производительность SSE примерно такая же.

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

Ответ 2

Квадратный корень примерно в 4 раза медленнее, чем добавление с использованием -O2, или примерно в 13 раз медленнее, не используя -O2. В другом месте в сети я нашел оценки 50-100 циклов, которые могут быть правдой, но это не относительный показатель стоимости, который очень полезен, поэтому я применил приведенный ниже код, чтобы сделать относительное измерение. Дайте мне знать, если вы видите какие-либо проблемы с тестовым кодом.

Код ниже был запущен на Intel Core i3 под управлением операционной системы Windows 7 и был скомпилирован в DevС++ (который использует GCC). Ваш пробег может отличаться.

#include <cstdlib>
#include <iostream>
#include <cmath>

/*
Output using -O2:

1 billion square roots running time: 14738ms

1 billion additions running time   : 3719ms

Press any key to continue . . .

Output without -O2:

10 million square roots running time: 870ms

10 million additions running time   : 66ms

Press any key to continue . . .

Results:

Square root is about 4 times slower than addition using -O2,
            or about 13 times slower without using -O2
*/

int main(int argc, char *argv[]) {

    const int cycles = 100000;
    const int subcycles = 10000;

    double squares[cycles];

    for ( int i = 0; i < cycles; ++i ) {
        squares[i] = rand();
    }

    std::clock_t start = std::clock();

    for ( int i = 0; i < cycles; ++i ) {
        for ( int j = 0; j < subcycles; ++j ) {
            squares[i] = sqrt(squares[i]);
        }
    }

    double time_ms = ( ( std::clock() - start ) / (double) CLOCKS_PER_SEC ) * 1000;

    std::cout << "1 billion square roots running time: " << time_ms << "ms" << std::endl;

    start = std::clock();

    for ( int i = 0; i < cycles; ++i ) {
        for ( int j = 0; j < subcycles; ++j ) {
            squares[i] = squares[i] + squares[i];
        }
    }

    time_ms = ( ( std::clock() - start ) / (double) CLOCKS_PER_SEC ) * 1000;

    std::cout << "1 billion additions running time   : " << time_ms << "ms" << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

Ответ 3

Квадратный корень занимает несколько циклов, но для получения доступа к памяти требуется больше порядков, если он не находится в кеше. Поэтому попытка избежать вычислений путем извлечения предварительно вычисленных результатов из памяти может нанести ущерб производительности.

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

Вот отличный разговор по этому поводу Эрика Браммера, разработчика компилятора на MSVC: http://channel9.msdn.com/Events/Build/2013/4-329