\documentclass[11pt,a4paper]{article} \usepackage[ansinew]{inputenc} \usepackage[margin=2.5cm,nohead]{geometry} \usepackage{amssymb} \usepackage{amsmath} \usepackage{wasysym} \usepackage{ngerman,latexsym,alltt,graphicx,textcomp} \usepackage[bookmarks, colorlinks=false, pdftitle={MRT I Praktikumsprotokoll}, pdfauthor={Fabian Kurz, http://fkurz.net/}, pdfsubject={Von Neumann-Simulator}, pdfkeywords={TU Dresden, Praktikum, Mikrorechentechnik}, linkbordercolor={1 1 1}]{hyperref} \date{\today} \author{Fabian~Kurz, Alexander Eder\\Stephan Stiebitz, Phillip Burker} \title{Praktikumsprotokoll -- Mikrorechentechnik I\\Versuch "`Von-Neumann-Simulator"'} \begin{document} \setlength{\parindent}{0pt} \setcounter{secnumdepth}{4} \maketitle \tableofcontents \newpage \section{Aufgabenstellung} Im Praktikumsversuch zum "`Von-Neumann-Simulator"' ist ein Programm zu entwerfen, welches die die Operation \[Y = X!\] realisiert. Dazu wird eine ganzzahlige Ziffer $X : 0 \leq X \leq 4$ über die Tastatur eingelesen und deren Fakultät nach der Berechung auf dem Bildschirm ausgegeben. \section{Lösung} \subsection{Programmentwurf, Algorithmus} Das Produkt der natürlichen Zahlen von $1$ bis $n$ bezeichnet man mit $n!$ ("`$n$--Fakultät). Zusätzlich ist festgelegt, daß $0! = 1$ ist. \smallskip Ein Algorithmus zur Berechnung der Fakultät läßt sich also verbal folgendermaßen beschreiben: \bigskip \hrule \begin{verbatim} Lese ZAHL ein Falls ZAHL gleich NULL ist, gib EINS aus und beende. Sonst { Setze ERGEBNIS auf ZAHL Solange ZAHL nicht NULL ist { Multipliziere ERGEBNIS mit ZAHL, speichere in ERGEBNIS Dekrementiere ZAHL } } Gib ERGEBNIS aus \end{verbatim} \hrule \bigskip Da der im Praktikum verwendete Simulator jedoch als arithmetische Operationen lediglich Addition und Subtraktion beherrscht, muß die Multiplikation zur Bildung der Fakultät als wiederholte Addition ausgeführt werden. Hierfür ist eine weitere Schleife erforderlich, es ergibt sich folgender Algorithmus: \bigskip \hrule \begin{verbatim} Lese FAKTOR1 und FAKTOR2 ein Solange FAKTOR2 größer als 1 ist { Addiere FAKTOR1 zu SUMME Dekrementiere FAKTOR2 } Gib SUMME aus \end{verbatim} \hrule \bigskip Anhand des somit kompletten Algorithmus konnte das Programm einfach in Assemblersprache übertragen werden. Der komplette und ausführlich dokumentierte Quelltext befindet sich im Anhang A. \subsection{Probleme} \setlength{\parindent}{20pt} Nennenswerte Probleme traten weder bei der Findung des Algorithmus, noch bei der Implementierung in Assemblersprache auf. Die erste lauffähige Version lieferte ein Ergebnis von $n! \cdot (n-1)$, was jedoch mithilfe des Debuggers schnell darauf zurückzuführen war, daß die Zwischensumme der Multiplikation nicht korrekt zurückgesetzt wurde. Durch das Setzen geeigneter Breakpoints konnte der Debug--Vorgang deutlich beschleunigt werden, da somit das Programm nicht von Anfang an im Einzelschrittbetrieb durchlaufen mußte, sondern erst an der Stelle, an der der Fehler vermutet wurde vom schnellen Betrieb in den Einzelschrittberieb gewechselt werden konnte. Das fertige Programm liefert nun für Eingabewerte von $0$ bis $4$ korrekt den Wert der Fakultät der Zahl. Auf eine Überprüfung der Gültigkeit des Eingabewertes wurde verzichtet, da dies auch in der Aufgabenstellung nicht verlangt wurde und den Quelltext unnötig unübersichtlich gemacht hätte. Die Schleife zur Multiplikation ist so gewählt, daß möglichst wenige Durchläufe benötigt werden. So wird z.B. $2 \cdot 6$ als $6 + 6$ und nicht als $2+2+2+2+2+2$ berechnet. \section{Genaue Betrachtung eines Programmabschnitts} \setlength{\parindent}{0pt} Es soll dargestellt werden, wie die Multiplikation zweier Zahlen funktioniert. In diesem Beispiel werden die Zahlen $3$ und $4$ multipliziert. Die $4$ wird dreimal mit sich selbst addiert, nach der dritten Addition ist die Bedingung für den Rücksprung nicht mehr erfüllt, somit ist die Multiplikation komplett. \begin{center} \begin{tabular}{cccccl} $BZ_{alt}$ & $BR_{alt}$ & $BZ_{neu}$ & $AC_{bin}$ & $Flags_{bin}$ & Bemerkungen\\ \hline 09 & LDA 34 & \phantom{1}A & \phantom{00}11 & 0010 & Laden des ersten Faktors \\ \phantom{1}A & STA 35 & \phantom{1}B & \phantom{00}11 & 0010 & Sicherung des Faktors als Index\\ \phantom{1}B & LDA 35 & \phantom{1}C & \phantom{00}00 & 0010 & Laden von Null\\ \phantom{1}C & STA 36 & \phantom{1}D & \phantom{00}00 & 0010 & Summe auf Null setzen\\ \phantom{1}D & LDA 36 & \phantom{1}E & \phantom{00}00 & 0010 & Summe wieder Laden\\ \phantom{1}E & ADD 37 & \phantom{1}F & \phantom{0}100 & 0010 & Index zu Summe addieren\\ \phantom{1}F & STA 36 & 10 & \phantom{0}100 & 0010 & Summe sichern\\ 10 & LDA 35 & 11 & \phantom{00}11 & 0010 & Index laden\\ 11 & SUB 31 & 12 & \phantom{00}10 & 0010 & Index dekrementieren\\ 12 & STA 35 & 13 & \phantom{00}10 & 0010 & Index sichern\\ 13 & CMP 33 & 14 & \phantom{00}10 & 0010 & Prüfe Rücksprungbedingung\\ 14 & JGT 13 & \phantom{1}D & \phantom{00}10 & 0010 & Erfüllt, erneute Addition!\\ \phantom{1}D & LDA 36 & \phantom{1}E & \phantom{0}100 & 0010 & Lade Summe\\ \phantom{1}E & ADD 37 & \phantom{1}F & 1000 & 0010 & Index zu Summe addieren\\ \phantom{1}F & STA 36 & 10 & 1000 & 0010 & Summe sichern\\ 10 & LDA 35 & 11 & \phantom{00}10 & 0010 & Index laden\\ 11 & SUB 31 & 12 & \phantom{000}1 & 0010 & Index dekrementieren\\ 12 & STA 35 & 13 & \phantom{000}1 & 0010 & Index sichern\\ 13 & CMP 33 & 14 & \phantom{000}1 & 0010 & Prüfe Rücksprungbedingung\\ 14 & JGT 13 & \phantom{1}D & \phantom{00}10 & 0010 & Erfüllt, erneute Addition!\\ \phantom{1}D & LDA 36 & \phantom{1}E & 1000 & 0010 & Lade Summe\\ \phantom{1}E & ADD 37 & \phantom{1}F & 1100 & 0010 & Index zu Summe addieren\\ \phantom{1}F & STA 36 & 10 & 1100 & 0010 & Summe sichern\\ 10 & LDA 35 & 11 & \phantom{000}1 & 0010 & Index laden\\ 11 & SUB 31 & 12 & \phantom{000}0 & 0100 & Index dekrementieren\\ 12 & STA 35 & 13 & \phantom{000}0 & 0100 & Index sichern\\ 13 & CMP 33 & 14 & \phantom{000}0 & 0100 & Prüfe Rücksprungbedingung\\ 14 & JGT 13 & 15 & \phantom{000}0 & 0100 & Nicht erfüllt! Fertig!\\ 15 & LDA 36 & 16 & 1100 & 0100 & Lade Produkt in ACU \end{tabular} \end{center} \newpage \appendix \section{Quelltext} \begin{verbatim} ; Mikrorechentechnik 1-Praktikum, Gruppe 63 ; ; Versuch "Von-Neumann-Simulator" ; ############### Initialisierung, Einlesen der Zahl, Umwandlung ASCII->Dez EXT UPAUS ; Externes Label UPAUS wird vereinbart RDA ; lese Zahl (0 .. 4) deren Fakultaet gebildet werden soll SUB ANULL ; aus ASCII-Wert Dezimalzahl machen ; ############### Test auf Sonderfall (0! := 1) CMP NULL ; ueberpruefe, ob Zahl Null ist JEQ ZERO ; Falls Zahl = 0, springe zu ZERO (Sonderfall, 0! = 1) ; ############### Hier Fakultaet berechnen STA FAK ; Eingegebene Zahl in FAK sichern LOOP CMP EINS ; Akku (Zahl oder Laufindex) wird mit 1 vergleichen JEQ FERTIG ; Falls ACU=1 fertig -> Springe zum Label FERTIG SUB EINS ; (sonst) Index erniedrigen STA INDEX ; als Index sichern ; ############### Hier Multiplikation von FAK mit INDEX LDA INDEX ; Laufindex der Fakultaet (zweiter Faktor) laden (obsolet) STA INDEXM ; in INDEXM sichern, da er veraendert wird LDA NULL ; ACU auf Null setzen STA SUMME ; Summe auf Null setzen AGAIN LDA SUMME ; Zwischensumme der Multiplikation laden ADD FAK ; Fakultaets-Zwischenwert aufsummieren (FAK=erster Faktor) STA SUMME ; Zwischensumme sichern LDA INDEXM ; ehem. Laufindex der Fakultaet laden (zweiter Faktor) SUB EINS ; Laufindex dekrementieren, d.h. einmal weniger aufaddieren STA INDEXM ; neuen Index abspeichern CMP NULL ; wenn Laufindex 0, muss nicht weiter addiert werden JGT AGAIN ; wenn Laufindex > 0, muss weiter addiert werden LDA SUMME ; Fertig, SUMME in ACU laden ; ############### Hier endet die Multiplikation STA FAK ; Ergebnis der Multiplikation sichern LDA INDEX ; Laufindex in ACU JMP LOOP ; wieder zurueck zum Anfang der Fakultaetsbildung FERTIG LDA FAK ; Fakultaet fertig, Ergebnis FAK in ACU ; ############### Hier die Fakultaet fertig berechnet JMP GIBAUS ; zur Ausgabe springen ; ############### Behandlung des Sonderfalles 0! ZERO LDA EINS ; Bei 0! wird als Ergebnis 1 in den ACU geladen ; ############### Ausgabe auf den Bildschirm, Beenden des Programmes GIBAUS JSB UPAUS ; Ausgabe des ACU auf den Bildschirm durch UPAUS HLT ; Programmausfuehrung wird beendent ; ############### Initialisierungen ANULL DEC 48 ; ASCII Wert fuer die 0 EINS DEC 1 ; Wert 1 NULL DEC 0 ; Wert 0 INDEX DEC 0 ; Laufindex fuer Fakultaet INDEXM DEC 0 ; Laufindex fuer Multiplikation SUMME DEC 0 ; Zwischensumme bei Multiplikation FAK DEC 0 ; Zwischenprodukt der Fakultaet \end{verbatim} \end{document}