You are not logged in.
Pages: 1
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)
Offline
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)
Offline
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.
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.
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)
Offline
Pages: 1