CODEWITHSUNDEEP
assembly64-bitmipsdivide
Ileana Profeanu
Ileana Profeanu

Reputation: 387

How to divide a big (64-bit) number by two in PC-Spim

I have a school assignment, to find out the sum of 1 + 2 + ... + n in MIPS assembly language (using PC-Spim as a virtual machine). I wrote a simple program which doesn't deal with big numbers (so n*(n+1) must not be greater than 232-1 for it to work). I heard today that the professor, if you didn't use registers hi and lo, will tell you to use them and make the program work for 64-bit numbers too!

So this is the initial program:

.data
 n:.word 10
 s:.word 0
.text
main:
 lw $t0,n
 add $t1,$t0,1
 mulou $t1, $t0, $t1
 sra $t1,$t1,1
 sw $t1,s
sfarsit:
li $v0,10
syscall

and this is my try to modify it:

.data
 n:.word 1048576
 s:.word 0
 s2:.word 0
.text
main:
 lw $t0,n
 add $t1,$t0,1
 mult $t0, $t1
 mflo $t0
 mfhi $t1
 sra $t0,$t0,1
 sra $t1,$t1,1
 sw $t0,s
 sw $t1,s
sfarsit:
li $v0,10
syscall

the sra trick doesn't work if you apply it to each 32-bit part of your result. (even though I hoped it will lol)

n: 1048576
expected result: 549756338176
what the program gives you: 549755813888

a program result

What could I do to divide the big number by two?

Upvotes: 0

Views: 1241

Answers (1)

phuclv
phuclv

Reputation: 41814

You're dividing two 32-bit numbers by 2 separately, not a single 64-bit number by 2.

mult $t0, $t1
mflo $t0
mfhi $t1
sra $t0,$t0,1  # $t0 = $t0 >> 1
sra $t1,$t1,1  # $t1 = $t1 >> 1
sw $t0,s
sw $t1,s

You need to shift the whole 64-bit values. That means the shifted out bit of the higher part must be shifted into the low part

sll $t2, $t1, 31   # Backup the bit that will be shifted-out
srl $t2, $t1, 1    # High part: $t1 = $t1 >> 1
srl $t0, $t0, 1    # Low part:  $t0 = $t0 >> 1
or  $t0, $t2, $t0  # Merge the shifted-out bit back

Since n is always positive, you don't need to shift arithmetically anyway. Use it as an unsigned type with srl instead. In fact if n is a signed type then n/2 is much more complex because you need to do some rounding at the end, since right shift rounds downwards. You can see some demo on compiler explorer

Upvotes: 3

Related Questions