Have something to say? Contribute New Article Reply to this Article
MIPS Recursive Programming, Help please!
I have been working on this assignment for couple weks (aling with my other classwork) and I couldn't get it anywhere, can any one help me doing it. Or can you at least tell me hints and tips toward resolving the program: the question is:
The element selection problem is defined here as follows. Given a sequence S = {s1, s2, s3, ..., sn} of integers and an integer k, where 1 ≤ k ≤ n, find the k-th smallest integer in S. The outline of a recursive algorithm that can solve the selection problem follows (adapted from: S. Akl, The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989). The parameter Q in procedure SELECT is a small integer constant.
procedure SELECT(S,k) if | S | < Q then sort S and return the k-th element
else subdivide S into | S | / Q subsequences of Q elements each
end if.
Sort each subsequence and determine its median.
Call SELECT recursively to find m, the median of the | S | / Q medians found in 2.
Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.if | S1| ≥ k then call SELECT recursively to find the k-th element of S1
else if | S1| + | S2| ≥ k then return m
else call SELECT recursively to find the (k - | S1| - | S2|)-th element of S3
end if
end if.
The running time of SELECT is O(n) for any value of Q ≥ 5 (under this condition, recursive calls are carried out for sequences ever-decreasing in size).
Notice the similarities between SELECT and the popular QUICKSORT algorithm. The latter algorithm is for sorting, and has worst case and expected running times O(n2) and O(n lgn), respectively.
I used bubble sort in my code. and my code is the following:
* I Also Uploaded the code in a text file *
CODE
#/////////////////////////#hopefully this shit will work!!!!!!!!!
.data
se: .word 14,23,17
.text
sa: .space 50
sb: .space 50
sc: .space 50
.globl main
main:
la $a0, se #a0 refers to se
addi $s0, $zero,5 #Q
addi $s1, $zero,2 #K
add $s2, $zero,$zero #set s2 to zero
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# count
ct: lw $a1, 0($a0) #store the first word from a0 to a1
add $s2, $s2, 1 #add one to s5 (this is the counter)
addi $a0, $a0, 4 #go to the next word (shift index by 4bytes)
bne $a1, $zero, ct #if a1 is not at the end, go back to ct (count)
la $a0, se #make a0 refers back to beginning of se
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# compare and branch
bgt $s0,$s2,bbss #if Q > |S| then bubble sort and give K
j subs #otherwise, go to subs
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# finish the program
li $v0,10 # exit
syscall
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# bubble sort
bbss: addi $sp,$sp,-4 #adjust this MF for one element
sw $ra,0($sp)
bbs: addi $t0,$s2,0
addi $t0,$t0,-1 #$t0 = na - 1
la $t1,se # pointer pa, $t1 = address of a
li $t2,0 # exchange flag, $t2 = 0
loop:
beq $t0,$zero,done
lw $t6,0($t1) # $t6 = *(pa)
lw $t7,4($t1) # $t7 = *(pa+1)
slt $t3,$t6,$t7 # if ($t6 < $t7)
beq $t3,$zero,next # goto next
sw $t6,4($t1) #
sw $t7,0($t1) # *pa <-> *(pa+1)
li $t2,1 # set exchange flag
next: addi $t1,$t1,4 # pa++
addi $t0,$t0,-1 # $t0 = $t0 -1
j loop
done:
bne $t2,$zero,fin # if (exchange) goto main
fin: la $a0,se
sll $s1,$s1,2
add $s1,$a0,$s1
lw $s3,0($s1)
lw $ra,0($sp)
addi $sp,$sp,4
jr $ra
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# subs
# make em
addi $t0,$s0,0 #copy Q to t0
addi $t1,$s2,0 #copy counter to t1
div $t1,$t0 #to find how many time we have to split
sll $t2,$t0,2 #t2 now contains a shift amount = size of elements
la $t3,se #address of se into a0
again: addi $sp,$sp,-4 #adjust this pointer for 1 element
sw $t3,0($Sp) #store one element on it
add $t3,$t3,$t2 #add size of Q elements
subi $t1,$t1,1 #we did that once, so we subtract
bne $t1,$zero,again
addi $sp,$sp,-4 #adjust this pointer for 1 element
sw $t3,0($Sp) #store one bitch on it
# sort em
sort: addi $t0,$s0,0 #copy Q to t0
addi $t0,$t0,-1 #$t0 = na - 1
lw $t1,0($sp) #load the address of first section
addi $sp,$sp,4 #so we go to next section at next time
li $t2,0 # exchange flag, $t2 = 0
lop:
beq $t0,$zero,pull
lw $t6,0($t1) # $t6 = *(pa)
lw $t7,4($t1) # $t7 = *(pa+1)
slt $t3,$t6,$t7 # if ($t6 < $t7)
beq $t3,$zero,next # goto next
sw $t6,4($t1) #
sw $t7,0($t1) # *pa <-> *(pa+1)
li $t2,1 # set exchange flag
next: addi $t1,$t1,4 # pa++
addi $t0,$t0,-1 # $t0 = $t0 -1
j lop
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# Pull K
pull:
/CODE
* I Also Uploaded the code in a text file *
I would appreciate it
regards
Alright, the question is asking to subdevide an array of integers into a smaller ones; each sub array size is equal to a number (Q). Hence, if the original array size is less than Q, we don't need to subdevide it. Otherwise, we should devide the array into smaller ones as i said whith eatch has Q elements in it.
after that, we will sort each array and determine its median.
if you can do this part for me (devide, sort ten get each median), that would be great! don't worry about recursion cause i don't have to do it with recursion.
after that, we will sort each array and determine its median. if you can do this part for me (devide, sort ten get each median), that would be great! don't worry about recursion cause i don't have to do it with recursion.
If you don't have to do it with recursion, why do we need to divide the array into smaller arrays? Aside from that, lets say you have knowledge of all the array sizes, and that they are all the same size, then you would use the following code fragment to figure out the median, assuming also it is an array of words:
add $t4, $zero, $zero
addi $s0, $s0, 2 # will be useful later
la $t0, size # size of the array, I just called it size
lw $t1, 0($t0) # get the size
div $t1, $s0 # divide the size by 2
mfhi $t2 # puts the remainder from the previous divide in $t2
mflo $t3 # puts the quotient in $t3
la $t5, numbers # numbers is the name of your array
loopStart:
slt $t6, $t4, $t3
beq $t6, $zero, loopDone
addi $t5, $t5, 4
j loopStart
loopDone:
lw $t7, 0($t5)
# Print the median size
add $a0, $t7, $zero
li $v0, 1
syscall
That should work to find the median of an odd array, not an even one, that will require a check of the mfhi instruction and then doing additional calculations to figure out where you need to go in the array, if you really need that part explained you'll have to wait till tomorrow, also, the above code might be off by one, but it should be right. if you need anymore explanation just ask
Hi ,
Your code for finding out the median was really helpful. I am trying to figure out how to use the same code for a list of integers, even or odd does not matter. Also I am trying to set up a bootloader program in MIPS. I have three option that should show on the MENU whe I start the program -
Division
Mean
Median
I have got division and mean to work and I am working on Median. But can you help me out with how to write the bootloader program. Please let me now if you need any clarifications. You r help will be gratly appreciated
If you don't have to do it with recursion, why do we need to divide the array into smaller arrays? Aside from that, lets say you have knowledge of all the array sizes, and that they are all the same size, then you would use the following code fragment to figure out the median, assuming also it is an array of words:
That should work to find the median of an odd array, not an even one, that will require a check of the mfhi instruction and then doing additional calculations to figure out where you need to go in the array, if you really need that part explained you'll have to wait till tomorrow, also, the above code might be off by one, but it should be right. if you need anymore explanation just askadd $t4, $zero, $zero addi $s0, $s0, 2 # will be useful later la $t0, size # size of the array, I just called it size lw $t1, 0($t0) # get the size div $t1, $s0 # divide the size by 2 mfhi $t2 # puts the remainder from the previous divide in $t2 mflo $t3 # puts the quotient in $t3 la $t5, numbers # numbers is the name of your array loopStart: slt $t6, $t4, $t3 beq $t6, $zero, loopDone addi $t5, $t5, 4 j loopStart loopDone: lw $t7, 0($t5) # Print the median size add $a0, $t7, $zero li $v0, 1 syscall
Hi , Your code for finding out the median was really helpful. I am trying to figure out how to use the same code for a list of integers, even or odd does not matter. Also I am trying to set up a bootloader program in MIPS. I have three option that should show on the MENU whe I start the program - Division Mean Median
I have got division and mean to work and I am working on Median. But can you help me out with how to write the bootloader program. Please let me now if you need any clarifications. You r help will be gratly appreciated
Unfortunately I can't help you, we never had to write a bootloader in our class so I have no experience with it, my book doesn't even make any mention of it. Sorry.
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
