Złożoność sqrt() z STL

Jaka jest złożoność operacji sqrt() z C++11?

long long int n;
cin >> n;
long long int p = sqrt(n);

To nie jest żaden STL.

Jaka złożoność? Standard nie definiuje żadnych wymagań czasowych ani pamięciowych dla std::sqrt.

W praktyce na x86 kompilator może wygenerować jedną instrukcję do obliczania pierwiastka (np. sqrtsd, te instrukcje to są dziesiątki cykli).

Jaka jest złożoność operacji sqrt() z C++11?
Złożoność jest zapewne O(1), czyli niezależna od wartości n.
Choć standard tego chyba nie zapewnia.

Azarien napisał(a):

Jaka jest złożoność operacji sqrt() z C++11?
Złożoność jest zapewne O(1), czyli niezależna od wartości n.
Choć standard tego chyba nie zapewnia.

Schodząc na najniższy poziom, czas wykonywania instrukcji liczącej pierwiastek na procesorze jest niekoniecznie stały, podobnie jak spora część instrukcji które wykonują się długo. Np patrząc na: http://agner.org/optimize/instruction_tables.pdf FSQRT na Intel Haswell dostajemy Latency 10 - 23 i Reciprocal throughput 8 - 17.

Złożoności mają sens głównie gdy mówimy o rozmiarach danych dążących do nieskończoności. Procesor natomiast operuje tylko i wyłącznie na małych porcjach. Żeby policzyć sobie pierwiastek z liczby N-bitowej (gdzie N to dowolna dodatnia liczba całkowita), trzeba sobie zrobić do tego algorytm i jemu będzie można policzyć złożoność.

Różnica między czasem optymistycznym a pesymistycznym jest pewną stałą, więc ogólnie można powiedzieć, że każda instrukcja ma złożoność O(1). Wydaje się to być trochę niedokładne, ale jeśli ktoś wie jak działają komputery to niedokładności widzi znacznie więcej. Nowoczesne procesory są superskalarne, czyli mogą wykonywać wiele instrukcji naraz (to jest ograniczone stałą zależną od projektu procesora), pod warunkiem, że są one niezależne. Czas dostępu do pamięci zależy od tego jak daleko znajduje się ona od rdzenia - najszybszy dostęp jest do pamięci podręcznej pierwszego poziomu, wolny dostęp jest do pamięci głównej, ale na upartego można i zmapować sobie zasób dyskowy (memory mapped files) lub sieciowy na przestrzeń adresową. Niuanse tego typu zmieniają się z architektury na architekturę i to także w obrębie jednego producenta. Przejmowanie się nimi spowodowałoby, że liczenie złożoności obliczeniowej urastałoby do rangi misji, dlatego nie uwzględnia się ich w złożoności. Duże składniki (typu 'n', 'sqrt(n)', itp) zwykle i tak dominują nad nawet dużymi różnicami w stałej złożoności. Dopiero gdy algorytmy różnią się małym składnikiem (typu 'log(n)') to można sprawdzać czy teoretycznie wolniejszy algorytm nie jest przypadkiem szybszy dzięki niższej stałej.

Np patrząc na: http://agner.org/optimize/instruction_tables.pdf FSQRT na Intel Haswell dostajemy Latency 10 - 23 i Reciprocal throughput 8 - 17.

Pod warunkiem że wiemy, że użyta będzie akurat instrukcja fsqrt. A to może zależeć od parametrów kompilacji, od wersji kompilatora...

Azarien napisał(a):

Np patrząc na: http://agner.org/optimize/instruction_tables.pdf FSQRT na Intel Haswell dostajemy Latency 10 - 23 i Reciprocal throughput 8 - 17.

Pod warunkiem że wiemy, że użyta będzie akurat instrukcja fsqrt. A to może zależeć od parametrów kompilacji, od wersji kompilatora...

a z tymi AVL co tam jest?
bo to też można użyć zamiast SSE2 w VS... od 2010 chyba.

a z tymi AVL co tam jest?

Chyba AVX?

Ale ten kod się u mnie wywala już na vmovsd z błędem “Illegal Instruction”. Co oczywiście zrozumiałe.