c++ практическа изчислителна сложност на ‹cmath› SQRT()

Отговорът на вашия въпрос зависи от вашата целева платформа. Ако приемем, че използвате най-често срещания 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-битов float; 58 отметки за 64-битов двойно; 69 отметки за 80-битово дълго двойно;

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

• 18 отметки за 32-битов; 32 отметки за 64-битов; 38 отметки за 80-битов

За по-новите процесори цената е по-малка и е почти еднаква за DIV и за SQRT, напр. за Sandy Bridge Intel CPU:

SQRT с плаваща запетая е

• 14 отметки за 32 бита; 21 отметки за 64 бита; 24 отметки за 80 бита

DIVIDE с плаваща запетая е

• 14 отметки за 32 бита; 22 отметки за 64 бита; 24 отметки за 80 бита

SQRT дори по-бързо за 32 бита.

Така че: За по-стари процесори sqrt сам по себе си е 30-50% по-бавен от fdiv; За по-нов процесор цената е същата. За по-новите процесори цената на двете операции става по-ниска, отколкото за по-старите процесори; За по-дълъг плаващ формат ви трябва повече време; напр. за 64-bit ви трябва 2 пъти повече време, отколкото за 32-bit; но 80-битовият е евтин в сравнение с 64-битовия.

Освен това по-новите процесори имат векторни операции (SSE, SSE2, AVX) със същата скорост като скаларната (x87). Векторите са от 2-4 еднотипни данни. Ако можете да подравните своя цикъл, за да работите върху няколко FP стойности с една и съща операция, ще получите повече производителност от процесора.

Ако функцията за квадратен корен не е реализирана в специален хардуер или софтуер, повечето библиотечни функции биха я изчислили, използвайки метода на Нютон, който се сближава квадратично.

Методът на Нютон е итеративен метод: правите първоначално предположение, изчислявате резултат от пробата и го използвате за следващото предположение. Повтаряте, докато смятате, че имате резултат, който е „достатъчно близък“. Случва се така, че можете да докажете колко итерации са ви необходими с квадратен корен. Всеки път през цикъла получавате още две цифри точност, така че повечето реализации ще се сближат до границата на прецизност от двойни за 8-9 цикъла.

Ако прочетете това внимателно, ще видите, че итеративният метод на Нютон прави две изваждания , едно умножение и едно деление на итерация.

Като общо правило: както делението с плаваща запетая, така и квадратният корен се считат за бавна операция (в сравнение с бързите като събиране или умножение). Може да се очаква квадратният корен да бъде приблизително същата скорост или малко по-бавен (т.е. приблизително 1x - 2x по-ниска производителност) в сравнение с деление. напр. на Pentium Pro

Делението и квадратният корен имат латентност съответно от 18 до 36 и 29 до 69 цикъла

За да получите по-точен отговор, трябва да се заровите в ръководството за архитектура за вашата платформа или да извършите бенчмарк.

Забележка: много съвременни платформи също предлагат обратен квадратен корен, който има скорост приблизително същата като sqrt, но често е по-полезен (напр. като имате invsqrt, можете да изчислите както sqrt, така и div с едно умножение за всяко).