finding out if there is a pair of elements in the array that sums to exactly K

Question

i am trying to write a for loop using MARIE that can find a pair of integers that sum to k. then it must output the index of the two numbers that add up to k. For Example: Input: [3, 7, 11, 5, -2, 1] Target K: 12 Output: 1, 3 Because Num[1] + Num [3] = 7 + 5 = 12 It is okay to assume that each input would have exactly one solution and I cannot use the same element twice. i found this c++ code that i tried to turn into marie code

**int find_sumPair (A[], n, K)
{
  for( i = 0 to n-1 )
  {
     for(j = i+1 to n-1)
     { 
         if(A[i]+A[j] == K)
         return 1
     }
  }
return -1
}****

the marie code is part of a bigger code which first allows the user to enter array size and then populate the array, after that thats when user inputs k value and tries to see if there are any elements which add up to the k value. i used indexposition but it is not referencing the positions of where the array elements are stored acccording to the marie simulator. i think the indexposition got distorted during the first half of the code which i have inserted below.

the following is my code so far

//code to create and populate array
ORG     100
INPUT 
STORE     ArraySize
OUTPUT    
LOAD   Arr
STORE   Indexposition
GetVal, LOAD  ArraySize
SUBT  index
SKIPCOND 800
JUMP Print
INPUT
STOREI Indexposition
LOAD   Indexposition
ADD   incr
STORE  Indexposition
LOAD index
ADD incr
STORE index
JUMP GetVal
Print, LOAD Arr
STORE Indexposition
CLEAR
STORE index
PrintVal, LOAD ArraySize
SUBT index
SKIPCOND 800
JUMP partB
LOADI Indexposition
OUTPUT
LOAD Indexposition
ADD incr
STORE Indexposition
LOAD  index
ADD incr
STORE index
JUMP PrintVal
partB, INPUT 
STORE Kvalue
//inner and outer loop to check for elements that add up to k
//loop1
outer, Load Indexposition
Subt one
Store t
Load t
Subt ArraySize
Skipcond 000
Jump loopend

//loop2
inner, Load Indexposition
Subt onee
Store j
Subt one
Store m
Load m
Subt ArraySize
Skipcond 000
Jump inner
Jump If

If, LoadI t
AddI m
Store SUM
Load SUM
Subt Kvalue
Skipcond 400
Jump Found
Load Indexposition
Add one
Store i
Jump outer

Found, Load Indexposition
Output
Load index
Output
Halt


index, dec 0
Indexposition, hex 28
ArraySize, dec 0
incr, dec 1
Arr, hex 28
One, dec 1
Kvalue, dec 0
SUM, dec 0
onee, dec 1
i, dec 0
low, dec 0
loopend, halt
j, dec 0
one, dec 1
m, dec 0
t, dec 0

Answer 1

You have pseudo code, so that's good.  It is important to know what you're trying to accomplish in assembly.  It is best to take working pseudo code to assembly, rather literally as is.  Use the same variable names, as much as possible, the same statements and expressions.

---

Variables i, j, ArrSize, K are in common between the two codes.  However, you have a variable index in the assembly that isn't present in the C code.  So, this assembly code diverges from the C code, and won't run the same.

---

The following code snippet offers no condition branch value:

Skipcond 000
Jump If
If, Load Indexposition

It either skips a jump or not, but in either case, simply continues at label If,.

---

The C/pseudo code has two loops, whereas the assembly code has only one.  You've merged the two loops together in some way that is not true to the idea of having the two loops.

In assembly we need backward branches to form a loop:

label,            <----------+
    ...                      |  loop structure
    jump label    *----------+

There's only one label and one backward branch in your assembly whereas there are two distinct loops in the pseudo code, so this also diverges.

You need a structure that looks more like this:

loop1,        <----------------------------+
    ...                                    |
loop2,          <----+                     |
    ...              |   inner loop        |  outer loop
    jump loop2   *---+                     |
    ...                                    |
    jump loop1 *---------------------------+

This is what it looks like to have an inner loop nested inside an outer loop, which is what's in the C code — nested loops: one loop inside the other.

---

You've mixed code and data here, which is bad form.

Found, Load Indexposition
Output
Load index
Output

index, dec 0
Indexposition, hex 28

Here, after the 2nd Output instruction runs, it will next execute the dec 0 — it is a logic error to ask the processor to execute data, so you should do something else there to prevent that (e.g. add a halt).

---

Array indexing requires indirection. A[i] means compute the address at A[i] by adding A and i, and then deference that: access the memory at that computed address.  You have something similar to A+i, but are missing the dereferencing/indirection, so what you want is to load A (address of A), add i, (now have A+i) then store that in a new variable, say t as in store t then do loadi t to accomplish the indirection and dereference the address to obtain the array element value at A[i]. 

(If A[i] were on the receiving end of an assignment, as in A[i] = x; then we would compute A+i, and ultimately use storei instead of loadi.)

Here t is a variable that is set and used right away — this is what we call a (short-lived) temporary variable.  (It is not a new loop variable.)  Since it's set and used and done with so quickly, you can reuse it immediately for the indexing of A[j] as well, for example.

---

While the pseudo code is fairly simple, that isn't C++, as C++ doesn't have a for .. to loop.  This means that you can't run this code to see if it works or study it using a C/C++ debugger.  Suggest that starting with running pseudo code is a better approach.

---

Regarding the introduction of another variable, index, and that the two loops were converted to one loop during translation: I suggest rather to just literally do exactly what the pseudo code does — translate each statement according to control flow patterns, then translate each expression stated, and locate statements and expressions in the same arrangement as the pseudo code.  Each statement, each expression has a pattern that translates to an assembly language pattern.  Succeeding statements (one statement after another) have a similar pattern in assembly; nested statements (one inside the body of another) have a similar pattern in assembly.

Don't make algorithmic improvements during translation to assembly.  Given starting with pseudo code, now is no time to get creative or inventive in the translation to assembly.  If you wanted to introduce an index variable, I would advise to do that in the C code first, then test it to make sure this change still works before taking it to assembly.

Of course in assembly, we need some temporary storage that the C code doesn't explicitly need, but while those are necessary in assembly (as in the variable t in the above indirection discussion) these are different from making algorithmic changes, such as introducing another loop variable.

---

From a program maintenance perspective, it is a dangerous practice to use a hard coded value (hex 28) to store the address array.  As you edit the program (and it maybe gets bigger) that constant goes out of date and needs adjustment.

I'd suggest the following: locate the array as the last item in the program, and get capture its address in a pointer variable as in the following:

 indexposition, jns array
 array,         dec 0      / this array extends beyond

The jns prefix on jns array says, put the address of the label array in this data memory variable — here this jns is being used as a data directive, like dec or hex, but accepting a label to be named instead of a numeric constant in decimal or hexadecimal.

(Note that jns has another purpose: it can also encode an instruction for calling a function, but that's not its use in the above.)

With that indexposition (named after your style) will hold the address of the (whole) array.