Blog

Multiplikation

Die ganzzahlige Multiplikation von Werten lässt sich durch wiederholte Addition realisieren, da folgendes gilt:

a*b = Sum (i=1 … a) b

Der folgende Code funktioniert allerdings nur bei ganzzahligen Werten für a. Dafür wird allerdings auch das Vorzeichen von a berücksichtigt. Das Ergebnis der Berechnung wird in der Speicherzelle c (3) abgelegt.

          @Start        # Initialisierung des Programmzeigers
Step:     -3            # Schrittweite des Programmzeigers
a:        10            # Wert für a, hier: 10
b:        5             # Wert für b, hier: 5
c:        0             # Wert für c,wird das Ergebnis beinhalten
i:        0             # Wert für i, Schleifenvariable
tmp:      0             # Wert für tmp, temporärer Speicher
one:      1             # Wert für one, Konstante 1

REM Schleifenvariable i setzen

Start:    JA @a @posi   # a>0, a muss erst negiert werden
          SUB @i @a     # ansonsten a negativ in i transferieren
          JA 0 @loop    # zur Multiplikation
posi:     SUB @tmp @a   # tmp = -a
          SUB @i @tmp   # i = -tmp = a
          SUB @tmp @tmp # tmp = 0

REM while i>0 ...

loop:     JA @i @next   # Wenn i größer als 0 ist, weiter, sonst

REM Schleife beendet, Ergebnis invertieren

          SUB @c @c     # c = 0
          JA @a @posa

REM a war negativ

          SUB @i @i     # i = 0
          SUB @i @tmp   # i = -tmp
          SUB @c @i     # c = -i = tmp
          SUB 0 0       # Programm beenden

REM a war positiv

posa:     SUB @c @tmp   # c = -tmp
          SUB 0 0       # Programm beenden

REM Schleifeninhalt, eine weitere Addition

next:     SUB @i @one   # i dekrementieren
          SUB @tmp @b   # tmp = tmp - b
          JA 0 @loop

In diesem Beispiel kommt erstmals auch eine Schleife im Sinne von while i>0 zum Einsatz.

Der Code lässt sich kürzer fassen, wenn z. B. die Überprüfung auf das Vorzeichen von a verzichtet werden kann oder die Speicherstellen für a und b nicht erhalten bleiben müssen. Auch ist dies sicherlich nicht die Effizienteste Möglichkeit, wenn mit großen Zahlen agiert wird. Die Berechnung von 1.000.000*1 macht dies deutlich. Zugleich wird wird 1*1.000.000 erheblich schneller berechnet, so dass es in einem optimierten Code Sinn machen kann, die Eingangswerte zunächst zu vergleichen und die Schleife über den kleineren Wert laufen zu lassen.

          @Start          # Initialisierung des Programmzeigers
Step:     -3              # Schrittweite des Programmzeigers
a:        10              # Wert für a, hier: 10
b:        5               # Wert für b, hier: 5
c:        0               # Wert für c,wird das Ergebnis beinhalten
i:        0               # Wert für i, Schleifenvariable
tmp:      0               # Wert für tmp, temporärer Speicher
absa:     0               # a Vorzeichenlos
absb:     0               # b Vorzeichenlos
one:      1               # Wert für one, Konstante 1
min:      0               # Speicher für den kleineren Wert
max:      0               # Speicher für den größeren Wert

Start:    

REM Optimierung der Multiplikation durch Sortierung der Eingangsgrößen
REM um die äußere Schleife nur über den kleineren Faktor laufen zu lassen.

REM Absolutwert für b ermitteln

          JA  @b @posb    # b>0
          SUB @absb @b	  # chg = -b
		  JA  0 @checka
posb:     SUB @tmp @b     # tmp = -b
          SUB @absb @tmp  # absb = -tmp = b
		  SUB @tmp @tmp   # tmp = 0
		  
REM Absolutwert für a ermitteln

checka:   JA  @a @posa    # a>0
          SUB @absa @a	  # chg = -a
		  JA  0 @posab
posa:     SUB @tmp @a     # tmp = -a
          SUB @absa @tmp  # absa = -tmp = a
		  SUB @tmp @tmp   # tmp = 0		  
		  
REM Vergleich der Absolutwerte und Belegung der Hilfsvariablen
REM min, max und i

posab:    SUB @absb @absa # absb = absb - absa
          JA  @absb @bgra # b>a
		  SUB @tmp @a
          SUB @min @tmp   # min = a
		  SUB @tmp @tmp
		  SUB @tmp @absa
		  SUB @i @tmp     # i = |a|
		  SUB @tmp @tmp
		  SUB @tmp @b
		  SUB @max @tmp   # max = b
		  SUB @tmp @tmp
		  JA  0 @loop
bgra:     SUB @tmp @a    
          SUB @max @tmp   # max = 0
		  SUB @tmp @tmp
		  SUB @tmp @b
          SUB @min @tmp   # min = b
		  SUB @i @tmp
		  SUB @tmp @tmp

REM Multiplikation von min und max in einer Schleife über i = min		  
REM while i>0 ...

loop:     JA  @i @next    # Wenn i größer als 0 ist, weiter, sonst

REM Schleife beendet, Ergebnis ggf. invertieren in abh. vom Vorzeichen
REM des kleineren Werts (min)

          SUB @c @c       # c = 0
          JA  @min @posmin

REM min war negativ

          SUB @i @i       # i = 0
          SUB @i @tmp     # i = -tmp
          SUB @c @i       # c = -i = tmp
          SUB 0 0         # Programm beenden

REM min war positiv

posmin:   SUB @c @tmp     # c = -tmp
          SUB 0 0         # Programm beenden

REM Schleifeninhalt, eine weitere Addition

next:     SUB @i @one     # i dekrementieren
          SUB @tmp @max   # tmp = tmp - b
          JA  0 @loop

Eine weitere Verbesserung kann das Zerlegen in Primfaktoren darstellen, wenn a = a₁*a₂*a₃*…*an+a₀*1 ist. In dem Fall muss die Schleife nicht über a, sondern nur über die Summe von a₀ bis a_n gehen. Bei a = 1.000 = 2*2*2*5*5*5 wären so lediglich 21 statt 1000 innere Iterationen erforderlich. Die Berechnung, bzw. der Aufwand für die Berechnung der Primfaktoren stellt dann allerdings noch eine andere Größe dar.