Some coding help needed...

Miksy91 · 2013-04-30 14:22:37

I've got a bit of schoolwork which would give me "extra" points for a certain exam but I'm having hard time solving some of these, and I think there are quite many of you who could find this as a fun exercise and could possibly help out.

Keyboard: "10"


t  ds 200
i  dc   0
k  dc   0

main      in  r5, =kbd  ; read k    // can't modify
          store r5, k               // can't modify

;--------------------------------------------------
           ; load r0, =0
           load r1, r5      ; r1 = 10

mloop      sub r1, =1      ; r1 = r1 - 1
       
           load r2, r1    
           add r2, r5    
           mul r2, r2

           store r2, t(r1)   ; t(i) = (i+k) * (i+k)
           add r0, r2
           jpos r1, mloop

           out r0, =crt ; print sum

The code under (--------------------------------) line should be modified so that the "mloop" would fit in 6 machine instructions, while currently, I've got 7.

What this piece of code here should do is the following:

1) Save the sum of "t" (which is a table) somewhere and print it (like I'm doing with "add r0, r2" and "out r0, =crt" there).
2) Initialize table, t, so that t(i) = (i+k) * (i+k).

i and k are variables of which both are set to value "0" with "... dc 0".

If someone could possibly pick up what I should do about it yet I haven't distributed enough information about what I could do with this "machine language" or such, reply back!

If this thing here goes anywhere, I might ask for more help later.

Last edited by Miksy91 (2013-04-30 14:25:28)

Tauwasser · 2013-04-30 18:46:58

How many registers do you have?
What are the available commands?
Are there only binary commands? (ld r2, =0; ld r2, r3) or also ternary (add r2, r3, =0)
How much of the initialization code can be changed?
Do you have pointers?

Keyboard: "10"


t  ds 200
k  dc   0

main      in  r5, =kbd  ; read k    // can't modify
          store r5, k               // can't modify

;--------------------------------------------------
           ;; r0 = sum
           ;; r1 = difference between elements t(i) and t(i + 1)
           ;; r2 = t(i + 1)
           ;; r3 = index/loop counter
           ;; r5 = k
           load r0, =0; sum = 0
           load r1, r5;
           jneg r1 output;      \ optional: check input is valid
           jzero r1 output;     /
           add r1, r1;
           load r2, r1;
           add r1, r1;
           add r1, =1;  r1 = 2i + 2k + 1 (with i = k)
           mul r2, r2;  t(k) = (2k)^2
           load r3, r5;
mloop:
           sub r1, =2;  r1 = 2i + 2k + 1 (with i = j - 1)
           sub r2, r1;  r2 = t(k - 1)
           sub r3, =1;  j <= j - 1
           store r2, t(r3);
           add r0, r2;  sum += t(j)
           jpos r3 mloop

output:
           out r0, =crt ; print sum

The trick here is to know that

t(i) = t(i + 1) - (2i + 2k + 1)

So you don't have to do the expensive multiplication each time, but just the difference that is subtracted with each loop iteration. My initial version had more initialization code that would skip the "unnecessary" multiplication for t(k) and do t(k - 1) directly. However, the code turns out to be somewhat less understandable, and will still be constant runtime anyway (think big-O notation).

I save a whole second in matlab when running appropriate code for k = 1*10^8. When using the maximum for-loop iteration (k = 2147483647 ~ 2e9), your code runs 98.348223 seconds, while mine runs 6.496314 seconds :).

cYa,

Tauwasser

Last edited by Tauwasser (2013-04-30 19:18:16)

Miksy91 · 2013-04-30 20:25:15

Wow... :D
I got it working, thanks to you (that piece of code is actually totally fine as it is) :)

I'll reply back about the specifics tomorrow if you have time to visit here then too so I could possibly ask about some other exercise, maybe similar to this one or something else (like recursions, have been having trouble with those too).

Still, I can say that I would have hardly figured this out myself, haven't gotten used to all kinds of "tricks" yet since I just started doing this - they really come in time after being forced to doing the same thing over and over again though.

Tauwasser wrote:

However, the code turns out to be somewhat less understandable, and will still be constant runtime anyway (think big-O notation).
I save a whole second in matlab when running appropriate code for k = 1*10^8. When using the maximum for-loop iteration (k = 2147483647 ~ 2e9), your code runs 98.348223 seconds, while mine runs 6.496314 seconds :).
cYa,
Tauwasser

That's some difference there!
This is why we've got assemblers though :)

Edit:
I guess I'll reply (somewhat) anyhow.

Tauwasser wrote:

1. How many registers do you have?
2. What are the available commands?
3. Are there only binary commands? (ld r2, =0; ld r2, r3) or also ternary (add r2, r3, =0)
4. Do you have pointers?

1. There are 5 general registers (R1, ..., R5) that can be used also as index registers. R0 is a general reg. too but it is used in "information pointing" (can't really find the right words in english for this) instructions as index 0. And along with those, we've got SP and FP (Frame Pointer, used in subprograms for pointing to data pushed to stack before calling the subprogram).

2. Add, sub, mul, div, mod, and, or, xor, shl(a), shr(a), comp, jump, j(n)les, j(n)gre, j(z)er, j(n)pos, j(n)neg, load, store, push(r), pop(r), exit.
-I can explain necessary details about them later if I ask more questions tomorrow :)

3. Each instruction is split into five parts:
Operation code (8-bit), Ri (3-bit), Mode (2-bit), Rj (3-bit), Address (16-bit)

"Rj" or "Address" can be 0.

Mode indicates, what kind of a "information pointing" mode we're using.

1.
load r1, =5 (r1 = 5)
load r1, X (r1 = "value of variable X")

2.
load r1, =X (r1 = address of variable X)
load r1, =t(r2)

3.
load r1, @t(r2) (r1 = value pointed by address of (t + r2))

Last edited by Miksy91 (2013-04-30 20:40:01)

Skeetendo

#1 2013-04-30 14:22:37

Some coding help needed...

#2 2013-04-30 18:46:58

Re: Some coding help needed...

#3 2013-04-30 20:25:15

Re: Some coding help needed...

Board footer