Angst vorm Wurzelziehen

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

Michael E.

@termite_: Na dann erklär mir mal bitte, wie du von a auf b kommst, ohne eine Wurzel zu ziehen (und jetzt bitte nicht so lange b vergrößern/verkleinern, bis a so groß ist wie b²)

davie

Mis2com schrieb:

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

oder gleich

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

BugJoe

Ja, ich muss die Wurzel ziehen, weil ich Entfernungen aufaddieren muss, da kann ich nicht mit den Quadraten arbeiten.

EDIT: Post by Optimizer mit Account von Kumpel

Das double-sqrt arbeitet scheinbar wirklich unglaublich wahnwitzig schnell

Das liegt daran, dass die sqrt function hardware beschleunig ist, der FPU besitzt hardware Proceduren um:
-quaratische Wurzeln zu ziehen (FSQRT)
-Sinus zu rechenen (FSIN)
-Kosinus zu rechenen (FCOS)
Es gibt noch weitere allerdings werden die in der Regel nicht von Compilern genutzt.

Also von Kompiler zu Kompiler kann es Unterschiede geben, da sqrt ja nicht mit FSQRT impementiert sein muss und sqrt oft als reale Funktion implementiert ist und nicht als inline (weil von C gerbt) und deswegen müssen ein paar Kopien von deiem double angefertigt werden (min 2) müssen und da können wenn schlect gemacht ein paar Kommastellen drauf gehen.

Was heisst Intel-kompatible Prozessoren?
Können AMDs nicht anders rechnen? Können nicht verschiedene Intels anders rechnen?

FSQRT müsst eigentlich immer das selbe Ergebnis liefern, ist zwar nicht explicit in den Intel ASM docs angegeben, allerdings steht da auch nicht, dass es nicht so wäre:

Intel schrieb:

Computes the square root of the source value in the ST(0) register and stores the result in ST(0). The following table shows the results obtained when taking the square root of various classes of numbers, assuming that neither overflow nor underflow occurs.

(Die angesprochene Tabelle ist unwichtig)
Die AMD docs hab ich nicht zur Verfügung allerdings dürfte es keinen Unterschied geben (wie gesagt dürfte)

nämlich ob mein Spiel im Mehrspielermodus synchron bleibt

Allerdings würde es mich schon interessieren, wo es in einem Spiel so wichtig ob ein Wert nun 58882124543 oder 58882124544 ist. Die einzige Anwendung dir mir spontan einfällt wäre um die Distance zwischen 2 Punkten zu rechnen, wenn du da Angst hast, dass ein Vergleich nun nicht true ergeben würde, dann Vergleich auf pi mal Daumen:

int a=845,b=846;
if(abs(a-b)<10){
  cout<<"Ungefähr gleich"<<endl;
}

Walli

CME386 schrieb:

@termite_: Na dann erklär mir mal bitte, wie du von a auf b kommst, ohne eine Wurzel zu ziehen (und jetzt bitte nicht so lange b vergrößern/verkleinern, bis a so groß ist wie b²)

Es war die Frage, ob man den Algortihmus nicht umstellen könnte, so dass eine Wurzel redundant würde. Manchmal hilft es ein wenig den Algorithmus zu überdenken, aber in diesem konkreten Fall anscheinend nicht.

*** schrieb:

nämlich ob mein Spiel im Mehrspielermodus synchron bleibt

Allerdings würde es mich schon interessieren, wo es in einem Spiel so wichtig ob ein Wert nun 58882124543 oder 58882124544 ist. Die einzige Anwendung dir mir spontan einfällt wäre um die Distance zwischen 2 Punkten zu rechnen, wenn du da Angst hast, dass ein Vergleich nun nicht true ergeben würde, dann Vergleich auf pi mal Daumen:
int a=845,b=846;
if(abs(a-b)<10){
  cout<<"Ungefähr gleich"<<endl;
}

Nein, das "ungefähr" nützt leider gar nichts, dann ist es auf einem Rechner 9 -> in Reichweite und auf dem anderen 10 -> nicht in Reichweite.
Das muss genau passen.

Aus Hume's Link entnehme ich:

The IEEE standard goes further than just requiring the use of a guard digit. It gives an algorithm for addition, subtraction, multiplication, division and square root, and requires that implementations produce the same result as that algorithm. Thus, when a program is moved from one machine to another, the results of the basic operations will be the same in every bit if both machines support the IEEE standard.

Das hört sich sehr positiv an. Ich werd mich da noch ein wenig mehr schlau machen.
Wenn jemand noch mehr Informationen zu diesem Thema hat, möge er sie doch bitte hier noch posten.

Wie wäre es so:

__int64 sqrt64 (__int64 value)
{
  __int64 tmp = static_cast<__int64>(std::sqrt(static_cast<double>(value)));
  while (tmp * tmp > value)
  {
    tmp = (tmp + value / tmp) / 2;
  }
  return tmp;
}

volkard

der_held schrieb:

Wie wäre es so:

__int64 sqrt64 (__int64 value)
{
  __int64 tmp = static_cast<__int64>(std::sqrt(static_cast<double>(value)));
  while (tmp * tmp > value)
  {
    tmp = (tmp + value / tmp) / 2;
  }
  return tmp;
}

sieht überzeugend aus. evtl die schleife wegschmeißen und den iterationsschritt ohne nachzudenken immer genau einmal oder immer genau zweimal machen.

der_held schrieb:

Wie wäre es so:

__int64 sqrt64 (__int64 value)
{
  __int64 tmp = static_cast<__int64>(std::sqrt(static_cast<double>(value)));
  while (tmp * tmp > value)
  {
    tmp = (tmp + value / tmp) / 2;
  }
  return tmp;
}

Glaubt ihr nicht, dass

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

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

    return result; 
}

schneller ist? Ich erwarte nämlich eigentlich keine größere Abweichung als 1 (eigentlich erwarte ich gar keine Abweichung). Und so ne __int64 Division ist nach meiner Erfahrung recht langsam.

Aber zumindest ist die Idee interressant, beim oberen Code die Schleife zu kicken...