3 ms·

Seems like the key insight into solving problem 1 is constructing the unconditional jump operation. From what I remember of my Cambridge interview, the questio

• white-flame 11y ago
  Why would there be an unconditional jump? - Initialize locations 2 & 3 to zero. (solution & scratch register, leaving 0 & 1 unmodified) - While loc 2 is not equal to loc 0, increment loc 2. (Copy, just a conditional jump) - While loc 3 is not equal to loc 1, increment locs 2 and 3. (Still just a conditional jump) In the end, 2 holds the solution, 3 holds a copy of 1, and there are no unconditional jumps.
  • compiler-guy 11y ago
    Your pseudo-code misses that there must be two branches in each loop. In a high-level language, it looks like there is a single branching construct: while (condition) { do_something } But in assembly, which is what we are writing, there are two branches: The loop test and the loop back. If you could guarantee that the two numbers were not zero, you could do it without an entry check, but since that isn't stated in the problem, you need to check. Z2 // zero 2. This will hold the answer // Branch to "add element zero" loop if element zero is not zero J 0, 2, Handle_element_zero Z4 // unconditional branch to Handle_element_one I4 J 3, 4, Handle_element_one Handle_element_zero: I2 // increment answer J2, 0, Handle_element_zero // loop if we haven't iterated enough Z3 // zero loop counter Handle_element_one: J 1, 3, End // branch if there are no elements C: I3 I2 J3, 1, C End
    • jessaustin 11y ago
      The followup question was "Under what circumstances does this program fail?" so it seems they didn't want fancy input-checking, just a simple algorithm that assumed positive integers. After all, your algorithm doesn't handle fractional numbers, does it? "6.2" is displayed in the example!
      • compiler-guy 11y ago
        Given the supplied instructions, it is not possible to write a program that handles floating point correctly, so my guess is that the failure conditions are non-integer numbers in locations 0 or 1. My code also doesn't handle negative integers correctly, but I'm pretty sure there is a way to do it. However, given that it is possible to write a program that works for all integers, and that this is an entry question for Oxford, "As correct as possible given the constraints of the problem" would be the right answer.
        • thaumasiotes 11y ago
          > My code also doesn't handle negative integers correctly, but I'm pretty sure there is a way to do it. It's pretty easy to show by induction that you can't handle negative numbers in the general case. Consider: if memory locations 0 and 1 are both negative, so is their sum. But the only operations available to you are setting a value to 0, and incrementing it. You can't produce a negative number that way.
          • btilly 11y ago
            This is true. But if you are clever, you can handle the case where you have 2 arbitrary integers whose sum is non-negative! The trick is to zero out a counter, then increment it until it is one of the two starting values. Then start a second counter and increment it together with the other starting value until the second counter reaches the first and the other contains the sum of the two. Finally start a counter at location 2 and increment it until it reaches the value of the register that has the sum.