C++ практическая вычислительная сложность <cmath> SQRT()

Question

Какая разница в циклах ЦП (или, по сути, в "скорости") между

 x /= y;

а также

 #include <cmath>
 x = sqrt(y);

РЕДАКТИРОВАТЬ: я знаю, что операции не эквивалентны, я просто произвольно предлагаю x /= y в качестве ориентира для x = sqrt(y)

Answer 1

Ответ на ваш вопрос зависит от вашей целевой платформы. Предполагая, что вы используете наиболее распространенный процессор x86, я могу дать вам эту ссылку http://instlatx64.atw.hu/ Это набор измеренных задержек команд (сколько времени потребуется ЦП, чтобы получить результат после аргумента) и как они конвейерны для многих процессоров x86 и x86_64. Если ваша цель не x86, вы можете попытаться измерить стоимость самостоятельно или обратиться к документации вашего процессора.

Во-первых, вы должны получить дизассемблер ваших операций (от компилятора, например, gcc: gcc file.c -O3 -S -o file.asm или путем разборки скомпилированного двоичного файла, например, с помощью отладчика). Помните, что в вашей работе происходит загрузка и сохранение значения, которое необходимо учитывать дополнительно.

Вот два примера из friweb.hu:

Для Core 2 Duo E6700 с задержкой (L) SQRT (для версий x87, SSE и SSE2)

• 29 тиков для 32-битного поплавка; 58 тиков для 64-битного дубля; 69 тиков для 80-битного длинного дубля;

DIVIDE (чисел с плавающей запятой):

• 18 тиков для 32-битных; 32 галочки для 64-битных; 38 тиков за 80-бит

Для более новых процессоров стоимость меньше и почти одинакова для DIV и для SQRT, например, для процессора Intel Sandy Bridge:

SQRT с плавающей точкой

• 14 тиков для 32 бит; 21 тик для 64 бит; 24 тика за 80 бит

DIVIDE с плавающей точкой

• 14 тиков для 32 бит; 22 тика для 64 бит; 24 тика за 80 бит

SQRT даже на 32 бита быстрее.

Итак: для старых процессоров sqrt сам на 30-50 % медленнее, чем fdiv; Для нового процессора стоимость такая же. Для более новых процессоров стоимость обеих операций становится ниже, чем для более старых процессоров; Для более длинного плавающего формата вам нужно больше времени; например, для 64-битной вам нужно в 2 раза больше, чем для 32-битной; но 80-битный дешевый по сравнению с 64-битным.

Кроме того, в новых процессорах векторные операции (SSE, SSE2, AVX) имеют ту же скорость, что и скаляр (x87). Векторы имеют 2-4 однотипных данных. Если вы можете выровнять свой цикл для работы с несколькими значениями FP одной и той же операцией, вы получите большую производительность от CPU.

Answer 2

Если функция квадратного корня не реализована в специальном аппаратном или программном обеспечении, большинство библиотечных функций рассчитывают ее, используя метод Ньютона, который сходится квадратично.

Метод Ньютона - это итеративный метод: вы делаете начальное предположение, вычисляете результат испытания и используете его для следующего предположения. Вы повторяете, пока не решите, что у вас есть результат, который "достаточно близок". Так получилось, что вы можете доказать, сколько итераций вам нужно, с помощью квадратного корня. Каждый раз в течение цикла вы получаете еще две цифры точности, поэтому большинство реализаций будут сходиться к пределу точности двойных значений в 8-9 циклах.

Если вы внимательно прочитаете это, то увидите, что итерационный метод Ньютона выполняет два вычитания: одно умножение и одно деление на одну итерацию.

Answer 3

Общее практическое правило: и деление с плавающей точкой, и квадратный корень считаются медленной операцией (по сравнению с быстрыми, такими как сложение или умножение). Можно ожидать, что квадратный корень будет примерно такой же скорости или несколько медленнее (т.е. примерно в 1–2 раза ниже производительности) по сравнению с делением. Например, на Pentium Pro

Деление и квадратный корень имеют задержку от 18 до 36 и от 29 до 69 циклов соответственно

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

Примечание: многие современные платформы также предлагают обратный квадратный корень, который имеет скорость примерно такую ​​же, как sqrt, но часто более полезен (например, используя invsqrt, вы можете вычислять как sqrt, так и div с одним умножением для каждого).