arqcomp: [2017][Febrero][Problema 2]

Buenos dias, tengo algunas dudas al respecto de la parte b de este ejercicio en el calculo del peor caso del stack

En la solucion de este problema, se dice que el peor caso es (n+1)R, siendo R los registros utilizados para cada llamada recursiva (AX, BX,...,SI, DI, BP, DIR_RET), sin embargo haciendolo manualmente llego a que:

N = 1 --> R

N= 2 --> R + 2R

...

N= n --> (2n + 1)R

Quisiera saber en que me estoy equivocando y si eventualmente este es un error significativo para perder el examen.

Adjunto la letra del ejercicio, gracias y saludos.

letra ejercicio

Re: Examen febrero 2017 ejercicio 2 - Assembler

de Guillermo Angel Kuster Techera - martes, 19 de diciembre de 2017, 11:34

Buenas, alguien me puede dar una mano con esto. He intentado enteder la solucion pero la verdad es que no le encuentro la vuelta de porque es (n+1)R y no (2n+ 1)R/

Saludos.

Re: Examen febrero 2017 ejercicio 2 - Assembler

de Federico Rivero - martes, 19 de diciembre de 2017, 12:35

Estimado,

Cada palabra que se pushea al stack ocupa 2 bytes. En la solución se habla siempre en términos de bytes, mencionando que son dos bytes por cada registro pusheado. Si querés dejarlo en función de los registros pusheados (R), el consumo sería R * (2N + 2), que como R = 9 da lo mismo que en la solución. Cuidado que es + 2 y no + 1 como mencionabas tú.

Espero haber despejado la duda.

Saludos,

Federico

Re: Examen febrero 2017 ejercicio 2 - Assembler

de Federico Rivero - martes, 19 de diciembre de 2017, 13:14

Estimado,

Volví a leer tu mensaje y la solución y se me ocurre un posible error mucho más grave.

El peor caso es cuando el árbol es una lista, por lo cual, la llamada recursiva de una de las ramas es siempre hacia el paso base. Por lo tanto no contribuye al máximo consumo de stack. Incluos así, el máximo consumo quiere decir eso: cuál es la máxima diferencia entre el tope y la base del stack. Por más que ambas llamadas recursivas fueran igual de largas, al comenzar la segunda, el consumo de la primera ya se retiró del stack, y por lo tanto no influiría en el máximo consumo.

No estoy seguro de si esto fue lo que quisiste decir, pero quería dejarlo claro.

Saludos,

Federico

Re: Examen febrero 2017 ejercicio 2 - Assembler

de Guillermo Angel Kuster Techera - martes, 19 de diciembre de 2017, 13:55

Federico,

Primero darte las gracias por la respuesta que me tenia a mal traer hace varios dias. Mi pregunta apuntaba justamente al razonamiento explicado en tu segunda respuesta. Tal y como tu lo mencionaste, pense en el peor caso como la suma de ambas ramas en el stack, pero es verdad que la funcion recursiva va hacia el paso base, por lo que sumar el costo de ambas ramas estaria mal.

Muchas gracias nuevamente.

Saludos.