ISI 2019 | PCB CS | Question: 5

Question

Consider a stack machine where the only available workspace is a stack whose elements are unsigned integers. We will denote the configuration of the stack by a sequence. For example $[a, b, c, d]$ represents a stack with $a$ being the top most element and $d$ the bottom most element. The stack machine supports the following instructions:

PUSH $a$	Pushes $a$ to the stack i.e., if $[x, y, z]$ be the stack, after PUSH $a$,the stack becomes $[a, x, y, z].$
DUP	Duplicates the top, i.e., if $[a, b, c]$ be the stack, after DUP the stack becomes $[a, a, b, c].$
ADD	Adds the two topmost elements, removes them and pushes the result, i.e., if $[a, b, c]$ be the stack, after ADD it becomes $[a + b + c].$
SUB	Subtracts the two topmost elements, removes them and pushes the absolute value of the result, i.e., if $[a, b, c]$ be the stack, after SUB it becomes $[|a - b|, c].$
SQR	Computes the square of the topmost element, removes it and pushes the result, i.e., if $[a, b, c]$ be the stack, after SQR it becomes $[a^{2}, b, c].$
SFT	Removes the topmost element, right shifts the element by $1$ bit, and pushes the result, i.e., if $[a, b, c]$ be the stack, after SFT it becomes $[\left \lfloor a/2  \right \rfloor, b, c].$
REV	Reverses the order of the three topmost elements in the stack, i.e., if $[a, b, c, z]$ be the stack, after REV the configuration becomes $[c, b, a, z]$ (if the stack contains less than $3$ elements, REV is undefined).

 

Computation starts with an empty stack and after a sequence of operations the top most element is considered as the final result. For example, to compute an expression $\left((x+y)^{2}+\lfloor z / 2\rfloor\right)^{2}$ the following sequence of instructions may be used:

$$\textsf{PUSH} \;x;\; \textsf{PUSH} \;y; \;\textsf{PUSH}\; z;\; \text{SFT};\; \textsf{REV; ADD; SQR; ADD; SQR}$$

Given two unsigned integers $a$ and $b$, write a sequence of instructions to compute the product $a b$. The instruction sequence should start with:

$$\textsf{PUSH} \;a ;\; \textsf{PUSH}\; b ; \ldots$$

with no further $\textsf{PUSH}$ operations allowed. After the whole sequence of instructions executes, the top of the stack should contain $a b$.

Answer 1

Stack state	Instruction
a	PUSH a
a,b	PUSH b
a,a,b	DUB
${a}^{2}$,a,b	SQR
b,a,${a}^{2}$	REV
b,b,a,${a}^{2}$	DUB
${b}^{2}$,b,a,${a}^{2}$	SQR
a,b,${b}^{2}$,${a}^{2}$	REV
a+b,${b}^{2}$,${a}^{2}$	ADD
${(a+b)}^{2}$,${b}^{2}$,${a}^{2}$	SQR
${|(a+b)}^{2}$-${b}^{2}$|,${a}^{2}$	SUB
||${(a+b)}^{2}$-${b}^{2}$|-${a}^{2}$|	SUB
floor(||${(a+b)}^{2}$-${b}^{2}$|-${a}^{2}$|/2)	SFT

 

Comments

Right