Assembly programming question
Author
I was given this question during a take-home-videogame-job-interview-exam. I had almost no clue how to solve it at the time. I am just curious what the solution is and also thought it might be useful for people trying to break into the industry. So here goes:
You have been given the opportunity to do some work on the new TISC (two instruction code) microprocessor, which has been designed to execute at lightning speeds.
The processor implements only two instructions:
STO <register>,<address> ( store from this register to this address )
SUB <register>,<address> (subtract the value at this address, from this register)
It also contains only two 32 bit registers: A and B
The machine you’re working on has two 32 bit ram addresses: 0 and 1
When the machine boots up, assume it magically begins executing your code. The value of A and B are unknown. Write a program to copy RAM location 0 into RAM location 1, and then optimize the program to use the fewest number of instructions possible.
I came up with:
STO A, 1
SUB A, 0
SUB A, 1
STO A, 1
STO B, 1
SUB B, 0
STO B, 1
SUB A, 1
STO A, 1
STO A, 1
SUB A, 0
SUB A, 1
STO A, 1
STO B, 1
SUB B, 0
STO B, 1
SUB A, 1
STO A, 1
This is what I can work out in a few mins... surely not optimal, but should do the job.
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = - m0
STO A, (0) // m0 = - m0
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = 0 - (-m0) = m0
STO A, (1)
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = - m0
STO A, (0) // m0 = - m0
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = 0 - (-m0) = m0
STO A, (1)
Looks like others beat me to it.
EDIT: oops, im a retard. I was using address 1 to zero with. fixed now.
STO A,1 // Following four commands zero both registersSUB A,1STO B,1SUB B,1SUB A,0 // A has -0STO A,0 // 0 has -0SUB B,0 // B has +0STO B,1 // 1 has +0EDIT: oops, im a retard. I was using address 1 to zero with. fixed now.
Quote:Original post by samoth
This is what I can work out in a few mins... surely not optimal, but should do the job.
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = - m0
STO A, (0) // m0 = - m0
STO A, (1) // dup A
SUB (1), A // A = 0
SUB (0), A // A = 0 - (-m0) = m0
STO A, (1)
Given his description, that doesn't work! The first parameters to STO and SUB can only be registers.
In fact, given the description, this is impossible! Register A and B can be any value. You can't store any of your own values to A or B. Where does the subtraction end up at when the value at the address is subtracted from the register. Is it in memory, or does the result get stored in the register.
Quote:
In fact, given the description, this is impossible! Register A and B can be any value. You can't store any of your own values to A or B. Where does the subtraction end up at when the value at the address is subtracted from the register. Is it in memory, or does the result get stored in the register.
Its entirely possible, as many people have shown. We don't need our own values, the only important value is the value in register 0. Its like using variables in math class ;)
Author
Quote:Original post by NerdInHisShoe
I came up with:
STO A, 1
SUB A, 0
SUB A, 1
STO A, 1
STO B, 1
SUB B, 0
STO B, 1
SUB A, 1
STO A, 1
Hmm, could you briefly explain what each line does.
Quote:Original post by jorgander
STO A,1 // Following four commands zero both registers
SUB A,1
STO B,1
SUB B,1
SUB A,0 // A has -0
STO A,0 // 0 has -0
SUB B,0 // B has +0
STO B,1 // 1 has +0
That doesn't work because the 'SUB B,0' is subtracting -0 from the number 0. Which results in -0 again.
Quote:Original post by Halifax2Quote:Original post by jorgander
STO A,1 // Following four commands zero both registers
SUB A,1
STO B,1
SUB B,1
SUB A,0 // A has -0
STO A,0 // 0 has -0
SUB B,0 // B has +0
STO B,1 // 1 has +0
That doesn't work because the 'SUB B,0' is subtracting -0 from the number 0. Which results in -0 again.
Quote:Original post by Halifax2It says "from the register" so the assumption is the result is stored in the register.
Where does the subtraction end up at when the value at the address is subtracted from the register. Is it in memory, or does the result get stored in the register.
Here's my version which has 1 less instruction than some others:
STO A,1 // [1] = A
SUB A,1 // A = 0
SUB A,0 // A = -v (where v = original value at memory location 0)
STO A,1 // [1] = A = -v
SUB A,1 // A = -v - (-v) = 0
SUB A,1 // A = 0 - (-v) = v
STO A,1 // [1] = v
Quote:Original post by Halifax2When he's saying '-0' and '+0' in the comments he means the -/+ of the value originally stored in memory location 0, not actually the value 0. So SUB B,0 is equivalent to 0 - (-0) = +0.Quote:Original post by jorgander
STO A,1 // Following four commands zero both registers
SUB A,1
STO B,1
SUB B,1
SUB A,0 // A has -0
STO A,0 // 0 has -0
SUB B,0 // B has +0
STO B,1 // 1 has +0
That doesn't work because the 'SUB B,0' is subtracting -0 from the number 0. Which results in -0 again.
[Edited by - prtc22 on March 24, 2008 8:15:08 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
