MIPS/assembly language questions

Discussion in 'OT Technology' started by mrburner, Oct 5, 2003.

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    alright, i have this program due in my mips class that is a rewrite of an older program i did just this time with slightly different requirements and i don't really understand exactly how i should be modifying my old code so any help on explaining this better or getting me started would help me out very much

    description: redo program 2, but using a recursive binary search algorithm. in this case, clearly the array's elements must be sorted in ascending order

    requirements: your program must use a recursive function to do the search
    the function is to be passed four parameters:
    1. the base address of the array to search
    2. the lowerbound index for the search space
    3. the upperbound index for the search space
    4. the target value to search for
    the function must return -1 on failure and the index of target on success

    i can post up my old code if that would help anyone...thanks in advance
     
  2. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    0
    Location:
    Edmonton, AB
    In a binary search, you divide a set of data into two halves, then check whether what you're searching for is above the middle or below the middle. Then you do it again with the side it's on, and again and again until you either find what you're searching for or determine that it's not in the set. I don't know ASM, so I can't help with the actual coding, but hopefully that helps you :)
     
  3. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    since you obviously know c pretty well...is there any chance you can give me an example of this in c++ because i've been trying to think of how to divide the array into 2 halves

    so basically my last program was to search for and find a value in an unordered array using a linear search

    now is this new program something that can just be rewritten from my old one easily or does doing a recursive binary search algorithm something that will change basically every part of the program? because to me it seems that it is pretty similar
     
  4. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    A binary search only works if the array is sorted. It works like this:

    1) Given a lower and upperbound index within which to search, the first thing to do is check if lowerbound == upperbound in which case the search function is being asked to look at only one element in the array. Check if array[lowerbound] == targetvalue and return either -1 or lowerbound.
    2) If lowerbound < upperbound check the midpoint element (i.e. the element at index (lowerbound + upperbound)/2). Since the array is sorted, if the value of the midpoint element is less than targetvalue, then search again in the upper half of the array bounded by midpoint+1 and upperbound. If the midpoint is greater than the target value, then search again in the lower half of the array bounded by lowerbound and midpoint.

    Step 2 is where it gets recusive because the search function is calling itself with different array bounds.

    The description should be enough for you to come up with your own C/C++ code which you can use to translate to ASM.
     
  5. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    but based on that...i don't understand how to make my array split into a lowerbound and upperbound...do i just have 2 seperate arrays? also something i forgot to mention is that i program in what is in the array...when the program is run, the user inputs a value and the program returns what spot in the array the target value is at
     
  6. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    The upper and lowerbound are just array indices that define a range in which to search. You're not creating two new arrays, you're just logically dividing the array by defining two separate ranges.

    Suppose you have a 10 element array. To search the entire array, the lower and upperbound would be 0 and 9 respectively. The algorithm says compare the targetvalue with the element at the midpoint of the range. In this case (0 + 9)/2 = 4. So compare array[4] with target value. If targetvalue is greater, then if targetvalue is contained in the array, it must be somewhere between index 5 and 9. So, you call the search function recursively using 5 and 9 as the lower and upperbound. If targetvalue is less, then search the range from 0 to 4. This process continues until you reach a point where lower and upperbound are the same, so you've narrowed your search to one element. Now if this element is equal to the targetvalue, you return the index, otherwise return -1.
     
  7. samm

    samm Next in Line

    Joined:
    Dec 22, 2000
    Messages:
    2,630
    Likes Received:
    0
    Location:
    San Jose, CA
    If you are writing this in C, what does this have to do with MIPS?
     
  8. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    i'm not writing it in c but most people you talk to will reccomend that you write ASM instructions in a high level language first and then transfer it over
     
  9. Ballast

    Ballast Cold Heartless Bastard

    Joined:
    Aug 9, 2001
    Messages:
    7,489
    Likes Received:
    23
    Location:
    London, Ontario
    really?? in my sparc assembly class we just wrote psuedo-code for the algorithm, and then programmed from there....
     
  10. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    hmm...it even suggests doing it in my book
     
  11. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    pseudo-code or C, doesn't matter, serves the same purpose.
     
  12. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    skinjob...hope you're still on this late at night...or anytime in the morning before i wake up

    how does this look for the c++ version of the code? i came up with one while i was at work tonight but then i went searching online and found another one that is semi-different...of course i just wrote these and then coded them in using wordpad so the formatting is probably gonna be off

    int bsearch(int array[], int lower, int upper, int target)

    {

    int mid;

    if(lower > upper) return -1;

    mid = (upper + lower)/2;

    if(array[mid] == target) return array[mid];

    else if(array[mid] > target) return bsearch(array, lower, mid-1, target);

    return bsearch(array, mid+1, upper, target);

    }


    here is the other one i found online

    void binary_search(apvector <int> &array, int lowerbound, int upperbound, int key)

    {

    int search_pos;

    search_pos = (lowerbound + upperbound) / 2;

    while((array[search_pos] != key) && (lowerbound <= upperbound))

    {

    if(array[search_pos] > key)

    {

    upperbound = search_pos - 1;

    }

    else

    {

    lowerbound = search_pos + 1;

    }

    search_pos = (lowerbound + upperbound) / 2;

    }

    }





    now...i talked to my professor this afternoon and he said i should be using stacks for this program...i have no idea how stacks would relate to this at all...any ideas? and do you have any tips on converting this over to mips? i usually have trouble with that

    my mips program is due on wednesday or later (it is supposed to be due wednesday but the professor is fairly flexable and doesn't take off too many points if it's late)...but i'd like to get it done by wednesday if at all possible...so do you have any pointers on transferring this over to mips? thanks again for all the help
     
  13. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Your function looks like it should work. The second function you found isn't recursive.

    You don't need a stack data structure to implement the search algorithm, but since you are trying to write assembly language code that calls a function (itself), your prof maybe talking about the call stack. I don't remember much of asm, but I know you need to push function arguments onto the call stack and maybe a return address before you jump to the function address.

    Your code should be pretty simple. Compare the arguments, and if needed, push the appropriate arguments onto the call stack and call (jump) the function recursively.
     
  14. samm

    samm Next in Line

    Joined:
    Dec 22, 2000
    Messages:
    2,630
    Likes Received:
    0
    Location:
    San Jose, CA
    skinjob is right, all arguments to functions in assembly code are pushed onto the stack. To execute a function, call the jal (jump and link) instruction to whatever pc address you decide to start you function. Then, do a jr (jump register) to whatever register is written by the jal instruction to return from your function call.
     
  15. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    is there any way you can give me an example of how to even push a stack in mips...like what the command could be?
     
  16. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Here's something I found on google

    http://www.cs.sunysb.edu/~cse320/example.html

    Take a look at example 2:

    There is a register called the stack pointer that contains the current address of the top of the stack. In MIPS, it looks like it's called $sp. You just copy the value you want to push on the stack to the address pointed to by $sp, then move the stack pointer so it points to the next available spot on the stack.
     
  17. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    alright, i'm getting into writing the program and don't know how to do a mips statement splitting the main array into 2 parts...how do you do division in mips? i am only finding addition and subtraction
     
  18. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    nevermind...found how to do division

    now i am having trouble indexing into the array...like how do i say the array divided by 2 and if the input is less than that value to do something...and if the input is greater than it to do something else
     

Share This Page