Aus ProgrammingWiki

Inhaltsverzeichnis 1 Registermaschine 1.1 RAM-Programm: (Jens Heider und Daniel Tasche) 1.2 RAM-Programm (Stefan Scheumann) 1.3 RAM-Programm: (Robert Rosenberger) 1.4 RAM-Programm: (Tobias Salzmann und Ronald Krause) 1.4.1 Ganzzahlige Division 1.4.2 Größer/Kleinervergleich

Registermaschine

Geben Sie mind. ein RAM-Programm zur Berechnung der Funktion $w : \N \mapsto \N$ mit $w(n) = \left\lfloor \sqrt{n} \right\rfloor$ an.

RAM-Programm: (Jens Heider und Daniel Tasche)

Nr	Methode	Bemerkung
0	R0 = 3	R0 = n (Berechnung Wurzel von 3)
1	R2 = 1	R2 = fixer Wert für Inkrement/Dekrement
2	R1 += R2	R1 = aktuelle Testvariable
3	R3 = R1	R3 = dekrementierter Wert bei Multiplikation
4	R4 = 0	R4 = Summe bei Multiplikation
5	IFZERO R3 GOTO 9	Quadratzahl des aktuellen Testwerts gebildet?
6	R4 += R1	Aufsummierung für Multiplikation
7	R3 -= R2	Dekrementierung des Multiplikation-Zählers
8	GOTO 5
9	R5 = R0	Begin des Tests, ob gebildete Quadratzahl größer als n
10	IFZERO R5 GOTO 15	Wenn n kleiner gleich gebildete Quadratzahl
11	IFZERO R4 GOTO 2	gebildete Quadratzahl noch nicht groß genug. Mit nächsten Testkandidaten fortfahren
12	R4 -= R2	gebildete Quadratzahl dekrementieren
13	R5 -= R2	n dekrementieren
14	GOTO 10
15	IFZERO R4 GOTO 17	Ist gebildete Quadratzahl = n, dann Ergebnis direkt erreicht.
16	R1 -= R2	Ansonsten muss gebildete Quadratzahl "abgerundet" werden
17	R0 = R1	Ergebnis in Rückgaberegister schreiben.

Test mit 4:

Test mit 5:

RAM-Programm (Stefan Scheumann)

BNr	Methode	Bemerkung
0	R0 = 25	Berechnung Wurzel 25
1	R1 = 1	R1 = aktueller Testwert
2	R2 = 0	R2 = alter Testwert
3	R5 = 1	Inkrement-Variable
4	R10 = R1	Parameter für die Berechnung des Quadrats; Beginne Quadrierung
5	R11=R10	Schleifenindex
6	IFZERO R10 GOTO 10
7	R12 += R10
8	R11 -= R5
9	GOTO 4
10	R3 = R12	R3 = Quadrat von aktuellen Testwert; Ende Quadrierung
11	R20 =R0	Vorbereitung Vergleich(Kopieren der Register) von gesuchten Wert mit Ergebnis der Quadrierung
12	R21 = R3
13	R20 -= R5	Beginn Vergleich errechneten Wert <= gegebenen Wert; Aufbau: beide Variablen dekrementieren bis eine oder beide 0 sind.
14	R21 -= R5
15	IFZERO R20 GOTO 21	R20(Gesuchter Wert) kleiner oder gleich R21(berechnetes Quadrat des aktuellen Testwertes)
16	IFZERO R21 GOTO 18	R21 kleiner R20 => weitermachen mit neuen Testwerten
17	GOTO 13	Wiederholen bis R20 oder R21 = 0
18	R2 = R1	alter Testwert = aktueller Testwert
19	R1 += R2	aktueller Testwert + 1
20	GOTO 4	Mit neuen Testwert von vorn anfangen.
21	R0 = R2	Ergebnis in Rückgaberegister schreiben.

RAM-Programm: (Robert Rosenberger)

1	R0 = 25
2	R3 = 1
3	R1 += R3
4	R5 = R1
5	R5 -= R3
6	R6 = R1
7	FZERO R5 GOTO 11
8	R5 -= R3
9	R6 += R1
10	GOTO 7
11	R10 = R0
12	R10 -= R6
13	IFZERO R10 GOTO 15
14	GOTO 3
15	R15 = R6
16	R16 = R0
17	IF ZERO R16 GOTO 21
18	R16 -= R3
19	R15 -= R3
20	GOTO 17
21	IFZERO R15 GOTO 23
22	R1 -= R3
23	R0 = R1
24	STOP

RAM-Programm: (Tobias Salzmann und Ronald Krause)

• Heron-Algorithmus

Ausgehend von $x=n$ und $y=1$ wiederholt man $x=\left\lbrack \frac{x+y}{2}\right\rbrack$ und $y=\left\lbrack \frac{a}{x}\right\rbrack$ solange wie $x>y$ ist.

Ist nach Austritt aus dieser Schleife $x\leq y$, so gilt $x=\left\lbrack \sqrt{n} \right\rbrack$

introot(n):= Module({x = n, y = 1}, WHILE( x > y) x = Quotient(x + y, 2); y = Quotient(n, x); return x; )

Befehlszähler	Befehl	Bemerkung
1	R0 = n
2	R1 = RO	X
3	R2 = 1	Y
4	R20 = R1
5	R21 = R2
6	GOTO 36	Größer/KleinerVergleich
7	IFZERO R23 GOTO 9
8	STOP	Ergebnis x in R1
9	R3 = 0
10	R3 += R1	0 + x
11	R3 += R2	x + y
12	R4 = 2
13	R10 = 0	Wert zur Überprüfen des Rücksprunges
14	GOTO 22	Division
15	R1 = R5	neues x in R1
16	R3 = R0	n in R3
17	R4 = R1	x in R4
18	R10 = 1	Wert zur Überprüfung des Rücksprunges
19	GOTO 22	Division
20	R2 = R5	neues y in R2
21	GOTO 36	Größer/Kleinervergleich

Ganzzahlige Division

q = 0; r = a; while (r>=b) { q = q+1; //Ganzzahliger Wert r = r-b; //Ganzzahliger Rest }

Befehlszähler	Befehl	Bemerkung
22	R9 = 1
23	R5 = 0
24	R6 = R3	Zähler für 1.Zahl
25	R7 = R4	Zähler für 2.Zahl
26	IFZERO R7 GOTO 31
27	R7 -= R9	subtrahieren
28	IFZERO R6 GOTO 34
29	R6 -= R9	subtrahieren
30	GOTO 26
31	R5 += R9	addieren
32	R6 -= R7
33	GOTO 24
34	IFZERO R10 GOTO 15
35	GOTO 20

Größer/Kleinervergleich

Befehlszähler	Befehl	Bemerkung
36	IFZERO R20 GOTO 41	x
37	R20 -= R9
38	IFZERO R21 GOTO 42	y
39	R21 -= R9
40	GOTO 36
41	R23 = 1
42	GOTO 7	Wenn R23 = 1; dann ist x <= y und wenn R23 = 0, dann x > y