Multiplimation und Division in mehreren Maschinenwörtern?

S

speedo

0
Seid gegrüßt!

Da ich gerade ein Programm schreibe, in dem ich mit größeren Zahlen hantieren muss, komme ich mit dem herkömmlichen 0 bis 2^32-1 -Zahlenbereich meines Computers nicht aus. Auf (unsigned long long) möchte ich eigentlich verzichten, was mich auf die Idee kommen ließ, einfach die mathematischen Operationen auf mehreren unsignd ints (jeweils 32 Bit) durchzuführen.

Addition und Subtraktion ist da recht einfach. Hier habe ich die Addition und die Subtraktion erst auf das eine Wort durchgefürt und im Fall eines Überlaufs auch auf das andere.

Was ein bisschen komplizierter ist, ist die Multiplikation und die Division.

Um ein stark vereinfachtes Beispiel zu geben, stelle ich das mal in form von 4-Bit Words dar:

Word#1: 0001
Word#2: 0000 (Dezimal 16)


Word#1: 0000
Word#2: 0011 (Dezimal 3)

Sicher ginge es, jetzt einfach so oft 3 zu subtrahieren, bis ein rest überig bleibt, der < 3 ist, aber ich erhoffe mir von der Frage hier, dass es einen schnelleren Weg gibt.

Kann mir da jemand helfen?


lg, speedo
 
Zuerst einmal ein verspätetes Danke :)

Dieser Code hat mir sehr geholfen, eine Moltiplikation zu implementieren. Die Division allerdings ist da recht kryptisch. :(

Gibt es vielleicht noch einen Code bzw. ein Doc, welches die Division möglichst ausführlich erklärt?


lg, speedo
 
hab in den code dort nicht reingeschaut, aber das einfachste was mir einfällt (a >= 0 && b > 0):

a/b = c

1. c=0;
2. b n mal shiften, bis du den größten wert hast, der kleiner als a ist;
c += 2^n;
a -= 2^n * b;

2. machst du solange bis b> a, also im prinzip das gleiche wie schriftlich dividieren.
(ungetesteter Gedanke ohne Garantie von Fehlerfreiheit, aber der Gedanke dahinter funktioniert. ist im prnizip das gleiche, wie b von a abziehen und dabei zu zählen, wie oft man's gemacht hat. ist aber in weniger als n iterationen fertig, wobei n die die anzahl der bits von a ist)

wenn man das effizient implementiert sieht's etwas kryptisch aus.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben