BuK-KA-RAM-Programm

Aus ProgrammingWiki

Inhaltsverzeichnis

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

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:

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.

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

q = 0;
r = a;

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

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