64 bit Überlauf

Hast du denn eine 128 bittigen Integer zur Verfügung? Man könnte evtl. auch gleich über inline asm mit SSE und dessen 128-Bit-Register gehen.
Ansonsten am Beispiel char:

short w = 27*33;
short s = w-w%(sizeof(char)<<CHAR_BIT);

Effizient ist es aber natürlich nicht...

Es steht nur C++ zur Verfügung. (Kein inline ASM)
Ich überlege allerdings mich gleich auf 32 Bit zu beschränken und dann als 64 Bit zu multiplizieren. So müsste ich halt doppelt so viele Multiplikationen machen.

wxSkip

überläufer schrieb:

Es steht nur C++ zur Verfügung. (Kein inline ASM)
Ich überlege allerdings mich gleich auf 32 Bit zu beschränken und dann als 64 Bit zu multiplizieren. So müsste ich halt doppelt so viele Multiplikationen machen.

Ich vermute, das wäre schneller als die 64-Bit-Lösung.

Hier wäre eine mögliche Lösung (ungetestet, nicht optimiert):

typedef unsigned long long ull;
const ull low_32_mask = (~static_cast<ull>(0)) >> 32;

ull high_64_mult(ull first, ull second)
{
    ull first_high = first >> 32, first_low = first & low_32_mask;
    ull second_high = second >> 32, second_low = second & low_32_mask;

    ull result = first_high * second_high;

    ull tmp_1 = first_high * second_low, tmp_2 = first_low * second_high;

    result += (tmp_1 >> 32) + (tmp_2 >> 32);
    result += (((first_low * second_low) >> 32) + (tmp_1 & low_32_mask) + (tmp_2 & low_32_mask)) >> 32;

    return result;
}

nachtfeuer

Überlauf? Was meinst du genau mit "Überlauf"?
Und wozu gibt es eigentlich flags?
Zur Not könnte man auch mit Doubles berechnen, ...moment, was eigentlich genau?

Wenn es nur darum geht, das der Wertebereich überschritten wird, dann kann auch shiften und addieren (mit Carry), und sich ein 128 Bit Register zusammenbasteln.
Aber man sollte dann schon auch wissen, was ein Carryflag ist.

hm oder man könnte sich Anregungen bei google besorgen...
...
http://www.mikrocontroller.net/topic/166621
Ach ja, die mikrocontrollerseite ist immer eine tolle Fundgrube für dies und das...aber selber nachdenken könnte auch schlauer machen

Und die SSE Befehle kannst du auch im Hexeditor reinkleistern, da brauchst du gar kein inline asm...;)

wxSkip

nachtfeuer schrieb:

Überlauf? Was meinst du genau mit "Überlauf"?
Und wozu gibt es eigentlich flags?
Zur Not könnte man auch mit Doubles berechnen, ...moment, was eigentlich genau?

Wenn man zwei 64-Bit-Integer multipliziert, passt das Ergebnis immer in einen 128-Bit-Integer, den er aber nicht hat. Nun hätte er gerne die oberen 64 Bit des nicht vorhandenen 128-Bit-Ergebnisses.

knivil

Schreibe dir einfach eine eigene Klasse int128 ...

cooky451

knivil schrieb:

Schreibe dir einfach eine eigene Klasse int128 ...

Super Idee, und wie multipliziert er dann da rein?

knivil

Indem er einen geeignete Multiplikation definiert, dann zwei Objekte fuer 128 Bit Integer nimmt, mit den 64 Bit Integer initialisiert und ... tata ... multipliziert.

Bashar

Und wie implementiert er die Multiplikation in der Klasse?

knivil

Indem er es genauso macht wie in BigInteger-Bibliotheken ... sicher geht es performanter, z.B.: http://svn.gnucash.org/docs/HEAD/group__Math128.html

SeppJ

Bashar schrieb:

Und wie implementiert er die Multiplikation in der Klasse?

64_Bit_A * 64+Bit_B
= ((32_Bit_A_high << 32) + (32_Bit_A_low)) * ((32_Bit_B_high << 32) + (32_Bit_B_low))
= (32_Bit_A_high * 32_Bit_B_high << 64) + (32_Bit_A_high * 32_Bit_B_low << 32) + (32_Bit_A_low * 32_Bit_B_high << 32) + (32_Bit_A_low * 32_Bit_B_low)

Damit hat man als Überlauf den Teil (32_Bit_A_high * 32_Bit_B_high) plus jeweils die höheren 32-Bit der beiden (64-Bit) Multiplikationsergebnisse 32_Bit_A_high * 32_Bit_B_low und 32_Bit_A_low * 32_Bit_B_high . Dies ist somit sowohl die Lösung der eingangsfrage des TE als auch für knivils 128-Bit-Klasse.

edit: Es kann natürlich noch sein, dass die ganzen unteren Beiträge in der Summe auch noch überlaufen, das muss man auch noch mitnehmen.

edit2: Und das ist, wie ich nun sehe, im Prinzip schon das was knivil als fertigen Quellcode verlinkt hat, bloß dass die auch noch an negative Zahlen u.ä. gedacht haben. Aber wenigstens schön zu sehen, dass meine Überlegung nicht total falsch war.

Bashar

Dann kann er das ja auch so machen, ohne sich eine 128-Bit-Klasse zu basteln. Danke für die Antworten

SeppJ

Bashar schrieb:

Dann kann er das ja auch so machen, ohne sich eine 128-Bit-Klasse zu basteln.

Wenn wir den Threadersteller fragen, warum er das überhaupt wissen möchte, kommt bestimmt, dass er so eine Klasse schreibt.

Bashar

Das macht die Antwort, er solle sich doch einfach so eine Klasse basteln, noch schwachsinniger.

wxSkip

SeppJ schrieb:

edit2: Und das ist, wie ich nun sehe, im Prinzip schon das was knivil als fertigen Quellcode verlinkt hat, bloß dass die auch noch an negative Zahlen u.ä. gedacht haben. Aber wenigstens schön zu sehen, dass meine Überlegung nicht total falsch war.

Und genau das, was ich als Beispielfunktion gepostet habe.

knivil

Bashar schrieb:

Das macht die Antwort, er solle sich doch einfach so eine Klasse basteln, noch schwachsinniger.

Es ging darum, wenn es keinen solchen Typ gibt, sich diesen eben definiert. Und wenn er soweit ist, dass er mal schaut, wie andere dann die Multiplikation definieren. Dann kommt man viel leichte auf den Suchstring bei Google: 128 Bit Klasse ... und dann schaut man sich diejenigen an, die eine Multiplikationsoperation implementieren. Auch wenn du meinen Vorschalg fuer schwachsinnig haelst, so war er als Hilfe zur Selbsthilfe gedacht.