Wie kann man sqrt am schnellsten berechnen?

khalderon

proggingmania schrieb:

float mysqrtopt(float r)
Das wird bei etwas grösseren Zahlen, hier ab ca. r > 3000 schnell wackelig nicht wahr.

Gucke mal dies:
#define MAGIC_SQRT_NUMBER 0x5f3759df
float magic_sqrt(float x)
{
	float h = x/2;
	int i = MAGIC_SQRT_NUMBER-(*(int*)&x>>1);
	x = *(float*)&i;
	return 1/(x=x*(1.5f-h*x*x));
}
Für x < 10⁴ ganz gut.
Für grössere x kannst du vor der Ausgabe durch Einfügen der Zeilen
x=x*(1.5f-h*x*x) die Genauigkeit steigern.

Für sehr grosse Zahlen kannst du gleich sqrt aus math.h nehmen, da gibts keinen Gewinn an Geschwindigkeit mehr.

Ich werde das benutzen. Vielen Dank!

Mr. N

float sqrtf(float);
double sqrt(double);

Die beiden Funktionen sollten verdammt schnell sein, zumindest schneller als irgendwelche Bithacks. (Wozu gibts die FPU?)

khalderon

Mr. N schrieb:

float sqrtf(float);
double sqrt(double);
Die beiden Funktionen sollten verdammt schnell sein, zumindest schneller als irgendwelche Bithacks. (Wozu gibts die FPU?)

Weißt du wie schnell die FPU von AT91 oder TI MSP ist?

Mr. N

Zdravko schrieb:

Mr. N schrieb:
float sqrtf(float);
double sqrt(double);
Die beiden Funktionen sollten verdammt schnell sein, zumindest schneller als irgendwelche Bithacks. (Wozu gibts die FPU?)
Weißt du wie schnell die FPU von AT91 oder TI MSP ist?

Nö. Woher soll ich das wissen? Haben die überhaupt eine? Wenn nicht, wird das Standard-sqrt ja wohl per Bibliothek sein, und vermutlich wird die Bibliothek sogar recht gut sein.

Aber du kannst ja Benchmarks machen und vergleichen.

pale dog

Mr. N schrieb:

Zdravko schrieb:
Mr. N schrieb:
float sqrtf(float);
double sqrt(double);
Die beiden Funktionen sollten verdammt schnell sein, zumindest schneller als irgendwelche Bithacks. (Wozu gibts die FPU?)
Weißt du wie schnell die FPU von AT91 oder TI MSP ist?
Nö. Woher soll ich das wissen? Haben die überhaupt eine?

haben sie nicht.
ich würde dem op ja zu festkommaarithmetik raten, mit floats tut er sich keinen gefallen.
bei AT91SAM7's isses noch machbar, die haben genug power (ARM7), aber 'nem MSP430 würde ich das nicht zumuten wollen. der ist selbst mit C++ überfordert. assembler oder C schmecken ihm am besten

Wenn die keine FPU haben, wie können die dann überhaupt Floatwerte verarbeiten ? Softwaregesteuert ?

rapso

am besten ist immer um die langsamen instructions drumrum zu kommen, sqrt kann man sehr oft umgehen. vielleicht sagst du uns ja den zusammenhang in dem du sqrt nutzt (code?) und vielleicht hat dann jemand nen tip wie du ohne sqrt auskommst.

pale dog

hardwarelooser schrieb:

Wenn die keine FPU haben, wie können die dann überhaupt Floatwerte verarbeiten ? Softwaregesteuert ?

ja, wird alles per software gemacht und ist natürlich dementsprechend langsam...

rapso schrieb:

am besten ist immer um die langsamen instructions drumrum zu kommen, sqrt kann man sehr oft umgehen. vielleicht sagst du uns ja den zusammenhang in dem du sqrt nutzt (code?) und vielleicht hat dann jemand nen tip wie du ohne sqrt auskommst.

Falls es dir entgangen ist, es sind schon 2 brauchbare Lösungen ohne sqrt vorgestellt worden.

pale dog schrieb:

ja, wird alles per software gemacht und ist natürlich dementsprechend langsam...

Die Berechnungen finden doch im Arbeitsspeicher statt, das ist doch sauschnell.

pale dog

hardwarelooser schrieb:

pale dog schrieb:

ja, wird alles per software gemacht und ist natürlich dementsprechend langsam...

Die Berechnungen finden doch im Arbeitsspeicher statt, das ist doch sauschnell.

im vergleich zu einer reinen hardwarelösung ist software saulangsam. jeder maschinenbefehl braucht zeit und das läppert sich zusammen. auf eine FPU muss man zwar auch etwas warten, aber nur sehr wenige taktzyklen, z.b. 4
--> http://www.ece.northwestern.edu/~ismail/courses/c92/fpu/index.html

pale dog schrieb:

--> http://www.ece.northwestern.edu/~ismail/courses/c92/fpu/index.html

Das ist doch eine Softwarelösung oder ?

pale dog

hardwarelooser schrieb:

pale dog schrieb:

--> http://www.ece.northwestern.edu/~ismail/courses/c92/fpu/index.html

Das ist doch eine Softwarelösung oder ?

jein
verilog ist eine hardware-beschreibungssprache. damit werden sogenannte fpga's konfiguriert.
--> http://de.wikipedia.org/wiki/FPGA
diese bestehen aus einem haufen von logikschaltkreisen, deren zusammenspiel mit z.b. verilog-code festgelegt wird. heraus kommt dabei ein hardware-baustein (in dem fall eine FPU).