Wie kann man sqrt am schnellsten berechnen?

pale dog schrieb:

float fake_sqrt (float f)
{
	int i = (((*(int*)&f & 0x7FFFFFFF) - 0x3f800000)>>1) + 0x3f800000;
	return *(float*)&i;
}

Nicht gerade genau.

@Zdravko:
Nimm doch sqrt aus math.h, das benutzt das Heronverfahren.

khalderon

Und endlich? Was soll ich benutzen? Jeder sagt etwas anderes.

proggingmania

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.

Daniel E.

Zdravko schrieb:

Und endlich? Was soll ich benutzen? Jeder sagt etwas anderes.

Welcome to the real world.

Hinsetzen, Genauigkeitsrahmen der einzelnen Lösungen prüfen, Laufzeiten nachrechnen, vergleichen, entscheiden. Viel Spaß.

Benutze dein Hirn!

proggingmania

Du könntest auch deine Version benutzen und ein bisschen verbessern, indem du deine Näherungsschritte in eine Schleife packst.
Die Schleife wird abgebrochen, wenn eine gewünschte Genauigkeit ( als PRECISION definiert ) erreicht ist.
Bei sehr grossen Zahlen und einem zu kleinen Precisionswert gibt es eine Endlosschleife.
1E-7 scheint mir ein guter Kompromiss zu sein.
Die Variable iteration_step_counter zählt die Schleifendurchläufe, die kannst du natürlich später rausschmeissen. ( falls du diese Version benutzen willst )
Bei FLT_MAX sind es bei mir 68 Durchläufe.
Je kleiner die Zahl umso weniger Durchläufe. ( Zahl=9 Durchläufe = 5 usw. )

Ob das schneller als die sqrt-Variante ist, keine Ahnung, das auszuprobieren überlasse ich dir.

#define PRECISION 1E-7
#define FLT_MAX         3.402823466e+38F   

int iteration_step_counter = 0;

float mysqrtopt_opt( float r )
{
	float x = r;
	do
	{
		x  = ( x + r / x ) / 2;
		iteration_step_counter++;

	}while( ( x*x / r ) > (1.0 + PRECISION) );

	return x;
}

int main()
{
	float z = FLT_MAX;
	float x = mysqrtopt_opt(z);
	printf("%G Anzahl der Schleifendurchlaeufe: %d\n", x, iteration_step_counter );
	return 0;
}

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).