IIm18-Kreativaufgabe7

Wiki-Quelltext dieser Seite.

= Random Access Maschine  -  <tt>Paul Bachmann, Johannes Thies</tt> =

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 ==

{|| border="1" cellpadding="5" cellspacing="0"
|- style="text-align: center;background-color:lightgreen;"
!Befehlszähler
!Anweisung
!Bemerkung

|-
||<div align="right">0</div>||xxx|| xxx
|-style="background-color:lightgrey;"
||<div align="right">1</div>||xxx|| xxx
|-
||<div align="right">2</div>||xxx|| xxx
|}




== RAM zur Ermittlung des größten gemeinsamen Teilers (ggt) - Euklidischer Algorithmus ==

{|| border="1" cellpadding="5" cellspacing="0"
|- style="text-align: center;background-color:lightgreen;"
!Befehlszähler
!Anweisung
!Bemerkung
|-
||<div align="right">0</div>||R0 = a|| belegen von R0 mit der ersten natürlichen Zahl a 
|-style="background-color:lightgrey;"
||<div align="right">1</div>||R1 = b|| belegen von R1 mit der ersten natürlichen Zahl b 
|-
||<div align="right">2</div>||IFZERO R1 GOTO 12|| Sprung zu 12 da R0 das Ergebnis beinhaltet 
|-style="background-color:lightgrey;"
||<div align="right">3</div>||IFZERO R0 GOTO 11|| Sprung zu 11 da R1 das Ergebnis beinhaltet 
|-
||<div align="right">4</div>||R2 = R0|| Zwischenspeichern von R0 in R2 für Größer vergleich
|-style="background-color:lightgrey;"
||<div align="right">5</div>||R2 -= R1|| R1 von R2 subtrahieren für Größer vergleich
|-
||<div align="right">6</div>||IFZERO R2 GOTO 9|| wenn R2 0 ist, ist R1 > R0
|-style="background-color:lightgrey;"
||<div align="right">7</div>||R0 -= R1|| R1 von R0 subtrahieren
|-
||<div align="right">8</div>||GOTO 2|| Sprung zum Schleifenanfang
|-style="background-color:lightgrey;"
||<div align="right">9</div>||R1 -= R0|| R0 von R1 subtrahieren
|-
||<div align="right">10</div>||GOTO 2|| Sprung zum Schleifenanfang
|-style="background-color:lightgrey;"
||<div align="right">11</div>||R0 = R1|| Ergebnis in R0 schreiben
|-
||<div align="right">12</div>||STOP||
|}




=== Beispiel mit a = 2 und b = 4 ===
{|| border="1" cellpadding="5" cellspacing="0"
|- style="text-align: center;background-color:lightgreen;"
!Anweisung
!R0
!R1
!R1
|-
||R0 = a ||2||0||0
|-style="background-color:lightgrey;"
||R1 = b ||2||4||0
|-
||IFZERO R1 GOTO 12 ||2||4||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||2||4||0
|-
||R2 = R0 ||2||4||2
|-style="background-color:lightgrey;"
||R2 -= R1 ||2||4||0
|-
||IFZERO R2 GOTO 11 ||2||4||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||2||2||0
|-
||GOTO 2 ||2||2||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||2||2||0
|-
||IFZERO R0 GOTO 11||2||2||0
|-style="background-color:lightgrey;"
||R2 = R0 ||2||2||2
|-
||R2 -= R1 ||2||2||0
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||2||2||0
|-
||R1 -= R0 ||2||0||0
|-style="background-color:lightgrey;"
||GOTO 2 ||2||0||0
|-
||IFZERO R1 GOTO 12 ||2||0||0
|-style="background-color:lightgrey;"
|}




=== Beispiel mit a = 2 und b = 15 ===
{|| border="1" cellpadding="5" cellspacing="0"
|- style="text-align: center;background-color:lightgreen;"
!Anweisung
!R0
!R1
!R1
|-
||R0 = a ||2||0||0
|-style="background-color:lightgrey;"
||R1 = b ||2||15||0
|-
||IFZERO R1 GOTO 12 ||2||15||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||2||15||0
|-
||R2 = R0 ||2||15||2
|-style="background-color:lightgrey;"
||R2 -= R1 ||2||15||0
|-
||IFZERO R2 GOTO 11 ||2||15||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||2||13||0
|-
||GOTO 2 ||2||13||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||2||13||0
|-
||IFZERO R0 GOTO 11||2||13||0
|-style="background-color:lightgrey;"
||R2 = R0 ||2||13||2
|-
||R2 -= R1 ||2||13||0
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||2||13||0
|-
||R1 -= R0 ||2||11||0
|-style="background-color:lightgrey;"
||GOTO 2 ||2||11||0
|-
||IFZERO R1 GOTO 12 ||2||11||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||2||11||0
|-
||R2 = R0 ||2||11||2
|-style="background-color:lightgrey;"
||R2 -= R1 ||2||11||0
|-
||IFZERO R2 GOTO 11 ||2||11||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||2||9||0
|-
||GOTO 2 ||2||9||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||2||9||0
|-
||IFZERO R0 GOTO 11||2||9||0
|-style="background-color:lightgrey;"
||R2 = R0 ||2||9||2
|-
||R2 -= R1 ||2||9||0
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||2||9||0
|-
||R1 -= R0 ||2||7||0
|-style="background-color:lightgrey;"
||GOTO 2 ||2||7||0
|-
||IFZERO R1 GOTO 12 ||2||7||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||2||7||0
|-
||R2 = R0 ||2||7||2
|-style="background-color:lightgrey;"
||R2 -= R1 ||2||7||0
|-
||IFZERO R2 GOTO 11 ||2||7||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||2||5||0
|-
||GOTO 2 ||2||5||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||2||5||0
|-
||IFZERO R0 GOTO 11||2||5||0
|-style="background-color:lightgrey;"
||R2 = R0 ||2||5||2
|-
||R2 -= R1 ||2||5||0
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||2||5||0
|-
||R1 -= R0 ||2||3||0
|-style="background-color:lightgrey;"
||GOTO 2 ||2||3||0
|-
||IFZERO R1 GOTO 12 ||2||3||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||2||3||0
|-
||R2 = R0 ||2||3||2
|-style="background-color:lightgrey;"
||R2 -= R1 ||2||3||0
|-
||IFZERO R2 GOTO 11 ||2||3||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||2||1||0
|-
||GOTO 2 ||2||1||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||2||1||0
|-
||IFZERO R0 GOTO 11||2||1||0
|-style="background-color:lightgrey;"
||R2 = R0 ||2||1||2
|-
||R2 -= R1 ||2||1||1
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||2||1||1
|-
||R0 -= R1 ||1||1||1
|-style="background-color:lightgrey;"
||GOTO 2 ||1||1||1
|-
||IFZERO R1 GOTO 12 ||1||1||1
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||1||1||1
|-
||R2 = R0 ||1||1||1
|-style="background-color:lightgrey;"
||R2 -= R1 ||1||1||0
|-
||IFZERO R2 GOTO 11 ||1||1||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||1||0||0
|-
||GOTO 2 ||1||0||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||1||0||0
|-
|}




=== Beispiel mit a = 119 und b = 7 ===
{|| border="1" cellpadding="5" cellspacing="0"
|- style="text-align: center;background-color:lightgreen;"
!Anweisung
!R0
!R1
!R1
|-
||R0 = a ||119||0||0
|-style="background-color:lightgrey;"
||R1 = b ||119||7||0
|-
||IFZERO R1 GOTO 12 ||119||7||0
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||119||7||0
|-
||R2 = R0 ||119||7||119
|-style="background-color:lightgrey;"
||R2 -= R1 ||119||7||112
|-
||IFZERO R2 GOTO 11 ||119||7||112
|-style="background-color:lightgrey;"
||R0 -= R1 ||112||7||112
|-
||GOTO 2 ||112||7||112
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||112||7||112
|-
||IFZERO R0 GOTO 11||112||7||112
|-style="background-color:lightgrey;"
||R2 = R0 ||112||7||112
|-
||R2 -= R1 ||112||7||105
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||112||7||105
|-
||R0 -= R1 ||105||7||105
|-style="background-color:lightgrey;"
||GOTO 2 ||105||7||105
|-
||IFZERO R1 GOTO 12 ||105||7||105
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||105||7||105
|-
||R2 = R0 ||105||7||105
|-style="background-color:lightgrey;"
||R2 -= R1 ||105||7||98
|-
||IFZERO R2 GOTO 11 ||105||7||98
|-style="background-color:lightgrey;"
||R0 -= R1 ||98||7||98
|-
||GOTO 2 ||98||7||98
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||98||7||98
|-
||IFZERO R0 GOTO 11||98||7||98
|-style="background-color:lightgrey;"
||R2 = R0 ||98||7||98
|-
||R2 -= R1 ||98||7||91
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||98||7||91
|-
||R0 -= R1 ||91||7||91
|-style="background-color:lightgrey;"
||GOTO 2 ||91||7||91
|-
||IFZERO R1 GOTO 12 ||91||7||91
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||91||7||91
|-
||R2 = R0 ||91||7||91
|-style="background-color:lightgrey;"
||R2 -= R1 ||91||7||84
|-
||IFZERO R2 GOTO 11 ||91||7||84
|-style="background-color:lightgrey;"
||R0 -= R1 ||84||7||84
|-
||GOTO 2 ||84||7||84
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||84||7||84
|-
||IFZERO R0 GOTO 11||84||7||84
|-style="background-color:lightgrey;"
||R2 = R0 ||84||7||84
|-
||R2 -= R1 ||84||7||77
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||84||7||77
|-
||R0 -= R1 ||77||7||77
|-style="background-color:lightgrey;"
||GOTO 2 ||77||7||77
|-
||IFZERO R1 GOTO 12 ||77||7||77
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||77||7||77
|-
||R2 = R0 ||77||7||77
|-style="background-color:lightgrey;"
||R2 -= R1 ||77||7||70
|-
||IFZERO R2 GOTO 11 ||77||7||70
|-style="background-color:lightgrey;"
||R0 -= R1 ||70||7||70
|-
||GOTO 2 ||70||7||70
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||70||7||70
|-
||IFZERO R0 GOTO 11||70||7||70
|-style="background-color:lightgrey;"
||R2 = R0 ||70||7||70
|-
||R2 -= R1 ||70||7||63
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||70||7||63
|-
||R0 -= R1 ||63||7||63
|-style="background-color:lightgrey;"
||GOTO 2 ||63||7||63
|-
||IFZERO R1 GOTO 12 ||63||7||63
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||63||7||63
|-
||R2 = R0 ||63||7||63
|-style="background-color:lightgrey;"
||R2 -= R1 ||63||7||56
|-
||IFZERO R2 GOTO 11 ||63||7||56
|-style="background-color:lightgrey;"
||R0 -= R1 ||56||7||56
|-
||GOTO 2 ||56||7||56
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||56||7||56
|-
||IFZERO R0 GOTO 11||56||7||56
|-style="background-color:lightgrey;"
||R2 = R0 ||56||7||56
|-
||R2 -= R1 ||56||7||49
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||56||7||49
|-
||R0 -= R1 ||49||7||49
|-style="background-color:lightgrey;"
||GOTO 2 ||49||7||49
|-
||IFZERO R1 GOTO 12 ||49||7||49
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||49||7||49
|-
||R2 = R0 ||49||7||49
|-style="background-color:lightgrey;"
||R2 -= R1 ||49||7||42
|-
||IFZERO R2 GOTO 11 ||49||7||42
|-style="background-color:lightgrey;"
||R0 -= R1 ||42||7||42
|-
||GOTO 2 ||42||7||42
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||42||7||42
|-
||IFZERO R0 GOTO 11||42||7||42
|-style="background-color:lightgrey;"
||R2 = R0 ||42||7||42
|-
||R2 -= R1 ||42||7||35
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||42||7||35
|-
||R0 -= R1 ||35||7||35
|-style="background-color:lightgrey;"
||GOTO 2 ||35||7||35
|-
||IFZERO R1 GOTO 12 ||35||7||35
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||35||7||35
|-
||R2 = R0 ||35||7||35
|-style="background-color:lightgrey;"
||R2 -= R1 ||35||7||28
|-
||IFZERO R2 GOTO 11 ||35||7||28
|-style="background-color:lightgrey;"
||R0 -= R1 ||28||7||28
|-
||GOTO 2 ||28||7||28
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||28||7||28
|-
||IFZERO R0 GOTO 11||28||7||28
|-style="background-color:lightgrey;"
||R2 = R0 ||28||7||28
|-
||R2 -= R1 ||28||7||21
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||28||7||21
|-
||R0 -= R1 ||21||7||21
|-style="background-color:lightgrey;"
||GOTO 2 ||21||7||21
|-
||IFZERO R1 GOTO 12 ||21||7||21
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||21||7||21
|-
||R2 = R0 ||21||7||21
|-style="background-color:lightgrey;"
||R2 -= R1 ||21||7||14
|-
||IFZERO R2 GOTO 11 ||21||7||14
|-style="background-color:lightgrey;"
||R0 -= R1 ||14||7||14
|-
||GOTO 2 ||14||7||14
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||14||7||14
|-
||IFZERO R0 GOTO 11||14||7||14
|-style="background-color:lightgrey;"
||R2 = R0 ||14||7||14
|-
||R2 -= R1 ||14||7||7
|-style="background-color:lightgrey;"
||IFZERO R2 GOTO 11 ||14||7||7
|-
||R0 -= R1 ||7||7||7
|-style="background-color:lightgrey;"
||GOTO 2 ||7||7||7
|-
||IFZERO R1 GOTO 12 ||7||7||7
|-style="background-color:lightgrey;"
||IFZERO R0 GOTO 11||7||7||7
|-
||R2 = R0 ||7||7||7
|-style="background-color:lightgrey;"
||R2 -= R1 ||7||7||0
|-
||IFZERO R2 GOTO 11 ||7||7||0
|-style="background-color:lightgrey;"
||R1 -= R0 ||7||0||0
|-
||GOTO 2 ||7||0||0
|-style="background-color:lightgrey;"
||IFZERO R1 GOTO 12 ||7||0||0
|-
|}

== RAM zur Ermittlung von $\left\lfloor \sqrt{n} \right\rfloor$==

=== Ermittlung der Potenz ===

=== Realisierung des logischen Operators $\leq$ ===