Berechnung mit großen Zahlen. Variablenüberlauf?

st3fan85

Hi,
ich verwende MinGW auf Windows. In dem Paketmanager von MinGW ist der Gcc32 vermerkt. Heißt wohl die 32bit Version von GCC?
Ich habe es mit uint64_t versucht:

int xj, yj;
long Vi, Vj;
int xi = 1059;
int yi = 1041;
xj = 951;
yj = 957;
Vi = 109239;
Vj = 2162117;
long new_V = Vi + Vj;
uint64_t new_x = ((Vi*xi+Vj*xj) / new_V);
uint64_t new_y = ((Vi*yi+Vj*yj) / new_V);
cout <<new_x <<" ; " <<new_y  <<endl;

new_x = ((Vi*xi/ new_V + Vj*xj/ new_V) );
new_y = ((Vi*yi/ new_V + Vj*yj/ new_V) );
cout <<new_x <<" ; " <<new_y  <<endl;
}

Ausgabe:
18446744073709550682 ; 18446744073709550687
955 ; 960

Das Problem ist, wenn die Größe der Zahlen sich nur um eine Größenordnung erhöht, dann reicht auch die Methode mit dem getrennten dividieren nicht mehr aus. Und die Zahlen werden sich noch um mehr als eine Größenordnung erhöhen.

Ist hier die Grenze von MinGW erreicht?

Wutz

@st3fan85
Auch MinGW-64Bit bietet den (Nicht-Standard) Datentyp __uint128_t an, das sollte für deine Rechnungen erstmal reichen.
Schwieriger wird es dabei aber mit printf&Co.
Mein Compiler zB. heißt x86_64-w64-mingw32-gcc.exe, und der ist 64Bit.

Schlangenmensch

@st3fan85 Aufgrund der ~~Auswertungsreihenfolge~~ verwendeten Datentypen will der Compiler (Vi*xi+Vj*xj) trotzdem erstmal zu einem 32 bit Integer Auswerten, ~~weil xj und yj 32 bit groß sind~~. Wenn du ~~die~~ irgendwas davon zu int64_tmachst, denke ich, dass die Zahlen aus deinem Beispiel funktionieren

Th69

Problem bei uint64_t new_x = ((Vi*xi+Vj*xj) / new_V); ist, daß der Ausdruck zuerst mit long (als größter Datentyp der benutzen Variablen) berechnet wird und danach erst das Ergebnis davon in ein uint64_t gecastet wird.

Man müßte also z.B. auch die verwendeten Variablen schon als uint64_t deklarieren.

Schlangenmensch

Natürlich, dass was @Th69 sagt.

mgaeckler

@Schlangenmensch Könnt Ihr euch mal angewöhnen Konjunktionen und Relativpronomen nicht durcheinander zu bringen? Das tut weh und Du bist schon der zweite hier in diesem Thread.

hustbaer

@Th69 sagte in Berechnung mit großen Zahlen. Variablenüberlauf?:

uint64_t new_x = ((Vi*xi+Vj*xj) / new_V);

uint64_t new_x = ((int64_t{Vi}*xi+int64_t{Vj}*xj) / new_V);

Alternativ: verwende gleich int64_t als Typ für Vi und Vj. long macht in den wenigsten Fällen Sinn, weil es auf sehr üblichen Compilern/Plattformen eben 32 oder auch 64 Bit sein kann (je nachdem ob du für 32 oder 64 Bit kompilierst). long nehme ich nur wenn ich mit einer API arbeite die long verwendet (z.B. die long irgendwo zurückgibt und dann den selben Wert wieder irgendwo als Parameter haben will).

Th69

@hustbaer: Das habe ich extra nicht vorgeschlagen, da es sehr unleserlich ist...

hustbaer

@Th69
Unleserlich ist relativ
Aber ja, es wäre vermutlich besser einfach int64_t überall zu verwenden.
Für Storage kann man es ja wenn nötig auf kleinere Typen runterkonvertieren, aber bei der Berechnung hat man auf 64 Bit Plattformen kaum einen Vorteil wenn man kleinere Typen für die Variablen verwendet.

Finnegan

@hustbaer sagte in Berechnung mit großen Zahlen. Variablenüberlauf?:

Für Storage kann man es ja wenn nötig auf kleinere Typen runterkonvertieren, aber bei der Berechnung hat man auf 64 Bit Plattformen kaum einen Vorteil wenn man kleinere Typen für die Variablen verwendet.

Es wären durchaus ein paar SIMD-ähnliche Optimierungen in allgemeinen Registern denkbar, wenn noch Platz für weitere Werte ist - auch ohne Instruktionen einer SIMD-Befehlssatzerweiterung zu verwenden. Stichwort SWAR. Gibt ein paar Bitschubser-Algorithmen, die diesbezüglich gekonnt tricksen.

Ob aber auch Compiler sowas machen weiss ich nicht - hat das schonmal jemand von euch beobachtet? Man könnte ja schon z.B. zwei 32-Bit-Additionen als eine 64-Bit-Additon umsetzen, wenn man die Überläufe manuell behandelt.

st3fan85

Hallo,
vielen Dank für die Hilfe! Ich verwende jetzt alle Variablen als Typ uint64_t.
Zur Info, sobald zwei Variablen aus der Gleichung (Vi*xi+Vj*xj) in uint64_t vorhanden sind, passt das Ergebnis.