Auf heutigen Desktop PCs kommt es nicht umbedingt auf jedes kleine Quäntchen Geschwindigkeit an, möchte man jedoch auf einem Mikrokontroller oder einem anderen nicht so Leistungsstarken System* etwas mehr Zeit gewinnen, kann man die Multiplikation etwas umformen.
Einführung
Zuerst muss man wissen das heutzutage jede CPU, sei es nun ein x86 Prozessor, ein 8051 oder Ähnliches nur mit Einsen und Nullen rechnet. Dies sollte soweit bekannt sein. Um es den Programmierern leichter zu machen gibt es jedoch darüber eine Ebene der sogenannten Assemblersprachen, diese bilden die Kombinationen aus Einsen und Nullen in lesbaren Code ab, sogenannten Maschinencode. Dieser kann von der Maschine direkt verarbeitet werden.
Ein Beispiel:
MOV X,Y |
Bedeutet für den Prozessor, kopiere den Inhalt von Register Y nach Register X. Diese auch Mnemoniks genannten Befehle werden vom Assembler nahezu 1:1 in Opcodes (Einsen und Nullen) umgewandelt.
Zum Beispiel in etwas wie:
110101 010101 010111 |
(Werte erdacht!)
In dem Beispiel stünde die erste Ziffernkolonne für den Befehl MOV, die zweite für die Adresse des Registers X und die dritte Ziffernkolonne für die Adresse von Y.
Die Mnemoniks sind also nur Hilfmittel um sich nicht die Ziffernkolonnen merken zu müssen, was zugegebener Maßen auch sehr mühselig wäre.
Wie funktioniert also eine Multiplikation?
Die meisten CPUs bringen für eine Multiplikation direkt einen eigenen Maschinenbefehl mit, der meistens als Mnemonik MUL heißt. Dieser hat jedoch bestimmte Einschränkungen, so multipliziert er einen Wert mit einem festen Register, meistens dem Akkumulator, einem speziellen Register in jeder CPU.
Das heißt, möchte man 10*2 rechnen sähe das in Assembler (x86) wie folgt aus:
MOV ax, 10 MOV bl, 2 MUL bl |
Das Ergebnis „20“ würde mach diesen 3 Schritten im Register Ax liegen, dem Akku(mulator).
Sieht nicht nach viel aus, ist es im Prinzip auch nicht. Doch stellen wir uns jetzt mal nicht einen Intel Core 2 Quad vor, sondern einen kleinen Prozessor mit wenig Ressourcen.
Verbesserungen!?
Mit etwas Gehirnschmalz findet man heraus das man eine Multiplikation mit „2“ auch in zwei Schritten lösen kann:
MOV ax, 10 SHL ax, 1 |
Was macht dieser Code?
Er schreibt die 10 (dezimal) in das Ax Register, also den Akku, und führt danach eine sogenannte Bitoperation aus, die Bits werden alle um eine Stelle nach Links verschoben. Was einer Multiplikation mit „2“ entspricht.
Wieso, das fragt ihr euch jetzt?
Dazu schauen wir uns den Aufbau des Binärsystems an, also das System der einzelnen Bits mit denen der Prozessor rechnet.
Die 10 (dezimal) wird intern in binärer Darstellung abgelegt, heißt als 1010 (binär). Hierbei steht die erste Null von rechts aus gelesen für 20, die 1 danach für 21 und so weiter bis zur vierten Stelle von rechts, diese steht für 23. Addiert man diese Werte auf erhält man genau 10, die ehemalige Dezimalzahl.
Der Befehl SHL macht nun nichts anderes als alle Bits um eine Stelle im Byte nach links zu schieben und die Lücke die dadurch Rechts entsteht mit einer 0 aufzufüllen.
Heißt also aus 1010 wird nach SHL: 10100
Die eingeschobene Null ist hier fett dargestellt.
10100 entspricht nun Dezimal gesehen: 20.
Also genau einer Multiplikation mit 2!
Im binären Systemen kann man also durch einfaches verschieben der Stellen um eins nach links eine Multiplikation mit 2 erzeugen.
Ich programmiere aber mit Java, C, C++ und nicht mit Assembler…
Kein Problem, auch hier gibt es solche Schiebeoperationen. Meistens durch werden diese durch << oder durch >> ausgeführt, jenachdem ob man nach links oder rechts „shifftet“.
So entspricht die Multiplikation 10*2 in C folgendem Code:
int x = 10<<1 |
Der Bitwert wird damit um eine Stelle nach Links geschoben, denkbar sind so auch leicht Multiplikationen mit Vielfachen von 2.
So entspricht:
int y = 10<<3 |
der Operation 10*8 (10*23).
Man sieht also das man so schneller als mit „normalen“ Multiplikationen zu einem Ergebnis kommt.
Divisionen?
Analog zu einer Multiplikation mit 2 kann man natürlich auch eine Division durch 2 damit erzeugen. Hierbei wird statt nach links einfach nach rechts geschoben (geshiffted). Beachten muss man hier jedoch das man eventuell ungenau wird. Steht an der Stelle die 20 entspricht eine „1“, so wird diese quasi gelöscht und ist verloren. Aus 5/2 wird so 2. Das heißt, Nachkommastellen werden einfach abgeschnitten!
Geschwindigkeit!
Bei kleinen Programmen oder großen und schnellen CPUs ist so ein Verfahren nur zur Verkomplizierung des Codes gut, auf Embedded Systemen oder in sehr großen Schleifen kann es aber durchauch Performancegewinne bringen. Und so sollte eigentlich jeder gute Programmierer mehrere Wege für eine Multiplikation/Division kennen.
Beispiel:
Das folgenden Java Programm zeigt die Unterschiede, hier jedoch nur minimal sichtbar, optimiert der Rechner* doch selber noch etwas am Code und bei Java kann man die Zeiten nicht so genau bestimmen, schliesslich läuft der Prozess in einer Virtuellen Maschine ab.
public class MoveBit { public static void main(String[] args) { int a = 10; int b = 10; long start1 = System.currentTimeMillis(); // "normale" Multiplikation for (long i = 0; i < 1000000000; i++) { a = a * 2; // kann auch als a *= 2; geschrieben werden! } long t1 = System.currentTimeMillis() - start1; // --------------------------------------------------- long start2 = System.currentTimeMillis(); // Bitverschiebung for (long i = 0; i < 1000000000; i++) { b = b << 1; // kann auch als b <<= 1; geschrieben werden! } long t2 = System.currentTimeMillis() - start2; System.out.println("Zeit für 'normale' Multiplikation: " + t1); System.out.println("Zeit für Bitverschiebung: " + t2); } } |
Ergebnis:
Zeit für ’normale‘ Multiplikation: 2703
Zeit für Bitverschiebung: 2469
Man sieht schon einen Unterschied, dieser ist auf kleineren Systeme* jedoch noch größer und wiegt mehr auf.
Und was ist mit 10*5?
„Krumme“ Werte kann man in Zweierpotenzen zerlegen und dann verschieben, danach addiert man den fehlenden Rest wieder drauf und erhält so auch ein Ergebnis. Das bekommt ihr aber sicher auch jetzt alleine hin :).
Mehr Informationen dazu auch unter http://dcla.rkhb.de/mul.html.