Multiplizieren sehr großer Zahlen

Neue Frage »

PHP_Problem Auf diesen Beitrag antworten »
Multiplizieren sehr großer Zahlen
Ich bin gerade dabei ein bisschen mit der Scriptsprache PHP rumzuspielen. Und dabei bin ich auf folgendes Problem gestoßen:

Ich will 0xBC20A4AE (also 3156255918) mit 0x41C64E6D (also 1103515245) miteinander multiplizieren.

PHP kommt mit so großen Zahlen jedoch nicht zurecht:
Dezimal: 3.48297652263E+018
Hexadezimal (mit der dechex()-Funktion): 98a72200

Laut Windows Rechner:
Dezimal: 3482976522634469910
Hexadezimal: 305604B198A72216

Hinzu kommt, dass mich vom Ergebnis nur die letzten 4 Byte, also 98A72216 interessieren.

Da es mit den normalen PHP-Funktionen offensichtlich nicht geht, wollte ich gerne wissen, wie man es "manuell" macht. Sozusagen eine eigene Multiplikationsfunktion, die die Zahlen zusammenrechnet und mir die letzten 4 Byte zurückgibt.

Bitte um Hilfe! Gott
Abakus Auf diesen Beitrag antworten »
RE: Multiplizieren sehr großer Zahlen
Vielleicht reicht es ja, wenn du nur die letzten 4 Bytes jeweils miteinander multiplizierst.

Grüße Abakus smile
Calvin Auf diesen Beitrag antworten »

Das hatte ich auch zuerst geantwortet... und dann schnell wieder gelöscht Big Laugh Die ursprünglichen Zahlen sind genau 4 Byte lang.
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Calvin
Das hatte ich auch zuerst geantwortet... und dann schnell wieder gelöscht Big Laugh Die ursprünglichen Zahlen sind genau 4 Byte lang.


Hm... verwirrt , naja, notfalls rechnet man halt modulo diesen 4 Bytes und schreibt sich seine Multiplikationsroutine selbst.

Ansonsten hängt es von den Funktionen ab, die dieses PHP zur Verfügung stellt. Ist da noch was Brauchbares dabei ?

Grüße Abakus smile
kiste Auf diesen Beitrag antworten »

Du könntest deine eigene Arithmetik schreiben.
Dazu musst du einfach eine geeignete Datenstruktur für große Zahlen finden und eine eigene Multiplikationsfunktion definieren.
Ich hab das selbst schon mal machen müssen allerdings nicht in einer Skript- sondern in einer Hochsprache.
Tobias Auf diesen Beitrag antworten »







Da sich jenseits der ersten 32bit (also 4 Byte) bewegt, musst du nur noch den hinteren Teil auswerten.

Eine Multiplikation mit 2^16 entspricht einer Bitverschiebung von 16 nach links. Also gehen bei nur die unteren 16bit in die letzten 32Bit des Gesamtergebnis ein.

Also:








Addiere zu den unteren 32bit von 63F166340000 noch 32732216:

66340000 + 32732216 = 98A72216

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
 Input: x, y

   x0 = x & 0xFFFF;
   x1 = x >> 16;
   y0 = y & 0xFFFF;
   y1 = y >> 16;
   
   result = ((x0*y1 + x1*y0) << 16) + x0*y0;
 
 
Hannes1984 Auf diesen Beitrag antworten »

Hallo, ich stehe genau vor einem ähnlichem Problem, deshalb hole ich den Thread wieder hervor. Ich will 2, 32 bit zahlen Multipliz. egibt 64bit.
Das Prinzip ist mir klar, habe auch folgenden Code dazu nur leider stimmt irgendwo was nicht verwirrt

>Wenn ich 9212D700 * CC20C500 übergebe

7478B617 5F730000--> kommt raus
7479B617 5F730000-->so solls sein

Vielleicht habt ihr ja eine Ahnung, wo im Code der Fehler liegen kann

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
void multiply_unsigned_long(long x,long y)
{
unsigned long a,b,c,d;
unsigned long p1,p2,p3,hi,lo;

    a = x & 0xffff;    //Lowpart
    b = x >> 16;    //Highpart
    c = y & 0xffff;   //Lowpart
    d = y >> 16;   //Highpart
    p1 = a*c;
    p2 = a*d + b*c;
    p3 = b*d;

    lo = p1;
    hi = p2 >> 16;
    p2 <<= 16;
    if (p2 + lo < lo)
        hi++; // Übertrag in die nächste Stelle
    lo += p2;
    hi += p3;
}


MFG der Hannes
AD Auf diesen Beitrag antworten »

Deine beiden Beispielzahlen sind negativ - klappt es denn mit positiven?

In dem Fall solltest du vielleicht mal den Shiftoperator unter die Lupe nehmen, und vielleicht sowas

b = ((unsigned long)x) >> 16; //Highpart

o.ä. überdenken...
Hannes1984 Auf diesen Beitrag antworten »

Achso die Zahlen sind Unsigned!

In der Funktion oben die Parameter sind auch unsigned habs gerade gesehen. Ich kann mir das aber auch nicht erklären.

Wo genau das Problem ist. Ich werd mal alles in dem Code auseinander nehmen, aber falls jemand was findet bin ich offen dafür smile

Mfg Hannes
AD Auf diesen Beitrag antworten »

Zitat:
Original von Hannes1984
Achso die Zahlen sind Unsigned!

Im Funktionskopf steht aber long, was bei den meisten Architekturen für vorzeichenbehaftete Werte steht. Und wenn das Shift x >> 16 vorzeichenbehaftet durchgeführt wird, kann einiges passieren...
Hannes1984 Auf diesen Beitrag antworten »

Ja ist mir schon klar was du meinst, aber

void multiply_unsigned_long(unsigned long x,unsigned long y)

so sollte der Funktionskopf aussehen. Und nun bleiben wir auch im Unsigned Bereich smile so heist ja auch die Funktion also Negative Zahlen werden hier nicht betrachtet. Ich werd jetzt mal jeden Zwischenschritt prüfen.
AD Auf diesen Beitrag antworten »

Warum schreibst du das dann nicht gleich so mit unsigned long ?

Ok, nächster Punkt:

p2 = a*d + b*c;

Wenn alle vier Zahlen sehr groß sind, z.B. , dann geht dir hier bereits bei der Summenbildung ein Übertrag durch die Lappen - und genau das ist der Fehler im obigen Beispiel!
Tobias Auf diesen Beitrag antworten »

64 Bit kann auch noch eine 32bit CPU.

Zitat:

void multiply_unsigned_long(long x,long y) {

unsigned long hi,lo;

__asm{
mov eax, x
mul y
mov lo, eax
mov hi, edx
}

[...]

}
AD Auf diesen Beitrag antworten »

Wenn man von x86-Archtitektur ausgeht, ja. Augenzwinkern
Tobias Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Wenn man von x86-Archtitektur ausgeht, ja. Augenzwinkern

...was ich in meiner Engstirnigkeit vorausgesetzt habe. Forum Kloppe
AD Auf diesen Beitrag antworten »

Nichts für ungut - erinnert mich an Zeiten, wo ich selbst derartiges verbrochen habe, wie z.B.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
/* y = x / Divisor   mit x,y = size*32 bit unsigned, Divisor=32 bit unsigned  */
unsigned long BigIntegerDivision (unsigned long *y, const unsigned long *x, long size, unsigned long Divisor)
{
    __asm {
        pushf
        mov     edi,y
        mov     esi,x
        xor     ecx,ecx
        xor     edx,edx
Div1:   mov     eax,[esi+4*ecx]
        div     Divisor
        mov     [edi+4*ecx],eax
        inc     ecx
        cmp     ecx,size
        jb      Div1
        popf
        xchg    eax,edx
    }
}
Hannes1984 Auf diesen Beitrag antworten »

Zitat:


p2 = a*d + b*c;

Wenn alle vier Zahlen sehr groß sind, z.B. , dann geht dir hier bereits bei der Summenbildung ein Übertrag durch die Lappen - und genau das ist der Fehler im obigen Beispiel!



Hi besten dank, den Fehler hatte ich dann auch entdeckt, so nun möchte ich den Fehler umgehen mit dem Übertrag, wie könnte ich das denn beseitigen, so das man das Ergebnis in 2 Variablen hat. Oder vielleicht gibt es auch eine bessere Idee
AD Auf diesen Beitrag antworten »

Z.B. so - du hast doch selbst schon eine Übertragerkennung drin, da muss eben noch eine zweite rein:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
void multiply_unsigned_long (unsigned long x, unsigned long y)
{
    unsigned long a,b,c,d;
    unsigned long p1,p2,hi,lo;

    a = x & 0xffff;     //Lowpart
    b = x >> 16;        //Highpart
    c = y & 0xffff;     //Lowpart
    d = y >> 16;        //Highpart
    p1 = a*d;
    p2 = p1+b*c;
    hi = (p1 <= p2 ? 0 : 0x10000);
    hi += p2 >> 16;
    p2 <<= 16;
    lo += a*c+p2;
    if (lo < p2)
        hi++; // Übertrag in die nächste Stelle
    hi += b*d;
}


Ich stimme allerdings Tobias zu, dass man das bei bekannter Architektur viel eleganter in Assembler-Code umsetzen kann, da die meisten Architekturen sowas wie Carry-Flag bei der Addition bieten - oder es geht sogar gleich so kurz wie bei Tobias. Augenzwinkern

Diverse Hochsprachenbibliotheken bieten derlei auch gleich als Funktion (oder Makro?) an. So ist mir z.B. von M$ Visual C bekannt, dass es dort eine derartige Funktion UInt32x32To64 gibt. Deren Umsetzung wird ähnlich der Assembler-Variante von Tobias sein.
Tobias Auf diesen Beitrag antworten »

Oder du implementierst die Multiplikation direkt für beliebig lange Integer.

Dafür habe ich einen nette Link für dich:
http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf

Seite 595 (gedruckt) bzw. 6 im Dokument.

Beachte, dass du hier die Basis 2^16 wählen solltest, da du sonst wieder beim gleichen Problem angekommen bist. Augenzwinkern

Noch eine Möglichkeit wäre, die zwei ulongs hi und low erstmal in 4 ulongs aufzuteilen und dann jeweils nur mit 16Bit zu addieren. Dann kann man die Überträge sofort aus den höheren 16Bit rausfischen und weitergeben. So kommt man ganz ohne Abfragen aus. Ein nicht verifiziertes Beispiel:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
ulong lo, hi, lo_low, lo_high, hi_low, hi_high;

ulong ad = a*d;
ulong bc = b*c;
ulong ac = a*c;

lo_low = d*b;
lo_high = lo_low >> 16;
lo_high += (ad & 0xFFFF);
lo_high += (bc & 0xFFFF);
hi_low = lo_high >> 16;
hi_low += (ad >> 16);
hi_low += (bc >> 16);
hi_low += (ac & 0xFFFF);
hi_high = (hi_low >> 16);
hi_high += (ac >> 16);
lo = (lo_low & 0xFFFF) | (lo_high << 16);
hi = (hi_low & 0xFFFF) | (hi_high << 16);
Hannes1984 Auf diesen Beitrag antworten »

Besten Dank euch beiden, ihr seid Gott , das mit dem ASM muss ich mir mal genauer anschauen, wie Arthur schon gesagt hat, für die Architektur x86 passt das. Mein Programm soll auf einer anderen 32Bit Architektur laufen, aber vielleicht wird mir da auch so etwas geboten durch ASM.

Zu Arthurs letzten Code da ist irgendwo noch ein kleiner Fehler für folgende Parameter kommt

b111f100 * b0fbe700 = 7a6a920d 7b770000

b111f100 * b0fbe700 = 7a6a920e 7b770000 --> wäre richtig


aber ich hab das wesentliche nämlich die Zeile heraus genommen smile nun Funktioniert der Code von mir, ich werde trotzdem noch mal weiter testen ob es noch Ungereimtheiten gibt

code:
1:
2:
hi = (p1 <= p2 ? 0 : 0x10000);
hi += p2 >> 16;
AD Auf diesen Beitrag antworten »

Hast recht, ist ein Fehler drin, aber nicht wo du denkst, sondern in Zeile 15 - da hat sich doch ein falsches += reingemogelt statt des einfachen =. Richtig ist an der Stelle also

code:
1:
    lo = a*c+p2;

Ein "ordentlicher" Compiler müsste bei dem vorherigen falschen Code ein Warning ausgeben, da das += auf eine nicht initialisierte Variable angewandt wurde... Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »