1

So im trying to add 1+2+3... and so on...without using brute force. Y=∑_1^100▒X_i, the numbers Xi are stored in consecutive memory locations starting at location 100. I am using the IAS instruction set:

IAS instructions I think will be sufficient to complete this task

I just cant seem to get this done. I dont even know where to begin, no real loops or if statements

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Codebank
  • 19
  • 3
  • 3
    What do you mean by "without using brute force"? You could use the summation formula or might as well just hardcode the result then... – Jester Apr 14 '20 at 00:11
  • I mean i dont want to load 1 to the accumulator and then add 2 and then 3 line by line. – Codebank Apr 14 '20 at 00:19
  • Q: Can you show us what you've tried? Q: Do you happen to have an IAS simulator to test with? Q: Does [this](http://www.cs.colby.edu/djskrien/IASSim/) example help? – FoggyDay Apr 14 '20 at 00:21
  • *"... and then add 2 and then 3 line by line"* So you want to use a **loop**? We'd consider that brute-force too, but are you really asking us how to write the assembly equivalent of `sum = 0; for i = 1 to 100 { sum = sum + i }`?. – Andreas Apr 14 '20 at 00:31
  • I dont even know how to reply to individual responses (im such a klutz ^_^). Im clicking but im not even seeing anything to click. In response to @Andreas , i just want to use the instruction set provided in the imgur link. If the instruction set gave more options like loops and ifs it would be easy for me. – Codebank Apr 14 '20 at 00:38
  • @FoggyDay this does help a bit, but my problem is that I have no increment instructions to use like the one in the example. And yes i have an IAS Sim. Sorry for bad language, still learning ^_^ – Codebank Apr 14 '20 at 00:42
  • @Codebank *"If the instruction set gave more options like loops"* What do you think you use `JUMP M` for? You could, you know, jump *back*, thereby creating a loop. --- *"... and ifs"* What do you think you use `JUMP+M` for, you know, the instruction with description *"**If** the number in the accumulator is nonnegative, ... [JUMP]"*? You jump past the code you don't want to execute. – Andreas Apr 14 '20 at 00:42
  • @Codebank: On SO, you reply to a comment by mentioning a username with an @. If it autocompletes you're doing it right. There's nothing you can click to do it. – Peter Cordes Apr 14 '20 at 01:43
  • Your ISA has a multiply so you can use that to implement Gauss's closed-form formula `n * (n+1) / 2`. Or if you want to be careful to avoid integer overflow for inputs up to the max that will fit, you can adjust that formula the way clang does when it turns a `for() sum += i;` loop into a closed form. (Try it on https://godbolt.org/z/iMJH8t e.g. for 32-bit x86. It shifts bits between the high and low halves of the full multiply result in EDX:EAX with an `shld` double shift, so probably you should just use the simple form of the formula and not worry about overflow before the final shift) – Peter Cordes Apr 14 '20 at 01:50

1 Answers1

2

You have 4 different possible approaches, that I will write in x86 since my knowledge of IAS is very limited, but you can apply the same logic

1/ Brute force

xor eax, eax
mov ecx, 100

.myloop:
add eax, ecx
dec ecx
jnz .myloop

2/ From brute force logic you can load value at memory address (which seems to be what you want to do? I add from 100 to 1.

xor eax, eax
mov ecx, 100

.myloop:
lea edx, [100+ecx*4-4]       ; assuming integer array
add eax, [edx]
dec ecx
jnz .myloop

3/ A more efficient way, and assuming the numbers follow each other and starting from 1, you can use the famous formula res = n(n+1) / 2. If you think about a dice, the sum from 1 to 6 is 21, which is exactly 6 * 7 / 2. To avoid the INT_MAX overflow I would suggest to test if the bit of n is set, if it is set divide n+1 by 2, else divide n by 2

mov edx, [100+99*4]      ; load value 100 in register edx
test edx, 1
jnz .planb

mov eax, edx
shr eax
inc edx
imul eax, edx
leave
ret

.planb:
mov eax, edx
inc eax
shr eax
imul eax, edx
leave
ret

4/ hardcode n(n+1)/2 in your register. (equal to 5050)

Antonin GAVREL
  • 9,682
  • 8
  • 54
  • 81
  • IAS apparently doesn't have bitwise operations. But it has `div` so you could use that to test for odd/even for the closed-form implementation that avoids overflow by branching. By contrast, clang's closed-form pattern (https://godbolt.org/z/Bv22Sz) uses a widening multiply and does an extended-precision right shift to get a 32-bit result from the low 33 of the multiply. (Apparently IAS has a widening multiply but shifting in a new high bit is probably a big pain so branch looks good). – Peter Cordes Apr 14 '20 at 05:31
  • 1
    Snippet 2 just needs `add eax, [100 + ecx*4 - 4]`. You forget to actually **read** the memory (missing [] on `add eax, edx`). Also the 100th element is found at array index `ECX=99`. – Sep Roland Apr 19 '20 at 21:09
  • Snippet 3 can't use the `LEA` instruction. You need to actually load from memory using `MOV`. – Sep Roland Apr 19 '20 at 21:33
  • I saw your invite for a chat. Sorry, but I will be logging off in a few minutes. – Sep Roland Apr 19 '20 at 21:36
  • no worries, it was just to confirm the changes made to the edit – Antonin GAVREL Apr 19 '20 at 21:37