Angst vorm Wurzelziehen

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

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.

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

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() ?

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

Ringding

Es gibt von Sun eine Library, die so ziemlich in jeder Java VM verwendet wird. fdlibm heißt die und rechnet ziemlich viele mathematische Funktionen ausschließlich mit Integer-Operationen.

wie wärs wenn du das ergebniss falls es eine stelle unter 0.5 ist in eine int var kopierst oder castest?und dann mit 1 addierst.ein primitives bsp.:bei 10.44 würde das ergebniss aberundet werden auf 10.4 jetzt kopierst du das ergebniss in eine int var da hast du 10...+1 =11
nehmen wir an jetzt hast du das ergebniss 10.45 jetzt rundet er auf 10.5 du kopierst es wieder in eine int var und erhälst wieder 11.
ist zwar ungenau aber es muß ja nur immer das selbe ergebniss sein...

also du weißt ja ungefähr was rauskommt...
ergebniss1 ist das ergebniss das du erhälst mit deiner optimierten funktion...

//einfaches beispiel bei werten um 10.0-11

int ergebniss2=ergebniss1;
if(ergebniss2<11)
{
ergebniss2+=1;
}

ich hoffe ich konnte dir helfen...

Deadlef

Ähm *kopfkratz*...
Du schreibst irgendwas von

Bei 9 trifft er, bei 10 ist er außerhalb der Reichweite

Da scheint mir am Konzept was nicht zu stimmen, wenn Du bei den kleinen Zahlen auf einmal in Bereiche bis $2^{45}$ kommst. Ich bin sicher, das ließe sich auch anders lösen mit ein wenig Kopfarbeit

FinalBlackout

Ähhm, wir wärs, wenn ihr einfach mal auf das Datum des Beitrags schaut?

Ringding

Was sind schon ein paar Monate? :p

Wenn er jetzt wieder aktiv ist, kann's ja weitergehen...

Cico schrieb:

wie wärs wenn du das ergebniss falls es eine stelle unter 0.5 ist in eine int var kopierst oder castest?und dann mit 1 addierst.ein primitives bsp.:bei 10.44 würde das ergebniss aberundet werden auf 10.4 jetzt kopierst du das ergebniss in eine int var da hast du 10...+1 =11
nehmen wir an jetzt hast du das ergebniss 10.45 jetzt rundet er auf 10.5 du kopierst es wieder in eine int var und erhälst wieder 11.
ist zwar ungenau aber es muß ja nur immer das selbe ergebniss sein...

also du weißt ja ungefähr was rauskommt...
ergebniss1 ist das ergebniss das du erhälst mit deiner optimierten funktion...
//einfaches beispiel bei werten um 10.0-11

int ergebniss2=ergebniss1;
if(ergebniss2<11)
{
ergebniss2+=1;
}
ich hoffe ich konnte dir helfen...

wasn das fuern quatsch?