Titlul: functia sqrt Scris de: CHERA Laurentiu din Noiembrie 18, 2010, 21:58:53 Salut! Ce algoritm foloseste c++ pentru extragerea radicalului (sqrt)? :D
Titlul: Răspuns: functia sqrt Scris de: Vlad Tarniceru din Decembrie 04, 2010, 19:17:25 scuze nu stiu ce algoritm foloseste. Eu fac radicalul cu cautare binara... nu stiu daca se poate mai rapid :)
Titlul: Răspuns: functia sqrt Scris de: Simoiu Robert din Decembrie 04, 2010, 19:19:17 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 .
Titlul: Răspuns: functia sqrt Scris de: nash mit din Decembrie 11, 2010, 10:47:53 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. Titlul: Răspuns: functia sqrt Scris de: CHERA Laurentiu din Decembrie 11, 2010, 15:02:45 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! Titlul: Răspuns: functia sqrt Scris de: nash mit din Decembrie 11, 2010, 21:17:07 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 |