langsame funktionen in c++
-
sin cos und tan sind 0(1)
sqrt kann man vereinfacht reimplementieren, um die anzahl der iterationen zu verringern
wenn ich mich richtig erinnere gibts auf neueren cpu's sogar einen asm befehl der das ganze in O(1) erledigt
-
O(1) bedeutet nur, dass sie eine konstante Laufzeit haben, also nicht bei wachsender Problemgröße ansteigen, aber es sagt nicht über die Tatsächliche Laufzeit aus, Aber in der Funktion ist auch garkeine Problemgröße festgelegt, was dazu führ, dass es eine Konstante Laufzeit haben muss. Die Laufzeit kann 1000 mal häher sein, als der Zugriff auf ein Datenelement eines Arrays, und trotz dem ist die Laufzeit O(1).
-
vielleicht meint r0nny das es gleich schnell ist egal wieviele ziffern die zahl hat
-
sin cos und tan sind einfach multiplikationen
sqrt ist eine iteration/rekursion einer gewissen tiefe (meistens ist 20 - 40 mehr als ausreichend
einige cpu's können sqrt in hardware und ohne langwierige iteration -> nur ein paar takte anstatt ein paar hundert
-
Krux schrieb:
O(1) bedeutet nur, dass sie eine konstante Laufzeit haben, also nicht bei wachsender Problemgröße ansteigen, aber es sagt nicht über die Tatsächliche Laufzeit aus, Aber in der Funktion ist auch garkeine Problemgröße festgelegt, was dazu führ, dass es eine Konstante Laufzeit haben muss.
Ach, und Faktorisiere(int zahl) hat demnach auch konstante Laufzeit, weil ja keine Problemgröße spezifiziert ist? Zeig mal Deine Implementierung davon.
-
Folgender Code soll die Sinus-Funktion beschleunigen, ich hab allerdings nicht ausprobiert ob es wirklich was bringt:
#include <iostream> #include <cmath> #include <iomanip> namespace fast { const int arrsize = 1024; const double maxRadian = 2 * M_PI; double arr[arrsize]; void InitSin() { for (int i = 0; i < arrsize; ++i) { arr[i] = sin(maxRadian * i / arrsize); } } inline double sin(double r) { if(r < 0) { r = -r + maxRadian / 2; } while(r > maxRadian) { r -= maxRadian; } return arr[static_cast<size_t>(r * arrsize / maxRadian)]; } } int main() { fast::InitSin(); std::cout << std::setprecision(6) << std::fixed; for (double i = -1; i < 3; i += 0.4) { std::cout << fast::sin(i) << std::endl << sin(i) << std::endl << std::endl; } }mfg.
-
die "fast" ist saulahm für große werte
-
r0nny schrieb:
die "fast" ist saulahm für große werte
ja das stimmt. Mir ist nicht eingefallen wie man das sonst lösen sollte. Wie würde man dass denn machen?
mfg.
-
division mit anschliesender multiplikation des flieskommaanteils
-
Jo, durch 2 Pi, dann alles vor dem Komma weg, und mal Tabellengrösse (die idealerweise gleich ne 2er Potenz ist), dann ab nach Integer und als Index in die Tabelle verwenden.
Geht halt wirklich nur wenn man keine sehr gute Genauigkeit braucht.
-
r0nny schrieb:
sin cos und tan sind einfach multiplikationen
oh, auf die begründung dieser aussage bin ich mal echt gespannt.
-
r0nny schrieb:
sqrt ist eine iteration/rekursion einer gewissen tiefe (meistens ist 20 - 40 mehr als ausreichend
auf dem 64-er nahen wir 3 newton-iterationen, wenn ich mich recht erinnere. als startwert den float mit alter mantisse und halbem exponent.
-
sqrt kann man manchmal auch weglassen. Aus
if (x < sqrt(y))wird dann zB dies
if (x*x < y)Was logisch gleich ist, jedoch deutlich flotter berechnet werden kann.
-
Aißerdem braucht man (ich) fast immer nur float bei trigonometrischen Berechnunen, double dauert ja noch mal länger.
-
sqrt kann man manchmal auch weglassen. Aus
if (x < sqrt(y))wird dann zB dies
if (x*x < y)Was logisch gleich ist, jedoch deutlich flotter berechnet werden kann.
Und was machst du wenn x eine negative Zahl ist?
Das mit sin cos tan und der multiplikation würd mich auch mal interessieren.
-
Storm.Xapek.de schrieb:
Und was machst du wenn x eine negative Zahl ist?
Uninteressant, wenn es um Beträge geht (was bei sqrt meistens der Fall ist). Ich schrieb ja auch nicht, dass es immer möglich ist. Man muss halt von Fall zu Fall abwägen, ob die Vereinfachung sinnvoll ist.
