Skip navigation

ARES

Site Search

Page Content:

Mathematik mit Redcode

Die Hauptaufgabe von Computern ist ja eigentlich das Berechnen verschiedenster Dinge. Als Benutzer bemerkt man das vielleicht nicht so direkt, aber als Programmierer hat man ständig damit zu tun. Auch Core War-Kampfprogramme müssen gelegentlich etwas berechnen. Redcode kennt fünf mathematische Instruktionen:

Mathematische Instruktionen
Opcode Bedeutung
ADD Addition
SUB Subtraktion
MUL Multiplikation
DIV Ganzzahlige Division
MOD Rest einer Division

Jeder dieser Befehle verwendet zwei Operatoren, wobei das Ergebnis in der Zelle gespeichert wird, die durch den Operand B ("Target") angegeben ist. Bei Division und Modulo ist zu beachten, daß B ÷ A gerechnet wird.

Die folgenden Beispiele dienen nur der Erklärung, solche Berechnungen kommen normalerweise nicht in Kampfprogrammen vor:

Potenzen

Da es nur die arithmetischen Grundoperationen als Maschinenbefehle gibt, muß man die höheren Funktionen durch Programme nachbilden. Ein einfaches Beispiel dafür ist die Berechnung einer Potenz be = b * b * ... * b, e-Mal. Also bilden wir eine Programmschleife, die b e-Mal mit sich selbst multiplizert. Dieses Beispiel berechnet p = be, mit b=2 und e=3:
  loop   MUL   b,    p    p mit b multiplizieren
         DJN   loop, e    e um eins verkleinern
         ... 
  p      DAT   #1         p = 1 * b * b * b...
  b      DAT   #2         Basis
  e      DAT   #3         Exponent
Nach dem die Schleife dreimal durchlaufen wurde, ist e = 0 und in p liegt der Wert #8. Die Werte für b und e können beliebig gewählt werden.

Absoluter Betrag

Diese Funktion wäre eigentlich auch sehr leicht zu implementieren. Der absolute BetragExternal Link einer Zahl ist die selbe Zahl, nur ohne Vorzeichen. Also: |n| ist gleich n, wenn n ≥ 0 ist, und n * (-1), wenn n < 0. Ein Programm für diese Berechnung würde so aussehen:
  start     SLT   #0,    n    ist 0 < n, dann wird der nächste Befehl übersprungen
  skipless  MUL   #-1,   n    ist n <= 0, dann mit (-1) multiplizieren
            ... 
  n         DAT   #123
Dieses nette Programm funktioniert in einem MARS-Computer allerdings nicht, denn...

Negative Zahlen

gibt es im Krieg der Kerne nicht. Weil der Speicher ringförmig aufgebaut ist, ist es egal, ob man eine Zelle zurück geht, oder CORESIZE-1 Zellen nach vorne. Werte, die z. B. durch Addition oder Subtraktion ausserhalb des Bereiches 0 ... CORESIZE-1 zu liegen kommen, werden vom MARS automatisch modulo CORESIZE gerechnet, d. h. sie werden auf den Rest der Division durch CORESIZE gekürzt: n ← n % CORESIZE. Negative Zahlen werden dabei in den positiven Bereich "verschoben". ARES zeigt allerdings negative Zahlen an - sofern man nicht mit STRG-I auf Anzeige absoluter Werte umschaltet. Üblicherweise wird Core War mit einer Speichergröße von 8000 Zellen gespielt. In diesem Fall werden alle Werte ab 4000 von ARES als negative Werte angezeigt, was meistens auch sinngemäß ist. Negative Werte n sind also als 8000 - n zu verstehen.

Wenn man unbedingt mit negativen Zahlen arbeiten möchte, kann man auch in einem MARS-Programm einfach vorsehen, daß alle Werte die größer als 4000 sind, als negative Zahlen betrachtet werden. Der eigentliche Wert dieser Zahl ist dann der Abstand zu 8000 und der absolute Wert ist durch die Formel Abs(n) = 8000 - n gegeben.

Ein Programm zur Berechnung des Absolutwertes könnte daher so aussehen:
  start   SLT   #CORESIZE/2,   n       ist n "negativ"?
          JMP   done                   Nein: dann fertig
          SUB   n,             temp    quasi * (-1)
          MOV   temp,          n       Ergebnis in n ablegen
  done    ... 
  n       DAT   #-1000 
  temp    DAT   #CORESIZE              Im MARS-Speicher eigentlich = 0

Primzahlen

Die Aufgabe, festzustellen, ob eine Zahl eine PrimzahlExternal Link ist, ist schon etwas schwieriger zu lösen: Eine Primzahl zeichnet sich bekanntlich dadurch aus, daß sie nur durch sich selbst und durch Eins teilbar ist. Das folgende Programm testet zunächst, ob bei der Division der Zahl n durch 2 ein Rest bleibt. Wenn nicht, dann handelt es sich um eine gerade Zahl. Falls ein Rest geblieben ist, prüft die Routine die Division durch alle ungeraden Zahlen, bis entweder eine Division keinen Rest hat oder eine Division durch n getestet wird. Sollte bis dahin keine Teilbarkeit durch eine der kleineren ungeraden Zahlen gefunden worden sein, so handelt es sich um eine Primzahl. (Das folgende Programm verwendet Opcode Modifiers, die bisher noch nicht erklärt wurden)
  start       MOV     n,           temp 
              MOD     #2,          temp    Prüfe, ob n/2 keinen Rest hat 
              JMZ     not_prime,   temp    Ende bei gerader Zahl 

  loop        MOV     n,           temp 
  check       MOD     #3,          temp    Probiere div (x*2)+1 
              JMZ     not_prime,   temp    Kein Rest, dann fertig! 

              ADD.a   #2,          check   Nächste ungerade Zahl in den MOD schreiben 

              SLT.ab  check,       n       Dividieren wir n / n ? 
              JMP     is_prime             Ja: fertig! 
              JMP     loop                 Nein: weiter 

  temp        DAT   #0 
  n           DAT   #73*73

  not_prime   ... 
  is_prime    ...
Es sei noch angemerkt, daß dieses Programm die Aufgabe nicht optimal löst: Zum einen bräuchte man nicht durch 9 dividieren, wenn schon festgestellt wurde, daß die Zahl nicht durch 3 teilbar ist. Zum anderen könnte man aufhören zu probieren, wenn man bereits erfolglos versucht hat, n durch die abgerundete Wurzel von n zu dividieren.

→ Multitasking

Content Management:

μCMS α1.6