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

Question

Насколько медленно (сколько циклов) вычисляется квадратный корень? Это возникло в курсе молекулярной динамики, где важна эффективность, а получение ненужных квадратных корней оказало заметное влияние на время работы алгоритмов.

Answer 1

Из таблиц инструкций Агнера Фога:

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

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

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

Answer 2

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

Приведенный ниже код был запущен на Intel Core i3 под операционной системой Windows 7 и скомпилирован в DevC++ (который использует 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;
}

Answer 3

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

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

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