Hack assembly language - finding the maximum number in RAM

Question

as a task I have to find the maximum number in the RAM locations 10 to 20 and we have to write the solution into RAM[0]. I have a big problem with getting the indexes up every time the loop goes through and I'm confused by the way of storing the data. Can someone help me? I have literally tried everything without any kind of solution...

My so far best approach:

@0
D=A
@R0
M=D

@10
D=A
@R1
M=D

@R1
D=M
@i
M=D //i=RAM[1]=10

(LOOP)
  // break condition for the Loop: If the Index i is = 20 --> goto End
  @i
  D=M
  D=D-20
  @END
  D; JEQ

  // i=i+1
  @i
  D=M 
  D=D+1
  M=D

  // store the value of RAM[i] in RAM[0]
  @i
  D=M 
  @R0
  M=D

  // Compare the value of RAM[i] and RAM[0]
  @i
  D=M 
  @R0
  D=D-M
  
  @R0
  M=D

  @i
  D=M
  @R0
  M=D

(END)
  @END
  0;JMP

Here is the problem, that the compiler has some problem with line 19 ("Expected Expression"). Has this Error to do with the variable somehow?

Kind regards and thanks for your time

Answer 1

You may find it helpful to develop the algorithm in a language you are comfortable with, using simple statements, and then convert it into Hack assembly. That way you'll be sure the algorithm is correct, and you'll be able to track what the Hack code is doing and more easily spot mistakes.

Putting the high-level code into your Hack project as comments will also be helpful.

To compare two numbers in Hack, you subtract one from the other and then jump based on the resulting flags. The boilerplate code looks something like this:

// IF VAR_1 == VAR_2 GOTO SOMELABEL
 
@VAR_2     // A = Address of VAR_2
D = M      // D = VAR_2
@VAR_1      // A = Address of VAR_1
D = D - M  // D = VAR_2 - VAR_1
@SOMELABEL // A = Address of where we want to Jump
D ; JEQ    // Set flags based on contents of D, Jump to (A) if EQ flag set (ie: D=0)

Once you have something that is working, don't stop there. One of the joys of writing in assembly language is finding clever optimizations that reduce the size of your code. See how many you can find and add to your bag of tricks.

Answer 2

The following loop exit test won't work because there is no instruction that does D=D-20

@i
D=M
D=D-20
@END
D; JEQ

Instead of that, source 20 to the A register, then do D-A, as follows:

@i
D=M
@20
D=D-A
@END
D; JEQ

---

Here:

// i=i+1
@i
D=M 
D=D+1
M=D

You can simplify as:

// i=i+1
@i
M=M+1

Let's note that this part is happening too soon.  You want to do the i++ after the other parts of the loop body, otherwise you'll skip RAM[10].

---

This operation does RAM[0]=i not RAM[0]=RAM[i]

// store the value of RAM[i] in RAM[0]
@i
D=M 
@R0
M=D

RAM[i] is indexing by a variable (aka pointer dereference) so if i is in memory, then this will require two reads to memory, the first to read i then the second to read where the value of i refers.

@i
A=M // read i directly into A
D=M // read RAM[i], e.g. the address to which i, in A and taken as pointer, refers

@R0
M=D // write RAM[i] to RAM[0]

Let's also note that this operation is also premature: you only want to capture RAM[0]=RAM[i] under the condition that it is the current max, but you're doing it always, unconditionally.  So, this operation should be the then-part of an if statement.

---

Hopefully, you can see now how variable indexing works: RAM[i], where i is in memory requires two reads: two ...=M operations.  Since i is a pointer to location 10 (at first, then 11 later), you need to get i into the A register so you can read where that points.

Also, the order of the various operations does not follow a working algorithm.  Try writing out the loop in pseudo code.  Trying to work out an algorithm in assembly when you don't know it is hard, and, debugging a broken algorithm in assembly is even harder.

Here's an example doing max:

int max = 0;
for ( int i = 10; i != 20; i++ ) {
    D = RAM[i];
    if ( D > max )
        max = D;
}

Let's simplify, by translating this into a while loop:

int max = 0;
int i = 10;
while ( i != 20 ) {
    D = RAM[i];
    if ( D > max )
        max = D;
    i++;
}

Can you see that the i++ needs to be at the end of the loop body, so that the main portion of the loop body operates with the original i?

You also need to implement the if-statement so that you capture max=D only when it is actually larger than the current max.

And also complete the loop so that it iterates.