Programming Assignment 2

Due: November 5th, 11:59 pm

Yale N. Patt, Instructor

TAs:Stephen Pruett, Siavash Zangeneh, Aniket Deshmukh, Zachary Susskind, Meiling Tang, Jiahan Liu

You must do every programming assignment ** by yourself**. You are permitted to
get help ONLY from the TAs and Dr. Patt. When you have completed the
program, and tested it sufficiently so that you are comfortable that it
works on any input, submit it for grading according to the submission
instructions at the end of this handout.

__
Programming Assignment 2: Find the zeros of a polynomial.
__

**Background:**
The zeros of a polynomial f(x) are the values of x for which
f(x) = 0. In an interval (xlow, xhigh), a monotonic function f(x) has
a zero in that interval if either of the following two things are true:

a. f(xlow) is postive and f(xhigh) is negative, or

b. f(xlow) is negative and f(xhigh) is positive.

In the first case, we say the function f(x) is monotonically non-increasing
in the interval because in the interval, f(x) never increases in going from
xlow to xhigh. Figure 1 is an example of a monotonically non-increasing
function in the interval.

In the second case, we say the function f(x) is monotonically non-decreasing,
because in the interval, f(x) never decreases in going from xlow to xhigh.

**Your Job:**
Given an interval (xlow, xhigh), a function f(x) that is monotonic
in that interval, and either f(xlow) is positive and f(xhigh) is negative or
f(xlow) is negative and f(xhigh) is positive, write an LC-3 assembly language
program that uses binary search to find the zero of f(x) in the interval
(xlow, xhigh), and store that value of x in x4000.

Input to your program will be found in a table in memory, starting at x4001:

Address | Content |
---|---|

x4001 | xlow |

x4002 | xhigh |

x4003 | degree of the polynomial, say n |

x4004 to x4004 + n | polynomial coefficients |

(Updated on 11/04/17)

All values in the table are 2's complement integers.

For example, if f(x) is the polynomial Ax^3 + Bx^2 + Cx + D, the table will
take the form:

Address | Content |
---|---|

x4000 | output: x-position of zero |

x4001 | left bound |

x4002 | right bound |

x4003 | degree: 3 |

x4004 | A |

x4005 | B |

x4006 | C |

x4007 | D |

To evaluate the polynomial, you will need to write a subroutine that computes the value of f(x). This must be written as a subroutine. The starting address of the subroutine should be location x5000. The main program should put the value of x into R0 BEFORE calling the subroutine. The subroutine will take the value in R0 and the coefficients stored in memory and compute the value f(x). The subroutine will place f(x) in R4 before returning to the main program. All other registers (other than R7) should remain unchanged. Your subroutine should work exactly as described.

Polynomial | Interval | Output |
---|---|---|

f(x) = 2x + 6 | (-100,100) | -3 |

f(x) = 4x - 8 | (-100,100) | 2 |

f(x) = x^{2} - 4x |
(2,100) | 4 |

f(x) = x^{2} - 4x |
(-100,2) | 0 |

f(x) = 4x^{2} - 12x - 16 |
(2,50) | 4 |

f(x) = x^{3} - 15x^{2} + 75x - 117 |
(-20,20) | 3 |

**Binary Search:**
In our program a user specifies an interval of the function that is
monotonic. If f(xlow) is positive and f(xhigh) is negative, then we know
that a zero of the polynomial must exist between the two bounds. We can
search for the zero by using a **binary search**. In a binary search,
we start by dividing the interval into two halves as shown in Figure 1.
We can test the polynomial evaluated at the mid-point of the interval
(f(xmiddle)) to see if it is positive, negative or zero. If it is zero,
then we are done. If the value is not zero, then we can narrow our
search to the interval between xmiddle and the appropriate bound such
that the new interval will still contain the zero. In the case of the
Figure 1, we can narrow our search to the interval (xlow, xmiddle)
because we know that this interval contains the zero. We can discard the
interval (xmiddle, xhigh) because we know that it does not contain the
zero. This process can be repeated until the zero is found. Question:
Why does this algorithm lead to the fewest number of calls (on average)
to the f(x) subroutine?

**You may assume:**

**Hints:**

**Submission Instructions:** The main program and the subroutine
should be submitted as two separate files. The main program should be
called **search.asm** and the subroutine should be called
**function.asm**. You MUST name your files EXACTLY as specified.
Failure to do so will result in a loss of points on the assignment. The
two .asm files should be submitted to Canvas by the deadline.