writing iteration in MIPS

Question

I am writing this program in MIPS to calculate 2 to a power given by me and sum the sequential powers down to 0. For example, if I put 4 in $a0 like in the code below, I want it to calculate (4^2)+(3^2)+(2^2)+(1^2) which should come out to be 15. It should stop before it reaches zero. This is what I have written so far

main: 
addi $a0, $zero, 4    #put k in $a0 in this case 
addi $a1, $zero, 0    #put 0 in current sum
addi $v1, $v1, 0      #tally the total in $v1   
for:  
lw $10, $a0           #load k into reg $10
lw $11, $a1           #load sum into $11
    addi $10, $10, -1     #subtracts 1 from k
    li $9, 0              #sets i in for loop ($9) to 0

done:

    li $v0, 10
    syscall

I'm new to MIPS and could use a lot of help on finishing this, I know I want to use a for loop, but I don't know how to go through it while subtracting 1 from k and also calculating the sum. How would I bring 2 to a power of k, because I guess there is no power operation in mips. At this point in the course I can only use add, sub, and, or, slt, addi, j, beq, lw, sw, and sll. Can you not use a constant when using sub? Thank you for any help

Answer 1

A power is a multiplication, and a multiplication is a sum. So you can write a function that does a multiplication by adding, and another function that does power by multiplicating. For example, the multiplication function:

multiply: # $a0 first factor, $a1 second factor, $v0 result of multiplication
    or $t0, $zr, $zr 
    or $t1, $a1, $a1
    or $t3, $zr, $zr
loop:
    beq $t1, $zr, end
    add $t0, $t0, $a0
    addi $t1, $t1, -1
    j loop
    nop
end:
    or $v0, $t0, $0
    jr $ra
    nop

(Please note I haven't tested this, and this will not work with negative numbers)

As a side note, you have MUL instruction as well, but I don't know if you saw that already.

Answer 2

I think the concept your instructor is trying to show you is that sll, in effect, multiplies by 2. You've got to think in binary. For example, let's start with 1:

0000 0000 0000 0000 0000 0000 0000 0001

Do a 'sll' on that, and what do you end up with? 0010 = 2. sll again and you get 0100 = 4. And so on, until you shift all the way over and have 0x80000000.

So the answer to the question, "How would I bring 2 to a power of k?", is simpler than you might have thought: you shift 1 by k.

# $t0 contains 'k', the amount we want to shift by
addi $t1, $zero, 1
sllv $t3, $t1, $t0

Note: I had to double-check that you can shift by a variable amount, but this link says sllv is valid. However, since it's not in your list of allowed functions, you'll have to do sll $t1, $t1, 1 in a loop. (Be sure to put your check at the start of the loop, in case the amount you want to shift by is zero!)

Answer 3

Quick question:

Are you doing 2^4+2^3.. etc? or 4^2+3^2 etc? Just a quick note:

2^4+2^3+2^2+2^1+2^0 = 15.

4^2+3^2+2^2+2^1 != 15.

(If it is the first, you do need 2^0 because you need to contemplate for odd numbers, 2^0 = 1. This is how we get odd numbers in binary.)

In this case, the answer about left shift (lls) is correct. When you left shift a binary number you increase the exponent of base 2 by 1.

so:

0001 = 1
0010 = 2
0100 = 4
1000 = 8

These summed give you 15.

So you could shift left, and add the result of each shift to a register.