Doing some prep for interviews so doing interview questions people have posted on glassdoor for similar positions. Ran into one I'm stuck and a little confused on.
A processor with only 1 register and 2 memory slots. It has two instructions SUB and STO. Implement LOD, ADD, and MOV using only the following:
I'm Assuming STO is store and LOD is load here. So would the register be assumed to start with a value of 0? If not I'm not sure how to even start since I can't use subtract with the register if it has no value in it, can I? Bit lost here.
This is basically puzzle solving. Which is not terribly productive as an interview technique, but it definitely pays to understand that is the case and to treat it a bit differently than e.g. a methodical programming problem. In the interview context you want to make it very clear how you are approaching the search space and what you are thinking rather than just spitting out the answer.
In this spirit, I'll approach this a bit more conversationally...
Per the question of whether a has to be zero initially, what would we do if the initial value is arbitrary? How do we get it to be zero? The only compute instruction we have is a subtract... How do you get a guaranteed zero from that? Well X - X is always zero right? So if we need the accumulator to be zero, we store to a memory location and then subtract it back from the accumulator. The post condition for that is the accumulator is zero.
So from here we can see that one constraint we'll have is using one or both memory locations as temporary storage. This is a fairly big issue, but we likely have to insist that the composite instruction sequences get to use one memory location as a temp while the other is the input operand. It is an open question whether all operations can be implemented without destroying the input as well.
Let's start with load as it should be simplest. We want:
LOD a, memory1 # a = *memory1 -- destroys value in memory2
Lets try:
# zero a
STO a, memory2
SUB a, memory2
SUB a, memory1 # a == -memory1
# Save -memory1 and zero a again
STO a, memory2
SUB a, memory2 # a = 0
SUB a, memory2 # a = 0 - (-memory1)
There's LOD. It may well be possible to be more efficient, but that should get you started.
ADD a, memory1 # a = a + *memory1 -- destroys value in memory2
As above, we'll be using the X - (-Y) == X + Y algebraic equivalence.
STO memory2, a # save a, call this "original_a"
SUB a, memory2 # a = 0
SUB a, memory1 # a = -*memory1
SUB a, memory2 # a = -*memory1 - original_a
# Save -*memory1 - original_a, then zero a
STO a, memory2
SUB a, memory2
SUB a, memory2 # a = -(-*memory1 - original_a) == *memory1 + original_a
And so on...