This assignment will give you more practice with functions in MIPS. It will also give you a chance to use MIPS instructions for (single precision) floating point variables. Finally, it will give you some experience with making your code efficient, both in terms of the number of instructions as well as with the use of the cache. The main problem is to write a MIPS functions that computes the root of a polynomial, using the bisection method. A recursive version of the algorithm is shown below. Note this is a tail recursive algorithm, which means the recursive call occurs at the end. Tail recursive algorithms can be written alternatively as an iterative algorithm using a loop. You will need to write both recursive and iterative versions. The idea underlying the algorithm is that if f(x) is any continuous function over an interval [a,c] and f(a) and f(c) are of opposite sign, then there must exist at least one value b in the interval [a,c] such that f(b)=0. In the case that f(x) is a polynomial p(x), we say that the value b is a root of the polynomial. The algorithm finds one such root. (There may be many roots in a given interval. The algorithm finds one.) findRoot(a,c) { b = (a + c) / 2 if(p(b)==0) return b else if ( abs(a - c) < epsilon) return b elseif(p(a)*p(b)>0) a=b else c=b return findRoot(a,c) } // assume p(a) and p(c) are of opposite sign // bisarootofp(x) // epsilon is a given constant // aandbhavethesamesign Function calls must obey MIPS register conventions. For floats, these conventions are: o $f0, ... $f3 are used to return float values from functions o $f4, ..., $f10 are temporary registers o $f12,...,$f15 are used for passing float arguments to functions o $f20,...,$f30 are save registers Notice that these conventions are different than for integer valued arguments and returned values. However, the same principles apply: return value registers and temporary registers are not preserved on function calls so parent much save them if parent needs them, and save registers and argument registers are preserved on call so child must save and restore old values if child uses these registers. In this assignment, we work with single precision only.

You are provided with two helper functions. The first of these evaluates a polynomial. The second is the power function which evaluates x^n. [ASIDE (for your interest only): There exist more efficient methods for evaluating polynomials, e.g. Horners method. There also exist faster methods for computing the power x^n. Here we use a O(n) method to compute power(x,n) but there is an asymptotically faster method, namely O(log n), which you may have learned in COMP 250. http://www.cim.mcgill.ca/~langer/250/11-binarysearch.pdf The algorithm described there is recursive, however, and so there are extra instructions associated with using stack which could make it more expensive than the O(n) in practice unless n is huge. [ADDED April 6: But you can write that algorithm without recursion (see Pauls April 5 posting on the discussion board). ] Data directives are used to define the following constants. The constants are given in the starter code. POLYORDER is the order of the polynomial. The COEFFICIENTS of the polynomial are integers. The INTERVAL [a,c] is given by two single precision floats (a and c). EPSILON is the error tolerance for the solution according to the epsilon in the above algorithm. .data # define the polynomial POLYORDER: .word 3 # Order of polynomial. COEFFICIENTS: .word 1, -2, -1, 2 # Integer coefficient of highest order comes first in list # define the interval in which we search for the root, and the tolerance for the solution INTERVAL: .float -1.53, 0.51 # Find a root between these values. EPSILON: .float 0.000001 # Value e in algorithm above. For example, the polynomial represented here is p(x) = x^3 -2x^2 - x + 2. It has roots x = -1, 1, 2. When we test the correctness of your code, we will change the values of these constants. Only valid constants will be tested. The main program (starter code) calls a findRoot function that you will write which returns a root of a given polynomial p(x) in a given interval [a,c] with precision EPSILON, namely the absolute difference between of the returned value from the true root must be at most EPSILON. The polynomial p(x) is evaluated using a helper function evaluate(x) which in turn calls the power function mentioned earlier. Question 1 (50 points): Write a recursive MIPS function findRoot that implements the above algorithm. Your function may call the helper function evaluate. Note that evaluate has access to the names POLYORDER, COEFFICIENTS but the function that you write does not. Rather we are insist that you pass only the arguments a, c, and epsilon. The two arguments a, c, epsilon of findRoot are single precision floats. They are passed in registers $f12, $f13, $f14 respectively. The root is returned in register $f0. Submit your recursive solution as a file findRootRecursive.asm (no starter code).