Angst vorm Wurzelziehen

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?

otze

auch wenn sich das problem wahrscheinlich nicht mehr stellt:
ich hab mal gelesen, dass man in der entfernungsberechnung effektiv die wurzel rauswerfen kann(solange man nur einen true/false wert braucht)

wenn
a=√b
dann ist auch
a²=b

natürlich kriegt man dabei nicht die distanz an sich raus,aber wenn man nur so nen code hat wie:

if(distance(a,b)==a.range){
    a.shoot(b);
}

dann brauch man ja nicht die distanz ansich.
und viel umarbeiung is es ja auch nicht, man muss nur beim pytagoras die wurzel rauswerfen.

hoffe geholfen zu haben(wenigstens etwas^^).

Hallo,

das Problem war damals ein anderes. Wenn ich die Entfernungen addieren und dann die Summen vergleichen will, kann ich nicht mit den Quadraten rechnen.
Das Thema hat sich allerdings inzwischen mehr oder weniger erledigt.

otze

die summen kann man auch vergleichen,hat zb david scherfgen bei seiner kugelkollision gemacht.