BuK/IIm11/BuK-KA-RAM-Programm
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=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: <tt>(Jens Heider und Daniel Tasche)</tt> ==
{|| border="1" cellpadding="5" cellspacing="0"
!Nr
!Methode
!Bemerkung
|-
||<div align="right">0</div>||R0 = 3|| R0 = n (Berechnung Wurzel von 3)
|-
||<div align="right">1</div>||R2 = 1|| R2 = fixer Wert für Inkrement/Dekrement
|-
||<div align="right">2</div>||R1 += R2|| R1 = aktuelle Testvariable
|-
||<div align="right">3</div>||R3 = R1|| R3 = dekrementierter Wert bei Multiplikation
|-
||<div align="right">4</div>||R4 = 0|| R4 = Summe bei Multiplikation
|-
||<div align="right">5</div>||IFZERO R3 GOTO 9|| Quadratzahl des aktuellen Testwerts gebildet?
|-
||<div align="right">6</div>||R4 += R1|| Aufsummierung für Multiplikation
|-
||<div align="right">7</div>||R3 -= R2|| Dekrementierung des Multiplikation-Zählers
|-
||<div align="right">8</div>||GOTO 5||
|-
||<div align="right">9</div>||R5 = R0|| Begin des Tests, ob gebildete Quadratzahl größer als n
|-
||<div align="right">10</div>||IFZERO R5 GOTO 15|| Wenn n kleiner gleich gebildete Quadratzahl
|-
||<div align="right">11</div>||IFZERO R4 GOTO 2|| gebildete Quadratzahl noch nicht groß genug. Mit nächsten Testkandidaten fortfahren
|-
||<div align="right">12</div>||R4 -= R2|| gebildete Quadratzahl dekrementieren
|-
||<div align="right">13</div>||R5 -= R2|| n dekrementieren
|-
||<div align="right">14</div>||GOTO 10||
|-
||<div align="right">15</div>||IFZERO R4 GOTO 17|| Ist gebildete Quadratzahl = n, dann Ergebnis direkt erreicht.
|-
||<div align="right">16</div>||R1 -= R2|| Ansonsten muss gebildete Quadratzahl "abgerundet" werden
|-
||<div align="right">17</div>||R0 = R1|| Ergebnis in Rückgaberegister schreiben.
|}
'''Test mit 4:'''
[[Bild:Sijeheid_RAM_Wurzel_4.jpg]]
'''Test mit 5:'''
[[Bild:Sijeheid_RAM_Wurzel_5.jpg]]
== RAM-Programm <tt>(Stefan Scheumann)</tt>==
{|| border="1" cellpadding="5" cellspacing="0"
!BNr
!Methode
!Bemerkung
|-
||<div align="right">0</div>||R0 = 25||Berechnung Wurzel 25
|-
||<div align="right">1</div>||R1 = 1||R1 = aktueller Testwert
|-
||<div align="right">2</div>||R2 = 0||R2 = alter Testwert
|-
||<div align="right">3</div>||R5 = 1||Inkrement-Variable
|-
||<div align="right">4</div>||R10 = R1||Parameter für die Berechnung des Quadrats; Beginne Quadrierung
|-
||<div align="right">5</div>||R11=R10||Schleifenindex
|-
||<div align="right">6</div>||IFZERO R10 GOTO 10||
|-
||<div align="right">7</div>||R12 += R10||
|-
||<div align="right">8</div>||R11 -= R5||
|-
||<div align="right">9</div>||GOTO 4||
|-
||<div align="right">10</div>||R3 = R12||R3 = Quadrat von aktuellen Testwert; Ende Quadrierung
|-
||<div align="right">11</div>||R20 =R0||Vorbereitung Vergleich(Kopieren der Register) von gesuchten Wert mit Ergebnis der Quadrierung
|-
||<div align="right">12</div>||R21 = R3||
|-
||<div align="right">13</div>||R20 -= R5||Beginn Vergleich errechneten Wert <= gegebenen Wert; Aufbau: beide Variablen dekrementieren bis eine oder beide 0 sind.
|-
||<div align="right">14</div>||R21 -= R5||
|-
||<div align="right">15</div>||IFZERO R20 GOTO 21||R20(Gesuchter Wert) kleiner oder gleich R21(berechnetes Quadrat des aktuellen Testwertes)
|-
||<div align="right">16</div>||IFZERO R21 GOTO 18||R21 kleiner R20 => weitermachen mit neuen Testwerten
|-
||<div align="right">17</div>||GOTO 13||Wiederholen bis R20 oder R21 = 0
|-
||<div align="right">18</div>||R2 = R1||alter Testwert = aktueller Testwert
|-
||<div align="right">19</div>||R1 += R2||aktueller Testwert + 1
|-
||<div align="right">20</div>||GOTO 4|| Mit neuen Testwert von vorn anfangen.
|-
||<div align="right">21</div>||R0 = R2|| Ergebnis in Rückgaberegister schreiben.
|}
<language>Scheme</language>
== RAM-Programm: <tt>(Robert Rosenberger)</tt> ==
{|| border="1" cellpadding="5" cellspacing="0"
|-
|| 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: <tt>(Tobias Salzmann und Ronald Krause)</tt> ==
* 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$
<code>
introot(n):=
Module({x = n, y = 1},
WHILE( x > y)
x = Quotient(x + y, 2);
y = Quotient(n, x);
return x;
)
</code>
<br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">1</div>||R0 = n||
|-
||<div align="right">2</div>||R1 = RO||X
|-
||<div align="right">3</div>||R2 = 1||Y
|-
||<div align="right">4</div>||R20 = R1||
|-
||<div align="right">5</div>||R21 = R2||
|-
||<div align="right">6</div>||GOTO 36|| Größer/KleinerVergleich
|-
||<div align="right">7</div>||IFZERO R23 GOTO 9||
|-
||<div align="right">8</div>||STOP||Ergebnis x in R1
|-
||<div align="right">9</div>||R3 = 0||
|-
||<div align="right">10</div>||R3 += R1|| 0 + x
|-
||<div align="right">11</div>||R3 += R2|| x + y
|-
||<div align="right">12</div>||R4 = 2||
|-
||<div align="right">13</div>||R10 = 0|| Wert zur Überprüfen des Rücksprunges
|-
||<div align="right">14</div>||GOTO 22|| Division
|-
||<div align="right">15</div>||R1 = R5|| neues x in R1
|-
||<div align="right">16</div>||R3 = R0|| n in R3
|-
||<div align="right">17</div>||R4 = R1|| x in R4
|-
||<div align="right">18</div>||R10 = 1|| Wert zur Überprüfung des Rücksprunges
|-
||<div align="right">19</div>||GOTO 22|| Division
|-
||<div align="right">20</div>||R2 = R5|| neues y in R2
|-
||<div align="right">21</div>||GOTO 36|| Größer/Kleinervergleich
|}
<br/>
=== Ganzzahlige Division ===
<code id="4fbbd6b37d2ca">
q = 0;
r = a;
while (r>=b)
{
q = q+1; //Ganzzahliger Wert
r = r-b; //Ganzzahliger Rest
}
</code><br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">22</div>||R9 = 1||
|-
||<div align="right">23</div>||R5 = 0||
|-
||<div align="right">24</div>||R6 = R3|| Zähler für 1.Zahl
|-
||<div align="right">25</div>||R7 = R4|| Zähler für 2.Zahl
|-
||<div align="right">26</div>||IFZERO R7 GOTO 31||
|-
||<div align="right">27</div>||R7 -= R9|| subtrahieren
|-
||<div align="right">28</div>||IFZERO R6 GOTO 34||
|-
||<div align="right">29</div>||R6 -= R9|| subtrahieren
|-
||<div align="right">30</div>||GOTO 26||
|-
||<div align="right">31</div>||R5 += R9|| addieren
|-
||<div align="right">32</div>||R6 -= R7||
|-
||<div align="right">33</div>||GOTO 24||
|-
||<div align="right">34</div>||IFZERO R10 GOTO 15||
|-
||<div align="right">35</div>||GOTO 20||
|}
<br/>
=== Größer/Kleinervergleich ===
<br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">36</div>||IFZERO R20 GOTO 41|| x
|-
||<div align="right">37</div>||R20 -= R9||
|-
||<div align="right">38</div>||IFZERO R21 GOTO 42|| y
|-
||<div align="right">39</div>||R21 -= R9||
|-
||<div align="right">40</div>||GOTO 36||
|-
||<div align="right">41</div>||R23 = 1||
|-
||<div align="right">42</div>||GOTO 7|| Wenn R23 = 1; dann ist x <= y und wenn R23 = 0, dann x > y
|}