hi kann mir wer bei der implementierung der fibonaccifolge in assembler helfen :
die folge ist wie folgt definiert :
für n=0 f(n)=0, für n=1 f(n)=1
für n>=2 : f = f(n-1)+f(n+2)
krieg dass einfach nicht gebacken, bin für jeden lösungsvorschlag sehr dankbar
mfg hategrown
Borlander 
hategrown „fibonaccifolge in mips assembler“
Welche Fibonacci-Zahlen brauchst Du denn?
Beliebige (also die n.te-Fibonacci-Zahl bei gegebenem n bestimmen)?
Den Nachfolger von 2 vorhandenen Folgengliedern?
krieg dass einfach nicht gebacken
Wo hängst Du denn, bzw. wo hast Du da konkrete Probleme?
bin für jeden lösungsvorschlag sehr dankbar
Hast Du zufällig eine Kurzreferenz für MIPS-ASM zur Hand? Bin mit ASM auf MIPS nicht vertraut...
Gruß
Borlander
Borlander hategrown „fibonaccifolge in mips assembler“
Du hast in Deiner Def übrigens einen Fehler drin...
f(n):=f(n-1)+f(n-2) , für alle n>=2
mr.escape hategrown „fibonaccifolge in mips assembler“
Vielleicht so?
#start
#$a0 = n
#rückgabe in $v0
#zerstört inhalt von $t0, $t1, $t2 und u.u. $a0
fib_start:
beq $a0, $zero, offset_a0 #für n=0 gebe n zurück
addi $t0, $a0, -1
beq $t0, $zero, offset_a0 #für n=1 gebe n zurück
addi $a0, $a0, -2 #noch n-2 schritte übrig
move $t2, $zero #f_n-2=0
addiu $t1, $t2, 1 #f_n-1=1
fib_loop:
addu $t0, $t1, $t2 #f_n=aus alten werten berechnen
beq $a0, $zero, offset_t0 #wenn letzter durchgang, $t0 zurückgeben
move $t2, $t1 #werte weiterkopieren (hier könnte man auch ein dreiteiliges loop-unrolling machen)
move $t1, $t0 #werte weiterkopieren
addi $a0, $a0, -1 #zähler verringern
j fib_loop
offset_a0:
move $v0, $a0
j $ra
offset_t0:
move $v0, $t0
j $ra
mr.escape
mr.escape Nachtrag zu: „Vielleicht so? start a0 n rückgabe in v0 zerstört inhalt von t0, t1, t2 und...“
Oder etwas eleganter, schneller (etwas loop unrolling zwecks "register renaming") und (hoffentlich) ohne pseudobefehle.
In $a0 wir der (positive) parameter n übergeben, die rückgabe erfolgt in $v0 und nur der inhalt von $t0, $t1 und $t2 wird verändert.
.text
.globl __start
__start:
ori $v0, $a0, 0 #für den fall n addi $t0, $a0, -2 #vergleichsgröße und zugleich anzahl der echten rechenschritte (falls nötig)
bltz $t0, fib_end #für n-2
ori $t1, $zero, 1 #f(n-1)=1
ori $t2, $zero, 0 #f(n-2)=0
fib_loop:
addu $v0, $t1, $t2 #f(n)=aus alten werten berechnen
beq $t0, $zero, fib_end #wenn letzter durchgang, $v0 zurückgeben
ori $t2, $v0, 0 #$t2 hat nun f(n-1), $t1 hat f(n-2)
addi $t0, $t0, -1 #zähler verringern
addu $v0, $t1, $t2 #f(n)=aus alten werten berechnen
beq $t0, $zero, fib_end #wenn letzter durchgang, $v0 zurückgeben
ori $t1, $v0, 0 #$t2 hat nun wieder f(n-2), $t1 hat f(n-1)
addi $t0, $t0, -1 #zähler verringern
j fib_loop
fib_end:
j $ra
mr.escape
mr.escape hategrown „fibonaccifolge in mips assembler“
Hier ist noch ein beispiel enthalten:
http://www.inf.uni-konstanz.de/dbis/teaching/ws0304/computing-systems/download/rs-05.pdf
mr.escape
hategrown Nachtrag zu: „fibonaccifolge in mips assembler“
hi !
danke borlander u. mr escape hat mir sehr weitergeholfen. @borlander falls du noch an einer mips referenz interessiert bist ...check out :
http://www.cs.wisc.edu/~larus/spim.html
unter resources ist ne referenz als pdf
danke nochmal
mfg hategrown
hategrown Nachtrag zu: „fibonaccifolge in mips assembler“
hi !
ich hätt da noch ein problem/frage
kann man in mips assembler mit modulo rechnen ? wenn wie lautet ein befehl dafür ich find nix .
müsste folgende aufgabe lösen:
Schreiben sie ein iteratives Mips assemblerprog, das sie wie folgt verhält:zu beginn ist in register $a0 eine 32bit lange zahl n in zweierkomplement darstellung abgelegt. am ende des progs steht in register $v0 die anzahl der "1"en, die die dartsellung von n im zweierkomplement hat.
mr.escape hategrown „hi ! ich hätt da noch ein problem/frage kann man in mips assembler mit modulo...“
Modulo ist bei berechnungen die binär erfolgen overkill. Dafür gibt es die schiebefunktionen.
.text
.globl __start
__start:
ori $t0, $zero, 32 #so viele bits zu testen
ori $v0, $zero, 0 #so viele schon gefunden
__loop:
andi $t1, $a0, 1 #$t1=0 wenn unterstes bit==0 und t1=1 wenn unterstes bit==1
add $v0, $v0, $t1 #$v0 erhöht sich um eins, wenn im untersten bit von $a0 eine eins war
srl $a0, $a0, 1 #$a0 um eine stelle nach rechts schieben, unterstes bit fliegt raus und wird durch das zweite ersetzt
addi $t0, $t0, -1 #zähler verringern
beq $t0, $zero, __end #wenn alle 32 bits getestet, $v0 zurückgeben
j __loop
__end:
j $ra
mr.escape
mr.escape Nachtrag zu: „Modulo ist bei berechnungen die binär erfolgen overkill. Dafür gibt es die...“
Noch etwas zum overkill.
Division durch 2^n lässt sich als shift-right um n stellen darstellen, wobei das höchste bit bei vorzeichenbehafteter darstellung beim schieben nicht durch 0 sondern sich selbst ersetzt wird, damit das ergebnis nicht falsch wird.
Der rest einer solchen division sind die ersten n bits vor dem shift-right (also genau das, was später raus fliegt).
Da in der aufgabenstellung die darstellung im zweierkomplement erwähnt ist (auch wenn das für die gestellte aufgabe unbedeutend ist), sollte nicht wie von mir verwendet srl (shift right logical), sondern sra (shift right arithmetic, also beibehaltung des höchsten bits oder auch srl der unteren 31 bits und kopieren des 32. bit ins 31. bit) verwendet werden.
Statt
srl $a0, $a0, 1
also
sra $a0, $a0, 1
mr.escape
