Informatiker Board | Theoretische Informatik | Anweisung auf eine Stackmaschine implementieren

Informatiker Board » Themengebiete » Theoretische Informatik » Anweisung auf eine Stackmaschine implementieren

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Anweisung auf eine Stackmaschine implementieren

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Anweisung auf eine Stackmaschine implementieren

Zitatantwort auf diesen Beitrag erstellen

Hallo

Zitat:

Implementieren Sie die Anweisung e = (a + b)(c + (a + b) d) auf einer Stackmaschine.

Sie haben die Befehle push (3 Taktzyklen), pop (3), add (1), mult (5) zur Verfügung.
Sie haben zusätzlich den Befehl dup (1 Taktzyklus) zur Verfügung, der das oberste Stackelement dupliziert. Die Addition ist kommutativ (a + b = b + a).

Zählen Sie für beide Fälle die Anzahl der Befehle, die Anzahl der Speicherzugriffe (mit und ohne dem Einlesen der Befehlscodes) und
die Anzahl der Taktzyklen, die das Programm benötigt.

Ermitteln Sie auch, wie viele Bytes im Programmablauf zwischen Speicher und CPU transferiert werden, wenn ein Operationscode 1 Byte lang ist, Speicheradressen 2 Bytes und Operanden 4 Bytes. a, b, c und d stehen von Beginn an im Speicher.

Also als erstes würde ich die Anweisung (a + b)(c + (a + b) d) in die "polnische"-Notation bringen,
also ab + d * c + ab + * (ich hoffe das stimmt so), und dann die Befehle ausführen, also:

PUSH a
PUSH b
ADD
PUSH d
MULT
PUSH c
ADD
PUSH a
PUSH b
ADD
MULT
POP

Okay, also funktioniert das so oder muss ich das mehr aufteilen?

BLAU a) wäre dann also 12.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 03.01.2016 13:32.

03.01.2016 13:32

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Passt fürs erste, in der b) wird optimiert.

__________________
Syntax Highlighting fürs Board (Link)

03.01.2016 14:06

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Okay super, danke.

Zitat:

Zählen Sie die Anzahl der Taktzyklen, die das Programm benötigt

Bei a) wäre dann für jedes Push 3, kommen sonst auch noch Taktzyklen vor?
Also 18 mMn.

Zitat:

Zählen Sie die Anzahl der Speicherzugriffe (mit und ohne dem Einlesen der Befehlscodes

Was wir denn alles unter einem Speicherzugriff verstanden? Sind das nicht nur die Push und Pop Befehle? Und die Befehlscodes sind die OP-Codes (also die, die in der Klammer danach stehen oder?).

03.01.2016 14:35

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Du hast noch 2 MULT, 3 ADD und ein POP, also 18+2*5+3*1+1*3 = 34

Irgendwo muss ja auch die Informatin kommen, dass etwas addiert oder multipliziert werden soll. Ich denke du sollst hier für jeden Befehl ein pop rechnen, also 34+12*3 = 70

__________________
Syntax Highlighting fürs Board (Link)

03.01.2016 14:42

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Zitat:

Ermitteln Sie auch, wie viele Bytes im Programmablauf zwischen Speicher und CPU transferiert werden, wenn ein Operationscode 1 Byte lang ist, Speicheradressen 2 Bytes und Operanden 4 Bytes. a, b, c und d stehen von Beginn an im Speicher.

12*1Byte (alle Codes) + 6*2Bytes (alle PUSH) + 5*4Bytes(alle ADD und MULT) = 44 Bytes ????

03.01.2016 15:06

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Zitat:

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Das musst du mir jetzt erklären.
Ich komme wir oben ausgerechnet auf 34 da waren deine ursprünglichen 6 pop ja schon mit dabei.

Beim letzten Teil denke ich, dass die Variablen noch vom Speicher in den Prozessor geladen werden müssen. Aber an der Stelle bin ich auch keine verlässliche Quelle.

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 03.01.2016 15:23.

03.01.2016 15:22

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Zitat:

Original von eulerscheZahl

Zitat:

Ah okay und ohne Einlesen der Befehlscodes wäre es dann 34+7*3 = 55 ? Oder 18+12*3 = 54 ?

Das musst du mir jetzt erklären.
Ich komme wir oben ausgerechnet auf 34 da waren deine ursprünglichen 6 pop ja schon mit dabei.

Laut Angabe gibt es die Anzahl der Speicherzugriffe mit und ohne dem Einlesen der Befehlscodes.

Mit wären ja: 34+12*3 = 70
Und bei ohne dachte ich mir ohne den (3 ADD und 2 MULT)-POPs, also 34+7*3 = 55

Dann noch zu b)
Würde das dann in etwa so aussehen?

PUSH a
PUSH b
ADD
DUP
PUSH d
MULT
PUSH c
ADD
MULT
POP

03.01.2016 22:51

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Kosten für Befehl selbst und Befehlscode ohne Gewähr:
PUSH a 3 3
PUSH b 3 3
ADD 1 3
PUSH d 3 3
MULT 5 3
PUSH c 3 3
ADD 1 3
PUSH a 3 3
PUSH b 3 3
ADD 1 3
MULT 5 3
POP 3 3
gesamt: 34 36
Also 34 für die Befehle alleine. 34+36=70, wenn du den Code noch laden musst.

Die b) passt so.

__________________
Syntax Highlighting fürs Board (Link)

04.01.2016 07:53

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Hmm okay, aber dann wäre

Zitat:

Zählen Sie die Anzahl der Taktzyklen, die das Programm benötigt

dasselbe wie die Anzahl der Speicherzugriffe ohne dem Einlesen der Befehlscodes.

04.01.2016 10:48

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ich habe die ganze Zeit von den Taktzyklen gesprochen.

Das einzige, was ich zum Speicherzugriff geschrieben habe:

Zitat:

Original von Shizrmo
12*1Byte (alle Codes) + 6*2Bytes (alle PUSH) + 5*4Bytes(alle ADD und MULT) = 44 Bytes ????

Zitat:

Original von eulerscheZahl
Beim letzten Teil denke ich, dass die Variablen noch vom Speicher in den Prozessor geladen werden müssen. Aber an der Stelle bin ich auch keine verlässliche Quelle.

__________________
Syntax Highlighting fürs Board (Link)

04.01.2016 10:56

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Ich hätte hier noch ein Beispiel, wo ich mir nicht ganz sicher bin, die Angabe:

Zitat:

Implementieren Sie folgende Anweisung auf einer Stackmaschine:
$[latex]c=\frac{a}{b+\frac{a}{b+\frac{a}{b+a} } } [/latex]$

a) Sie haben die Befehle push, pop, add, div zur Verfügung.
b) Sie haben zusätzlich den Befehl dup zur Verfügung.

Also eh wieder sehr ähnlich:

Also erst einmal ordentlich hinschreiben: [latex]a/(b+a/(b+a/(b+a)))[/latex]

Dann polnische Notation: [latex]ab+a/b+a/b+a/[/latex]

Wenn das soweit passt ist a):
PUSH A
PUSH B
ADD
PUSH A
DIV
PUSH B
ADD
PUSH A
DIV
PUSH B
ADD
PUSH A
DIV
POP C

bei b) bin ich mir allerdings nicht ganz sicher:
PUSH A
PUSH B
ADD
PUSH A
DIV
DUP
PUSH B
ADD
DIV
POP C

Denn wenn ich das jetzt wieder auflöse, wäre das: [latex](((a+b)/a)+b) / (a+b)/a[/latex]

Wenn ich von rechts nach links gehe teile ich [latex]a[/latex]

durch

was ja eigentlich nicht richtig ist.

Wo liegt mein Fehler? Zunge raus

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 23.01.2016 10:05.

23.01.2016 02:04

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Du hast in der polnischen Notation ein fünftes a dazubekommen. Nimm das mal wieder weg.

__________________
Syntax Highlighting fürs Board (Link)

23.01.2016 06:58

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Hoppala, war ein Fehler beim Abtippen:

[latex]ab+a/b+a/b+a/[/latex]

23.01.2016 10:06

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ich komme bei deiner Rechnung auf $[latex]\frac{b+a/(a+b)}{a/(a+b)}[/latex]$ .
a/(b+a) zu kopieren macht denke ich keinen Sinn, weil man es nur einmal verwenden kann.
Ich würde erst mal schauen, dass ich die Doppelbrüche wegbekomme: $[latex]c=\frac{{\left({\left(a + b\right)} b + a\right)} a}{{\left(a + b\right)} a + {\left({\left(a + b\right)} b + a\right)} b}[/latex]$ .
Dadurch wird die Rechnung aber eher länger als kürzer verwirrt

__________________
Syntax Highlighting fürs Board (Link)

23.01.2016 10:36

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Hmmm, eigenartig. Aber die a) passt soweit?

23.01.2016 10:48

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Anweisung auf eine Stackmaschine implementieren