tengo un ejercicio y no se ni como empezar estoi mui perdido he empezado ahora si me pudieran ayudar gracias el ejercicio es el siguiente:
En este ejercicio se debe realizar una función recursiva que dado como parámetro de entrada un número natural “n”, devuelva la suma de los cuadrados de los números desde 1 hasta n.
el simulador es en mars el procesador no se que tipo es los requisitos que piden son los siguientes:
La función que calcula la suma de los "n" cuadrados se debe llamar "cuad"
• La función "cuad" tomará un parámetro de entrada "n" que se le pasará por el registro $4 y devolverá el resultado por el registro $2
• No hay que tener en cuenta el desbordamiento,sólo hay que devolver los 32 bits menos significativos del resultado (recuerda que al multiplicar dos números de 2 bits el resultado es de 64 bits, considerar sólo los 32 menos significativos)
gracias un saludo
La función que calcula la suma de los "n" cuadrados se debe llamar "cuad"
• La función "cuad" tomará un parámetro de entrada "n" que se le pasará por el registro $4 y devolverá el resultado por el registro $2
• No hay que tener en cuenta el desbordamiento,sólo hay que devolver los 32 bits menos significativos del resultado (recuerda que al multiplicar dos números de 2 bits el resultado es de 64 bits, considerar sólo los 32 menos significativos)
gracias un saludo
MARS (MIPS Assembler and Runtime Simulator) es un simulador del procesador MIPS.
El primer paso es escribir la función recursiva que te piden, en este caso:
cuad(n) = n² + cuad(n-1)
cuad(1) = 1
Esa es la función que debemos implementar (cuad(n) = n² + cuad(n-1)), y su caso base (cuad(1) = 1).
Con esto ya podemos empezar.
Primero, necesitamos saber si se cumple (o no) el caso base (si n = 1), debemos implementar:
Para ello, comprobaremos si n (el parámetro de entrada $4) es menor que 2.
En caso contrario, devolvemos n (almacenado en $4), y en caso contrario, saltamos a else.
Disponemos de la instrucción slt (Set on Less Than):
Si $4 (n), es menor que 2, el valor de $8 (registro temporal) será 1, en caso contrario, 0.
Por lo que pasamos a interpretar el valor de retorno con la instrucción beq (Branch on equal):
Si el contenido de $8 es igual a 0 (constante en $0) salta a else.
Si no, ejecuta la siguiente instrucción.
Ahora queremos devolver n, es decir, queremos tener en $2 (registro de salida), lo que haya en $4 (registro de entrada). Lo podemos solucionar con un simple add
(0 + $4 = $4 -> $2)
Y volvemos simplemente con:
(recuerda la instrucción jal, Jump And Link)
Bien, hasta aquí sencillo.
Ahora hay dos partes, la recursividad, y el cálculo de los valores devueltos.
En primer lugar vamos a implementar la recursividad. Para ello usaremos la pila (stack).
Recuerda que en $29 se almacena el puntero (stack pointer), y cómo se almacenan los datos.
Pero, ¿qué debemos almacenar en dicha pila? Muy simple, la dirección de retorno ($31, por jal), y el valor calculado en esa etapa (n²).
Antes, debemos reservar espacio en la pila para estos dos valores:
Restamos 8, 2 palabras (1 palabra = 4 bytes, 2*4 = 8), dejando espacio para dos palabras, siendo $29 el puntero.
Y calculamos n²:
Ahora, guardamos en la pila los dos valores, la dirección de retorno ($31) y n² (almacenado en $9):
Nótese el 4 de desplazamiento, ya que el primer valor ($31) ocupó la primera palabra de las dos que reservamos, la siguiente se deberá almacenar a una distancia de una palabra (4 bytes) del puntero ($29).
Y ahora llamamos a cuad(n-1):
Ahora, implementaremos el cálculo de los resultados. Para ello, deberemos retirar de la pila los valores almacenados anteriormente, y seguidamente, efectuar el cálculo de n² (almacenado en la pila) y el resultado devuelto por cuad(n-1) (almacenado en $2).
Ahora sabemos dónde tendremos que ir ($31) y el valor de n² ($4), ya que antes se encontraban en la pila...
Pero no podemos olvidarnos de restaurar la pila para, posteriormente, seguir sacando los valores calculados y las direcciones de salto.
Simplemente, avanzamos el puntero dos palabras hacia delante.
Llegados a este punto, solo nos queda sumar el resultado anterior, cuad(n-1) (devuelto en $2) a n² (almacenado en $4 ahora), y seguir a la siguiente dirección (almacenada en $31 ahora):
Como nota final aclaratoria, cabe destacar el uso de $2 para almacenar el valor del caso base y para ir guardando los resultados parciales de la recursividad, y el uso de la pila para almacenar n², ya que cuad(n-1) estará disponible en $2.
Te dejo el código completo.
Cualquier cosa, no dudes en preguntar :D
Un saludo!!
El primer paso es escribir la función recursiva que te piden, en este caso:
cuad(n) = n² + cuad(n-1)
cuad(1) = 1
Esa es la función que debemos implementar (cuad(n) = n² + cuad(n-1)), y su caso base (cuad(1) = 1).
Con esto ya podemos empezar.
Primero, necesitamos saber si se cumple (o no) el caso base (si n = 1), debemos implementar:
Código: Seleccionar todo
if (n <= 1) {
return n;
} else {
...
}
En caso contrario, devolvemos n (almacenado en $4), y en caso contrario, saltamos a else.
Disponemos de la instrucción slt (Set on Less Than):
Código: Seleccionar todo
slt $8, $4, 2
Por lo que pasamos a interpretar el valor de retorno con la instrucción beq (Branch on equal):
Código: Seleccionar todo
beq $8, $0, else
Si no, ejecuta la siguiente instrucción.
Ahora queremos devolver n, es decir, queremos tener en $2 (registro de salida), lo que haya en $4 (registro de entrada). Lo podemos solucionar con un simple add
Código: Seleccionar todo
add $2, $0, $4
Y volvemos simplemente con:
Código: Seleccionar todo
jr $31
Bien, hasta aquí sencillo.
Ahora hay dos partes, la recursividad, y el cálculo de los valores devueltos.
En primer lugar vamos a implementar la recursividad. Para ello usaremos la pila (stack).
Recuerda que en $29 se almacena el puntero (stack pointer), y cómo se almacenan los datos.
Pero, ¿qué debemos almacenar en dicha pila? Muy simple, la dirección de retorno ($31, por jal), y el valor calculado en esa etapa (n²).
Antes, debemos reservar espacio en la pila para estos dos valores:
Código: Seleccionar todo
addi $29, $29, -8
Y calculamos n²:
Código: Seleccionar todo
mul $9, $4, $4
Código: Seleccionar todo
sw $31, 0($29)
sw $9, 4($29)
Y ahora llamamos a cuad(n-1):
Código: Seleccionar todo
addi $4, $4, -1
jal cuad
Código: Seleccionar todo
lw $31, 0($29)
lw $4, 4($29)
Pero no podemos olvidarnos de restaurar la pila para, posteriormente, seguir sacando los valores calculados y las direcciones de salto.
Código: Seleccionar todo
addi $29, $29, 8
Llegados a este punto, solo nos queda sumar el resultado anterior, cuad(n-1) (devuelto en $2) a n² (almacenado en $4 ahora), y seguir a la siguiente dirección (almacenada en $31 ahora):
Código: Seleccionar todo
add $2, $4, $2
jr $31
Te dejo el código completo.
Código: Seleccionar todo
.data
n: .word 3
.text
main: lw $4, n($0)
jal cuad
li $2, 10
syscall
cuad: slt $8, $4, 2 # n < 2 ?
beq $8, $0, else # j else
add $2, $0, $4 # return n
jr $31
else: addi $29, $29, -8 # reserva 2 posiciones en la pila (2x4 = 8)
mul $9, $4, $4 # n^2
sw $31, 4($29) # guardamos $31 (stack pointer)
sw $9, 0($29) # guardamos n^2
addi $4, $4, -1 # n--
jal cuad # call cuad(n-1)
lw $4, 0($29) # restauramos n^2
lw $31, 4($29) # restauramos $31 (stack pointer)
addi $29, $29, 8 # restauramos la pila
add $2, $4, $2 # return n^2 + cuad(n-1)
jr $31
Un saludo!!
github.com/Slek-Z