Насколько медленно (сколько циклов) вычисляется квадратный корень? - PullRequest
29 голосов
/ 11 октября 2011

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

Ответы [ 3 ]

22 голосов
/ 11 октября 2011

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

На 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 примерно такая же.

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

11 голосов
/ 11 октября 2011

Квадратный корень примерно в 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;
}
6 голосов
/ 19 марта 2014

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

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

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

...