Multiplizieren sehr großer Zahlen |
01.03.2007, 15:52 | PHP_Problem | Auf diesen Beitrag antworten » | |||||
Multiplizieren sehr großer Zahlen 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! |
|||||||
02.03.2007, 22:59 | 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 |
|||||||
02.03.2007, 23:01 | Calvin | Auf diesen Beitrag antworten » | |||||
Das hatte ich auch zuerst geantwortet... und dann schnell wieder gelöscht Die ursprünglichen Zahlen sind genau 4 Byte lang. |
|||||||
02.03.2007, 23:10 | Abakus | Auf diesen Beitrag antworten » | |||||
Hm... , 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 |
|||||||
02.03.2007, 23:19 | 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. |
|||||||
03.03.2007, 14:36 | 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
|
|||||||
Anzeige | |||||||
|
|||||||
20.04.2007, 11:54 | 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 >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
MFG der Hannes |
|||||||
20.04.2007, 12:07 | 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... |
|||||||
20.04.2007, 12:13 | 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 Mfg Hannes |
|||||||
20.04.2007, 12:17 | AD | Auf diesen Beitrag antworten » | |||||
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... |
|||||||
20.04.2007, 12:26 | 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 so heist ja auch die Funktion also Negative Zahlen werden hier nicht betrachtet. Ich werd jetzt mal jeden Zwischenschritt prüfen. |
|||||||
20.04.2007, 13:38 | 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! |
|||||||
20.04.2007, 13:52 | Tobias | Auf diesen Beitrag antworten » | |||||
64 Bit kann auch noch eine 32bit CPU.
|
|||||||
20.04.2007, 13:55 | AD | Auf diesen Beitrag antworten » | |||||
Wenn man von x86-Archtitektur ausgeht, ja. |
|||||||
20.04.2007, 14:02 | Tobias | Auf diesen Beitrag antworten » | |||||
...was ich in meiner Engstirnigkeit vorausgesetzt habe. |
|||||||
20.04.2007, 14:25 | AD | Auf diesen Beitrag antworten » | |||||
Nichts für ungut - erinnert mich an Zeiten, wo ich selbst derartiges verbrochen habe, wie z.B.
|
|||||||
23.04.2007, 09:00 | Hannes1984 | Auf diesen Beitrag antworten » | |||||
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 |
|||||||
23.04.2007, 09:40 | AD | Auf diesen Beitrag antworten » | |||||
Z.B. so - du hast doch selbst schon eine Übertragerkennung drin, da muss eben noch eine zweite rein:
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. 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. |
|||||||
23.04.2007, 10:19 | 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. 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:
|
|||||||
23.04.2007, 12:12 | Hannes1984 | Auf diesen Beitrag antworten » | |||||
Besten Dank euch beiden, ihr seid , 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 nun Funktioniert der Code von mir, ich werde trotzdem noch mal weiter testen ob es noch Ungereimtheiten gibt
|
|||||||
23.04.2007, 14: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
Ein "ordentlicher" Compiler müsste bei dem vorherigen falschen Code ein Warning ausgeben, da das += auf eine nicht initialisierte Variable angewandt wurde... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|