Sign in to follow this  
lougv22

Unity Assembly programming question

Recommended Posts

lougv22    392
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.

Share this post


Link to post
Share on other sites
jorgander    180
Looks like others beat me to it.


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




EDIT: oops, im a retard. I was using address 1 to zero with. fixed now.

Share this post


Link to post
Share on other sites
Halifax2    295
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.

Share this post


Link to post
Share on other sites
NerdInHisShoe    130
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 ;)

Share this post


Link to post
Share on other sites
lougv22    392
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.

Share this post


Link to post
Share on other sites
Halifax2    295
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.

Share this post


Link to post
Share on other sites
Halifax2    295
Quote:
Original post by Halifax2
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.


Share this post


Link to post
Share on other sites
prtc22    144
Quote:
Original post by Halifax2
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.
It says "from the register" so the assumption is the result is 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 Halifax2
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.
When 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.

[Edited by - prtc22 on March 24, 2008 8:15:08 PM]

Share this post


Link to post
Share on other sites
PlayerX    279
Well the question doesn't state whether address 0 needs to be kept original or not, so here's one that'll keep address 0 intact:

STO A,1
SUB A,1 ; A = 0

SUB A,0 ; A = -0
STO A,1
SUB A,1 ; A = 0
SUB A,1 ; A = +0
STO A,1

Edit: D'oh! Beaten by a minute! :)

Share this post


Link to post
Share on other sites
Halifax2    295
Quote:
Original post by prtc22
Quote:
Original post by Halifax2
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.
It says "from the register" so the assumption is the result is 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 Halifax2
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.
When he saying '-0' and '+0' in the comments he means the -/+ of the value originally stored in memory location 0, not actually the value 0.


Ah okay, my fault.

And by the way, which company gave you this test?

Share this post


Link to post
Share on other sites
Bob_the_dev    186
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)


Using this, and assuming I'm doing this correctly, I got it down to 6 lines:
STO A, (1) [m1 = A]
SUB A, (1) [A = A - A = 0]
STO A, (1) [m1 = 0]
SUB A, (0) [A = 0 - m0 = -m0]
SUB A, (1) [A = 0-(-m0) = m0]
STO A, (1) [m1 = m0]

Share this post


Link to post
Share on other sites
jorgander    180
Quote:
Original post by Halifax2
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.


I'm assuming SUB uses unsigned integral math, in which case "-0" is just my shorthand for the complement of the value in the 0 address, with respect to the memory size of 32 bits.

For example, if the memory size was 4 bits, the maximum representable value would be 15 (once again, assuming unsigned values). Just for kicks, assume the value in address 0 is 5 at the start. After zero-ing both registers, the last four commands are:

SUB A,0 // register A now has (0 - 5) % 15 => 10
STO A,0 // address 0 now has A's value of 10
SUB B,0 // register B now has (0 - 10) % 15 => 5
STO B,1 // address 1 now has B's value of 5

Share this post


Link to post
Share on other sites
prtc22    144
Quote:
Original post by Bob_the_dev
Using this, and assuming I'm doing this correctly, I got it down to 6 lines:
STO A, (1) [m1 = A]
SUB A, (1) [A = A - A = 0]
STO A, (1) [m1 = 0]
SUB A, (0) [A = 0 - m0 = -m0]
SUB A, (1) [A = 0-(-m0) = m0]
STO A, (1) [m1 = m0]
Your second to last line doesn't actually do [A = 0-(-m0) = m0], it does [A = (-m0) - 0 = -m0], so the result you then store in memory location 1 is -m0.

Share this post


Link to post
Share on other sites
jorgander    180
Quote:
Original post by Bob_the_dev
Using this, and assuming I'm doing this correctly, I got it down to 6 lines:
STO A, (1) [m1 = A]
SUB A, (1) [A = A - A = 0]
STO A, (1) [m1 = 0]
SUB A, (0) [A = 0 - m0 = -m0]
SUB A, (1) [A = 0-(-m0) = m0]
STO A, (1) [m1 = m0]

Edit: yah... lotsa editting in this thread...

Share this post


Link to post
Share on other sites
NerdInHisShoe    130
Quote:
Original post by lougv22
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.


Sorry, theres an error in my first solution, disregard it.

I did this on paper like this:

A C
B D

A, B are registers, C D are memory locations 0 and 1 respectively

The trick is to get -C in memory and 0 in a register to do 0 - (-C) = C, then move it to memory


STO A,1
A C
B A

SUB A,0
A-C C
B A

SUB A,1
-C C
B A

STO A,1
-C C
B -C

STO B,0
-C B
B -C

SUB B,0
-C B
0 -C

SUB B,1
-C B
C -C

STO B,1
-C B
C C

Share this post


Link to post
Share on other sites
Bob_the_dev    186
Quote:
Original post by prtc22
Quote:
Original post by Bob_the_dev
Using this, and assuming I'm doing this correctly, I got it down to 6 lines:
STO A, (1) [m1 = A]
SUB A, (1) [A = A - A = 0]
STO A, (1) [m1 = 0]
SUB A, (0) [A = 0 - m0 = -m0]
SUB A, (1) [A = 0-(-m0) = m0]
STO A, (1) [m1 = m0]
Your second to last line doesn't actually do [A = 0-(-m0) = m0], it does [A = (-m0) - 0 = -m0], so the result you then store in memory location 1 is -m0.


Ahh you're right. Bummer

Share this post


Link to post
Share on other sites
lougv22    392
Quote:
Original post by Halifax2
Quote:
Original post by prtc22
Quote:
Original post by Halifax2
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.
It says "from the register" so the assumption is the result is 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 Halifax2
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.
When he saying '-0' and '+0' in the comments he means the -/+ of the value originally stored in memory location 0, not actually the value 0.


Ah okay, my fault.

And by the way, which company gave you this test?


I think it was Budcat Creations.

Share this post


Link to post
Share on other sites
lougv22    392
I noticed many of you are only using register A in their solutions. It seems to me if register B wasn't needed they wouldn't give it to us. Can those who didn't utilize register B explain why?

Share this post


Link to post
Share on other sites
prtc22    144
This was my solution:
Quote:
Original post by prtc22
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

You don't need to use both registers for this question because you don't need to hold more than one subtraction result at a time to complete the task.

Share this post


Link to post
Share on other sites
TheUnbeliever    963
I came up with this:

Instruction |	State
____________________________________________
| A: x B: y 0: v 1: ?
STO A, 1 | A: x B: y 0: v 1: x
SUB A, 1 | A: 0 B: y 0: v 1: x
STO B, 1 | A: 0 B: y 0: v 1: y
SUB B, 1 | A: 0 B: 0 0: v 1: y
SUB A, 0 | A: -v B: 0 0: v 1: y
STO A, 1 | A: -v B: 0 0: v 1: -v
SUB B, 1 | A: -v B: v 0: v 1: -v
STO B, 1 | A: -v B: v 0: v 1: v


(effectively NerdInHisShoe's solution, from a quick look)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this