math.h zu langsam
-
für y = -1 bekommst du was ganz lustiges. und warum ist pow bei dir so wichtig fürs Wurzelziehen?
-
ja das mit der 0 überprüfe ich schon im Programm aber ist sonst noch irgendwo ein Fehler?
Das mit dem Semikolon habe ich schon ausgebessert.
edit:
@und
Ich ziehe in etwa so die Wurzel:// ein= Zahl von der die Wurzel gezogen werden soll // root= 0 // w= welche Wurzel es ist while(pow(root, w)<ein) root+=0.00000001;
-
Du solltest e mit 1.0 initialisieren... dann verhält sich die Funktion auch bei y=0 richtig.
Bei e=x musst du die Schleife einmal weniger als jetzt durchlaufen lassen.
-
tuxer schrieb:
edit:
@und
Ich ziehe in etwa so die Wurzel:// ein= Zahl von der die Wurzel gezogen werden soll // root= 0 // w= welche Wurzel es ist while(pow(root, w)<ein) root+=0.00000001;Na, dann wundert es mich nicht, dass dir das Wurzelziehen zu lange dauert
Probier es doch so: root=pow(ein,1.0/w);
-
Nanyuki schrieb:
Probier es doch so: root=pow(ein,1.0/w);
dauert immer noch genauso lange
-
tuxer schrieb:
Nanyuki schrieb:
Probier es doch so: root=pow(ein,1.0/w);
dauert immer noch genauso lange
weil dein Programm zu ineffizient ist.
-
tuxer schrieb:
dauert immer noch genauso lange
Hast du die while-Schleife noch? Die Anweisung sollte alleine stehen.
-
-
Aha
Jetzt kappier ich die Formel erst
Danke
-
inline float FastWurzelExact(float r) { if(r == 0.0f) return 0.0f; if(r < 0.0f) r = -r; Value = r; halfValue = 0.5f*r; ptr = (unsigned long*)&r; *ptr=(0xbe6f0000-*ptr)>>1; temp1Wurzel = r; temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; return Value*temp1Wurzel; }
-
Dieser Code ist weder kompilierbar, noch liefert exakte Ergebnise (sondern Approximationen). Und funktioniert vorrangig, in dieser Form, für Quadratwurzeln.
-
Ausserdem gibts einige Unschönheiten:
Skym0sh0 schrieb:
inline float FastWurzelExact(float r) // inline ist sehrwahrscheinlich langsamer { if(r == 0.0f) // Wird selten der Fall sein, siehe Float-Vergleich return 0.0f; if(r < 0.0f) // Willst du bei Wurzeln aus negativen Zahlen r = -r; // wirklich ein Resultat ausgeben? ptr = (unsigned long*)&r; // C-Style-Cast }Aber was ist denn so schlecht an
sqrt()? Das ist wahrscheinlich auch schneller und genauer als deine eigene Funktion (die den Namen FastWurzelExact eigentlich nicht verdient hat ;))...
-
Die ist mit grosser Wahrscheinlichkeit langsamer..
Allerdings gab es diese Diskussion hier bereits einmal..
http://www.c-plusplus.net/forum/viewtopic-var-p-is-1487117.html
Hier gibt es noch einen interessanten Artikel über "Fast inverse square root".
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
-
naja das ist eine routine aus einem buch üebr 3d spiele programmierung
und so eine ähnliche wird in quake 3 verwendetok sie ist nicht so exakt, aber sie ist im gegensatz zu math::sqrt verdammt schnell
hab mal en test gemacht
1000000 wurzeln gezogen
math::sqrt hat 30 sek gebraucht
meine funktion hier hat nur 1 oder 2 gebraucht...ich denke das spricht für sich
ok ich muss dazu sagen wurzel 9 -> 2.99987324, aber es ging hierbei um eine möglichst schnelle und genau genügende funktion und man könnte noch ein oder 2 iterationen hinzufügen um genauer zu werden...
-
Skym0sh0 schrieb:
ich denke das spricht für sich
Vor allem spricht es dafür, dass keine Ahnung hast, was da eigentlich gemessen wurde.
-
achja komm schon
wir wissen doch alle wie ich das meine oder?
wenn du auf die cpu ticks abzielst weiss ich sehr wohl bescheid...
naja ich hab meinen beitrag zum thema wurzeln geliefert und gut ist
die funktion hat vor(ungenauigkeit) und nachteile (schnelligkeit) aber sowas hat jede funktion...
-
Skym0sh0 schrieb:
wir wissen doch alle wie ich das meine oder?
Ich weiß nicht, was du meinst. Wenn zutreffen sollte, dass du meinst, was ich glaube dass du meinst, dann wage ich es, diese Aussage anzuzweifeln; solange du uns nicht ein Programm zeigst, dass genau dieses Verhalten hat + die Aussage, auf welchem System dieses Ergebnis erzielt wurde. Und auch dann werde ich dir wahrscheinlich (99%) zeigen können, dass das, was gemessen wurde, gerade nicht (bzw. nur zu einem unwesentlichen Teil) etwas mit der "Geschwindigkeit" von sqrt der Standardbibliothek zu tun hat.
Jedenfalls ist dein Beitrag hier ohne eine gewisse Qualifikation fehlplatziert und schlicht unseriös. Schlimmer: Neulinge tendieren dazu, sich gerade solchen Unfug als erstes anzueignen.
-
Ein kleiner Test (schnell hingeschrieben, deshalb viel c&p) mit Visual C++ 2008 Express (/Ox /Ob2 /Oi /Ot /Oy /GT /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MT /GS-)
Die Tests auf <0 bzw. ==0 habe ich (zugunsten der Laufzeit der schnellen Wurzelfunktionen) weggelassen - ==0 ist nicht notwendig, <0 überflüssig im Hinblick auf die Emulation von sqrt.#include <iostream> #include <cmath> #include <ctime> #include <float.h> using namespace std; inline float FastWurzelExact1(float r) { float Value = r; float halfValue = 0.5f*r; unsigned long* ptr = (unsigned long*)&r; *ptr=(0xbe6f0000-*ptr)>>1; float temp1Wurzel = r; temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; return Value*temp1Wurzel; } inline float FastWurzelExact2(const float& r) { const float halfValue = 0.5f*r; float temp1Wurzel = reinterpret_cast<const float&>(static_cast<const unsigned&>((0xbe6f0000u-reinterpret_cast<const unsigned&>(r))>>1)); temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; temp1Wurzel *= 1.5f-temp1Wurzel*temp1Wurzel*halfValue; return r*temp1Wurzel; } typedef unsigned long long u64; u64 rdtsc() { __asm rdtsc; } void fast_state() { #if 0 _controlfp(_PC_24,_MCW_PC); #endif } void default_state() { #if 0 _controlfp(_PC_64,_MCW_PC); #endif } int main() { const int repeat = 100000; const int inner = 100; float f = 0; srand(time(0)); const int index[16] = { rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8,rand()%8 }; const float x[16] = { rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f,rand()/13.f }; fast_state(); u64 best_fast = ~0ull; for ( int i = repeat; i--; ) { u64 time = rdtsc(); for ( int j = inner; j--; ) { f += FastWurzelExact1( x[index[0]] ); f += FastWurzelExact1( x[index[1]] ); f += FastWurzelExact1( x[index[2]] ); f += FastWurzelExact1( x[index[3]] ); f += FastWurzelExact1( x[index[4]] ); f += FastWurzelExact1( x[index[5]] ); f += FastWurzelExact1( x[index[6]] ); f += FastWurzelExact1( x[index[7]] ); f += FastWurzelExact1( x[index[8]] ); f += FastWurzelExact1( x[index[9]] ); f += FastWurzelExact1( x[index[10]] ); f += FastWurzelExact1( x[index[11]] ); f += FastWurzelExact1( x[index[12]] ); f += FastWurzelExact1( x[index[13]] ); f += FastWurzelExact1( x[index[14]] ); f += FastWurzelExact1( x[index[15]] ); } time = rdtsc() - time; if ( time < best_fast ) { best_fast = time; i = repeat; f = 0; } } default_state(); cout << "Fast1:\t" << f << '\t' << FastWurzelExact1( x[index[0]] ) << '\t' <<double(best_fast)/inner/16 << endl; fast_state(); u64 best_fast2 = ~0ull; for ( int i = repeat; i--; ) { u64 time = rdtsc(); for ( int j = inner; j--; ) { f += FastWurzelExact2( x[index[0]] ); f += FastWurzelExact2( x[index[1]] ); f += FastWurzelExact2( x[index[2]] ); f += FastWurzelExact2( x[index[3]] ); f += FastWurzelExact2( x[index[4]] ); f += FastWurzelExact2( x[index[5]] ); f += FastWurzelExact2( x[index[6]] ); f += FastWurzelExact2( x[index[7]] ); f += FastWurzelExact2( x[index[8]] ); f += FastWurzelExact2( x[index[9]] ); f += FastWurzelExact2( x[index[10]] ); f += FastWurzelExact2( x[index[11]] ); f += FastWurzelExact2( x[index[12]] ); f += FastWurzelExact2( x[index[13]] ); f += FastWurzelExact2( x[index[14]] ); f += FastWurzelExact2( x[index[15]] ); } time = rdtsc() - time; if ( time < best_fast2 ) { best_fast2 = time; i = repeat; f = 0; } } default_state(); cout << "Fast2:\t" << f << '\t' << FastWurzelExact2( x[index[0]] ) << '\t' <<double(best_fast2)/inner/16 << endl; fast_state(); u64 best = ~0ull; f = 0; for ( int i = repeat; i--; ) { u64 time = rdtsc(); for ( int j = inner; j--; ) { f += sqrt( x[index[0]] ); f += sqrt( x[index[1]] ); f += sqrt( x[index[2]] ); f += sqrt( x[index[3]] ); f += sqrt( x[index[4]] ); f += sqrt( x[index[5]] ); f += sqrt( x[index[6]] ); f += sqrt( x[index[7]] ); f += sqrt( x[index[8]] ); f += sqrt( x[index[9]] ); f += sqrt( x[index[10]] ); f += sqrt( x[index[11]] ); f += sqrt( x[index[12]] ); f += sqrt( x[index[13]] ); f += sqrt( x[index[14]] ); f += sqrt( x[index[15]] ); } time = rdtsc() - time; if ( time < best ) { best = time; i = repeat; f = 0; } } default_state(); cout << "sqrt:\t" << f << '\t' << sqrt( x[index[0]] ) << '\t' << double(best)/inner/16 << endl; } #include <windows.h> struct Affinity { Affinity() { SetThreadAffinityMask(GetCurrentThread(),1); Sleep(1); } } affinity;zeigt mit verschiedenen von mir getesten Rechnern folgendes Verhalten:
Fast1 Fast2 sqrt Coppermine-P3 42,2 27,9 8,1 Northwood-P4 62,3 43,4 23,1 Merom-T7200 25,9 19,8 9,0 Palomino-Athlon XP 26,3 25,3 12,0 Winchester-Athlon 64 38,3 25,4 13,0Angaben jeweils in Taktzyklen pro Aufruf (die Modifikation des Steuerwortes führt nur zu minimalen Änderungen beim Ergebnis)
Daraus kann man nicht ableiten, dass dieses sog. schnelle Wurzelziehen irgendwie grundsätzlich schneller wäre. Bei mir ist es durchweg etwa halb so schnell (das Missverhältnis wird noch größer, wenn sse2-Instruktion verwendet werden auf Prozessoren, die das unterstützen). Es bedeutet aber auch nicht, dass sqrt per se schneller wäre - gerade bei einer inline-Funktion kann in einem bestimmten Programm durch den Scheduler oder ggf. den Prozessor (out of order execution) eine Menge Latenz verdeckt werden. Und schließlich kann das mit einem anderen Compiler oder auf einem anderen Rechner wieder ganz anders aussehen. Ohne ein paar Überlegungen in dieser Hinsicht lässt sich eben immer gerade das beweisen, was man glauben möchte, ganz unabhängig von einer möglicherweise existierenden objektiven Wahrheit. Womit dieses Thema hoffentlich erledigt ist.
-
Skym0sh0 schrieb:
naja das ist eine routine aus einem buch üebr 3d spiele programmierung
und wie alt ist das buch? 15+ jahre?
und so eine ähnliche wird in quake 3 verwendet
q3 ist 10 jahre alt, und der code basiert wiederum auf noch viel älterem code.
in der zwischenzeit hat sich viel getan bei den prozessoren.es gibt wirklich keinen vernünftigen grund, ohne not solche hacks zu verwenden.
-
pharmacy;