functia sqrt

[•chera_lary]

Salut! Ce algoritm foloseste c++ pentru extragerea radicalului (sqrt)? 

[•vladtarniceru]

scuze nu stiu ce algoritm foloseste. Eu fac radicalul cu cautare binara... nu stiu daca se poate mai rapid

[•SpiderMan]

Spre exemplu, pentru numere mari, extragerea radicalului de mana e mult mai rapid ca si cel cu cautarea binara, acum nu stiu cum e la numere mai mici .

[•nash]

Modul de calcul este dupa o serie care converge catre rezultat... ( asa are implementat in spate limbajul )
Acelas lucru este si pentru functiile trigonometrice. Pentru anumite functii trigonometrice exista si niste aproximari linare ( tot serii ) pentru calcul mai rapid a valorii dar asta numai in vecinatatea unor puncte fixate.

[•chera_lary]

Da stiu... asta! Dezvoltarile in serie Taylor! Numai ca nu eram sigur daca se foloseste aceasta metoda! Voiam sa stiu daca are aceeasi complexitate cu operatiile de *, / si de asta intrebam! In cazul in care se dezvolta in serie complexitatea e mai mare!
Ms de raspunsuri!

[•nash]

Este normal sa nu aibe aceasi complexitate... cred ca se poate si demonstra asta...

Demonstratie :

sqrt(t) apartine R [ R = Q reunit cu R\Q ]
pentru Q -> exista un numar finit de pasi pentru a se ajunge la rezultat ( de ce ? ... consideram ca se face prin algoritmul cautarii binare atunci pentru orice numar finit "t" exista log(t) operatii care este finit  ).
pentru R\Q -> forma lui necesita adunarea unei infinitati de termeni intr-o serie ( daca te uiti cum este definita seria este ca o cautare binara , ma refer la Tyler , care converge la rezultat... ) ceea ce sigur nu se face pentru ca oricum avem o precizie clar definita a numerelor in virgula mobila dar din punct de vedere al complexitatii va fi tot timpul mai mare decat O(1) .

QED