Angst vorm Wurzelziehen

[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?

[Gast]

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.

[termite_]

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.

[Gast]

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

[der_held]

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.

[Gast]

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

[volkard]

Optimizer schrieb:

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.

ja, böse division!
aber ne gehörige abwichung hatte ich an sich angenommen, weil ein __int64 massig viel mehr genaue stellen kann als ein double. andererseits... wenn der __int64 nur für zahlen bis zu ein paar milliarden verwendet wird, paßt alles noch fein in den double rein.

[Gast]

volkard schrieb:

ja, böse division!

Ähm, allerdings.

Das mit der Anzahl Stellen hab ich noch gar nicht bedacht, aber wenn ichs mir recht überlege, kann ich das eigentlich vernachlässigen. Wie gesagt, das Ergebnis muss nicht extrem genau sein (es sollte natürlich schon in etwa passen ), sondern es muss halt überall gleich sein.
Man, das floating-point zeugs confused mich jetzt langsam wirklich krass, laut IEEE muss das Ergebnis in jedem Bit auf allen Prozessoren gleich sein, aber ich lese immer wieder irgendwo, dass es da Unterschiede geben kann.

[volkard]

ich weiß nicht, wo wann was gerundet wird. aber falls mal die letzte stelle des double hochgerundet wird...
ein double hat 53 bits in der mantisse (wenn ich [url="link"]http://www.opensource.apple.com/darwinsource/10.3/gcc-1495/more-hdrs/synthesize-float[/url] richtig lese). wenn ich nu pech habe und nen wirklich großen int64 zu double mache, setzt er 11 bits auf 0. aus den 11 bits werden beim radizieren 5 1/2, was ne ungenauigkeit von so um 50 macht. also lassen wir die schleife

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

maximal 50-mal laufen. null problemo, würde ich sagen. und bleibste mit den eingangsdaten unter 2^53 (kann ja sein, daß das immer einhaltbar ist), läuft sie gar nicht oder einmal.
ps: bin unsicher, was die zahlen angeht, nimms nur als anstoß.

[Gast]

Ich denke mal, dass ich sicher nicht über 2^45 (über den Daumen gepeilt) hinauskomme. Also werde ich es glaub ich dabei belassen.
Aber ich spiele immer noch mit dem Gedanken, diese Sicherheit ganz wegzulassen. In dem Link steht eigentlich wirklich drin, dasss das Ergebnis auf allen IEEE konformen Prozessoren gleich sein muss.
Es ist sogar genormt, wie nach ganzzahl oder festpunktzahl gecastet wird.
Mal ne dumme Frage: Welche Prozessoren unterliegen dem IEEE Standard? Eigentlich alle, oder?

[Thomson87]

Das klingt vielleicht blöd, aber ich krieg in C++ ne Wurzel nicht gezogen:

int main()
{
double f;

f = 'pow(9, 0.5 )';

cout << f << endl;

cin.get(); cin.get();
return 0;
}

Das klappt so irgendwie nicht!
Kann mir jemad helfen?

[interpreter]

So gehts:

#include <iostream>
#include <cmath>
using namespace std;

int main() 
{ 
double f; 

f = pow(9.0, 0.5 ); 

cout << f << endl; 

cin.get(); cin.get(); 
return 0; 
}

Was sollten die Hochkommata um pow() ?

[Gast]

Krass, wo hast du denn den Thread wieder her??