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

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

7 голосов
/ 30 июля 2011

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

 x /= y;

и 

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

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

Ответы [ 3 ]

9 голосов
/ 30 июля 2011

Ответ на ваш вопрос зависит от вашей целевой платформы.Предполагая, что вы используете наиболее распространенный процессор 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.

5 голосов
/ 30 июля 2011

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

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

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

2 голосов
/ 30 июля 2011

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

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

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

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

...