Trouble with division using shifting

Question

I'm having some trouble implementing a division algorithm with MIPS, I'm assuming it has something to do with the way that I'm shifting and setting the least significant bit, but I'm not entirely sure.

The algorithm goes like this:

1) Subtract the divisor register from the remainder register and place the result in the remainder register.

2a) If the remainder >= 0, shift the quotient register to the left, setting the new rightmost bit to 1

2b) If the remainder <0, Add the divisor register to the remainder register and store the result in the remainder register (to restore the remainders previous value). Shifht the quotient register to the right, setting the rightmost bit to 0.

3) Shift the divisor register right one bit

4) Do this n+1 repititions. Since we are doing unsigned 8-bit division, i would assume this to mean 9 repitions

Edit: To make this simpler, I just set $t0 = 12 and $t1 = 5. However for the quotient i get 63 and the remainder I get 0


    .data
    quotient_a:     .asciiz "Quotient (a/b): "
    remainder_a:        .asciiz "Remainder (a/b):"
    quotient_b:     .asciiz "Quotient (b/a): "
    remainder_b:        .asciiz "Remainder (b/a):"
    error:          .asciiz "Sorry, divide-by-zero not allowed"
    new_line:       .asciiz "\n"


    .text
main:
    li $s0, 8   #8 bit

    li $t0, 12
    li $t1, 5

    ## Quotient  A message
    la $a0, quotient_a      # load the addr of display_sum into $a0.
    li $v0, 4           # 4 is the print_string syscall.
    syscall             # do the syscall.

    ##Computer the Quotient and remainder
    ## $t0 = a     $t1 = b
    ## $t0 = dividend       $t1 = divisor
    li $t2, 0       ##Quotient
    li $t3, 0       ##Remainder
    li $t9, 0       ##i
    li $s0, 9       ##count

loop:
    sub $t3, $t3, $t1
    blt $t3, 0, less_than
    ## >= 0
    sll $t2, $t2, 1
    addi $t2, $t2, 1
    j cont

less_than:
    add $t3, $t3, $t1
    sll $t2, $t2, 1

cont:   
    srl $t1, $t1, 1 
    addi $t9, $t9, 1
    bne $t9, $s0, loop



    ## print the quotient 
    move $a0, $t2
    li $v0, 1           # load syscall print_int into $v0.
    syscall             # make the syscall.

    ## new line
    la $a0, new_line        # load the addr of new_line into $a0.
    li $v0, 4           # 4 is the print_string syscall.
    syscall 

    ## Remainder A message
    la $a0, remainder_a         # load the addr of display_sum into $a0.
    li $v0, 4           # 4 is the print_string syscall.
    syscall             # do the syscall.

    ## print the remainder 
    move $a0, $t3
    li $v0, 1           # load syscall print_int into $v0.
    syscall             # make the syscall.

    #Exit Program
    li $v0, 10          # syscall code 10 is for exit.
    syscall             # make the syscall.

Michael Michael · Accepted Answer · 2013-03-26T11:15:25

The description of the algorithm looks a bit off to me. This is what a working 8-bit division algorithm in C looks like:

unsigned char Q,R;
unsigned char N=12,D=5;
int i;

Q = 0;
R = 0;
for (i = 0; i < 8; i++) {
    R <<= 1;
    R |= (N & 0x80) >> 7;
    N <<= 1;
    Q <<= 1;
    if (R >= D) {
        R -= D;
        Q |= 1;
    }
}

Transcribing that into MIPS assembly shouldn't be too difficult.

Trouble with division using shifting

1 Answers