26 views

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$.

1 vote