Angst vorm Wurzelziehen

Hoi,
ich hab Angst vorm Wurzelziehen. Genauer gesagt, ich brauche die Wurzel aus einem int64.
Ob das Ergebnis danach auf- oder abgerundet wird, ist mir absolut egal, aber was echt wichtig ist, dass auf jedem Computer das selbe Ergebnis rauskommt!

Wenn jetzt die Funktion z.B. abrundet darf nicht auf einem Computer rauskommen
sqrt(6084) = 78.0 -> 78
und auf dem anderen
sqrt(6084) = 77.99999999.. -> 77

Ich habe vor einiger Zeit im Matheforum meine eigene Wurzelfunktion vorgestellt, welche mit dem Newton'schen Näherungsverfahren arbeitet, diese ist jedoch etwa um den Faktor 90 langsamer als (double)sqrt(double). Deshalb habe ich meine Wurzelfunktion jetzt vorläufig so implementiert:

/* Liefert die auf die nächste Ganzzahl
 * aufgerundete Wurzel einer Zahl zurück.
 */
inline __int64 sqrt(__int64 x)
{
	__int64 result = (__int64)sqrt((double)x)  -  1i64;

	while(result * result  <  x)
		++result;

	return result;
}

Gibt es dazu irgendwelche Verbesserungsvorschläge? Kann man das ganz anders besser lösen?
Oder was am besten wäre: Gibt es so etwas fertiges vielleicht schon in einer Lib?! So unglaublich optimized ist ja meine Funktion auch wieder nicht.

Bashar

Da es __int64 nur auf dem Visual C++ gibt, hat sich die Portabilitätsfrage doch von vornherein schon erledigt, wozu noch der Aufwand?

Es geht ja nicht darum, den code portabel zu machen, sondern die erzeugte exe. Und das auch nicht unabhängig vom Betriebssystem sondern einfach nur vom Prozessor und seiner floating-point Arithmetik.

Bashar

Das sind in jedem Fall 32-bit-Intel-kompatible Prozessoren, deren Fließkommaeinheiten gleich funktionieren. Was hängt denn davon ab? Menschenleben? Dann mach, was du für richtig hältst. Ansonsten löst du gerade ein non-problem.

Was heisst Intel-kompatible Prozessoren?
Können AMDs nicht anders rechnen? Können nicht verschiedene Intels anders rechnen?
Und davon hängt einiges ab, nämlich ob mein Spiel im Mehrspielermodus synchron bleibt (<- extreme mega hard-to-find bug).

Bashar

Wie eine Fließkommaeinheit zu rechnen hat ist bis aufs Bit genau spezifiziert, es kann sich also bei Abweichungen nur um Bugs im Prozessor handeln. Ich würd mich darüber nicht fertig machen an deiner Stelle ...

Ist das tatsächlich so? Aber wie erklärt sich dann sowas wie ne for-Schleife, die in 0.1 Schritten hochzählt und es kommt dann irgendwann 10.0000000001 raus?
Oder 49.999999999999 anstatt 50.0?
Kommt das dann auf jedem Prozessor so raus? Das wäre ja sehr erfreulich.

Das kann schon ein Problem sein, siehe ein Problem aus einem anderen Forum:
http://www.usf.de/forum/Forum1/HTML/001688.html
Und das ist nicht mit Standard-C++ loesbar..
-Gunnar

Bashar

Optimizer schrieb:

Ist das tatsächlich so? Aber wie erklärt sich dann sowas wie ne for-Schleife, die in 0.1 Schritten hochzählt und es kommt dann irgendwann 10.0000000001 raus?

Das liegt daran, dass Prozessoren im Binärsystem arbeiten und nur eine begrenzte Bitanzahl haben. Jedem Bit ist eine Zweierpotenz zugeordnet. Bei Ganzzahlen ist das kein Problem, 70 ist z.b. 64 + 4 + 2, also 1000110b, fertig. Aber versuch das mal mit 0.1 ... das ist 1/16 + 1/32 + 1/256 + 1/512 + ... ich könnt das jetzt fortführen, aber lassen wir es dabei, dass es in Kommaschreibweise der periodische Bruch 0,000110011... ist. Irgendwo schneidet der Prozessor ab, und das was übrig bleibt, ist nicht genau 0,1.

SirLant

Wenn ich mich jetzt nicht Irre ist dein Problem mit einem einfach +0.5 vor der
Umwandlung in einen Integer erledigt, wenn die Abweichung mehr als 0.5 ist, dann
stimmt etwas mit deiner Implementierung nicht oder die ALU der CPU hat nen ernsthaftes
Problem, aber alles afaik (fein aus der Afaire zieh )

HumeSikkins

Hallo,
alle Jahre wieder:
What Every Computer Scientist Should Know About Floating-Point Arithmetic

@Bashar:
Ja ok, das ist mir irgendwie schon klar. Der eigentliche Punkt ist ja sowieso nicht, ob das Ergebnis genau ist.
Aber es muss auf allen Prozessoren auf jeden Fall das selbe rauskommen. Davor hab ich eben einfach Angst, dass ich (wie schon mal geschehen) 3-4 Monate lang nen Bug suche, weil das Spiel auf verschiedenen Rechnern unterschiedlich abläuft.
Und wenn das dann an der Fließkomma-Arithmetik liegt, dann flipp ich nämlich echt aus. Deshalb muss ich mir da echt sicher sein.

@SirLant:
Das funktioniert nicht. Fiktiv:
Prozessor 1 rechnet aus: 1.5 -> +0.5 => 2
Prozessor 2 rechnet aus: 1.4999... -> +0.5 => 1

HumeSikkins schrieb:

What Every Computer Scientist Should Know About Floating-Point Arithmetic

Da fühle ich mich angesprochen, das werde ich mir mal zu Gemüte führen.

Danke mal, scheint ja recht ... umfangreich ... zu sein.

Was fuer Wurzeln willst Du denn ziehen? Wenn es nur Wurzeln der ganzen Zahlen von 0 bis 20000 sind, kannst du die doch in einem Loesungsarray statisch abspeichern. Dann hast Du die Gararntie dass es ueberall laeuft und schnell ist es auch.
-Gunnar

Sagen wir es mal so... ich verwende __int64 nicht zum Spaß.

2^63 - 1 == (irgendne 18stellige Zahl)

Bashar

Optimizer: Im Zweifelsfall mußt du mal in irgendwelchen Experten-Newsgroups fragen.

Oh, habe ich uebersehen

Mir hat mal jemand gesagt, dass sqrt (auch Hardwaremaessig) auch nur mit dem Newton-Verfahren zum Wurzelziehen arbeitet. Dabei wird die Wurzel zunaechst so abgeschaetzt, das bewiesenermassen nur eine Handvoll Iterationen (ca. 5?) fuer die benoetigte Genauigkeit ausreicht.

(Ich meine mich dunkel daran zu erinnern dass Volkard hier mal eine einfache Naeherungsformel fuer die Wurzel gepostet hat..)

-Gunnar

volkard

Optimizer schrieb:

Hoi,
ich hab Angst vorm Wurzelziehen. Genauer gesagt, ich brauche die Wurzel aus einem int64.
Ob das Ergebnis danach auf- oder abgerundet wird, ist mir absolut egal, aber was echt wichtig ist, dass auf jedem Computer das selbe Ergebnis rauskommt!
[...]
Ich habe vor einiger Zeit im Matheforum meine eigene Wurzelfunktion vorgestellt, welche mit dem Newton'schen Näherungsverfahren arbeitet, diese ist jedoch etwa um den Faktor 90 langsamer als (double)sqrt(double).

naja, unter faktor 90 werden wir schon kommen. falls verschiedene compiler verwendet werden, isses wohl wichtig, daß die berechnungen mit integers passieren, da haste dann eindeutige ergebnisse. beim gleichen compiler würd ich lieber bashar glauben.

vielleicht raffste ja im gegensatz zu mir eines der verfahren auf http://www.azillionmonkeys.com/qed/sqroot.html und kannst es auf int64 aufblasen. oder du nimmst eines davon und schaust, ob du noch nen newton-schritt dranhängen kannst. newton verdoppelt ja pro schritt die anzahl der genauen stellen und mit nem 32-bittigen zwischenergebnis und einem schritt läßt sich ja vielleicht ein 64-bittiges bauen, das recht genau ist?

zu prüfen wäre überhaupt, ob das runterrechnen auf double nicht bereits zu viele genaue stellen wegschmeißt. wohl nicht, sonst würdest du es nicht machen. wenns ganz ungenau sein darf, nimmste vielleicht gleich nen 32-bittigen integer-sqrt?

Also ich hab mich jetzt mal weiterhin schlau gemacht über Wurzelfunktionen, in der engeren Auswahl sind jetzt nur noch zwei (meine Wurzelfunktion von damals ist schon früh rausgeflogen ). Ich berechne 10000000mal die Wurzel aus const __int64 x = 9887347873i64;

Funktion 1:

__int64 sqrt2(__int64 x)
{
	__int64 result = (__int64)sqrt((double)x)  +  1i64;

	while(result * result  >  x)
		--result;

	return result;
}

In etwa die Funktion, die ich am Anfang des Threads vorgestellt habe, nur dass sie jetzt abrundet statt aufrundet, damit bei beiden Funktionen die selben Ergebnisse rauskommen.
Die Berechnungszeit liegt trotz der beiden typecasts nur bei etwa 2050ms. Das double-sqrt arbeitet scheinbar wirklich unglaublich wahnwitzig schnell.

Funktion 2:

__int64 sqrt3(__int64 x)
{
  __int64 temp, g=0, b = 0x8000, bshft = 15;
  do {
    if (x >= (temp = (((g<<1)+b)<<bshft--))) {
      g += b;
      x -= temp;
    }
  } while (b >>= 1);
  return g;
}

Eine der Funktionen von volkard's Link. Viele der Funktionen dort arbeiten mit fertigen Tabellen und sind deshalb für mich unbrauchbar und eine davon hab ich noch nicht ausreichend verstanden, um sie mit int64 arbeiten zu lassen.
Auf jeden Fall braucht sie etwa 6200ms, was ich eh schon eine wirklich gute Zeit finde.

Ich bin also glaub ich am besten dran, wenn ich bei meiner jetzigen Funktion bleibe. Morgen les ich mir mal das ganze Zeug über floating point Arithmetik durch, um festzustellen ob ich diese albernen checks in der ersten Funktion wirklich brauche...
Wenn ich jetzt nicht nen totalen Denkfehler hab, düfte die obere Funktion (so wie sie jetzt ist) aber selbst bei leicht verfälschten double-Werten das korrekte (und vor allem überall gleiche) Ergebnis liefern.

Hi

mal ne ganz sau blöde frage, musst du umbeding die wutzel aus deiner zahl ziehen? oder lässt sich der algorithmus so umstellen, das du das wutzelziehen gar nicht mehr brauchst?

kleines beispiel:
$\sqrt{a} = b$ kann man auch durch $a = b^2$ vergleichen, wenn du schon angst vor der wurtzelungenauigkeit hast.

gruss Termite

Mis2com

double a = static_cast<double>(static_cast<int>(sqrt(laber)));