Assignment 5: Numeric Computation

As you may have noted, Math.sqrt only accepts values of type double. What happens if we want to compute the square root of a BigDecimal? One possibility is that we could convert the BigDecimal to a double, compute the square root, and then convert back. Unfortunately, that technique essentially eliminates the benefit of BigDecimal values - that they can be more accurate than double values.

The alternative is to write our own procedure. Fortunately, there is a well-known algorithm for computing square roots, the Newton-Raphson method. The algorithm starts with some approximation of the square root and repeatedly improves that approximation until the approximation is “good enough” (less than some specified amount, which we typically call “epsilon”).

Suppose we are computing the square root of a number n, and our current approximation is a. How do we improve a? We take the average of a and n/a. Note that this is a very sensible way to improve approximations because (a) if the approximation is already correct, a and n/a will be the same, so the approximation will remain correct; (b) if a is too small, n/a will be too large, so the average will be closer to the root; (c) similarly, if a is too large, n/a will be too small.

What approximation should we start with? 1.0 or even n while a bit absurd, will work acceptably well.

Write and test Utils.sqrt(BigDecimal d, BigDecimal epsilon). (You need not supply your tests.)

Warning: Unfortunately, division with BigDecimal values is less straightforward than it should be. You may need to take some time to read over (and understand) the different forms of division.

Note: There are at least two ways you can decide whether a value, a, is a reasonable estimate for the square root of n. You can compare the square of a to n. You can also compare a to n/a.

Many students write functions to compute xⁿ using loops, which means that they do approximately n multiplications. As algorithm designers, we should ask whether we can solve the problem more efficiently.

The lab on debugging contains a significantly more efficient algorithm for doing exponentation. However, that algorithm is recursive and some companies have policies that strongly discourage the use of recursion. Recursion also adds a bit of additional overhead (unless you use tail recursion and have a competent compiler).

Rewrite the algorithm iteratively.

Are you done? You can be. However, you may earn a bit of extra credit if you can identify an even more efficient way to do exponentiation. (To be more efficient, the number of steps in your algorithms will likely need to be independent of both the value and the exponent. That means you can't use loops or recursion.)

In a previous assignment, you implemented a simple calculator by writing a method that takes a string as input, parses the string, evaluates the parsed string, and returns the computed value.

While that calculator is useful, there are certainly many opportunities to improve its design. One natural extension is to include “storage elements” (variables, registers), so that you can name the result of a computation and use it in a future computation.

Implement a class, Calculator, that supports simple calculations using fractions and integers. Your calculator should support at least eight storage elements, labeled r0 ... r7.

In particular, you calculator class should support evaluate(String expression), where expression is either an expression over fractions, integers, and storage elements or an “assignment” of the form ri = expression.

Note that evaluate should throw an appropriate exception if the expression is malformed. (Ideally, you should find a way to indicate the location of the error in the expression.)

Since your calculator is stateful, it makes sense to write a template class. That way, we can create multiple independent calculators.

Here's an example of a sequence of calls to evaluate.

  Calculator calc = new Calculator();
  calc.evaluate("2 + 3");               // Output: 5
  calc.evaluate("2 + 3 * 4");           // Output: 20 (or 14)
  calc.evaluate("r0 = 2 + 3");          // Output: 5
  calc.evaluate("r0 + 2");              // Output: 7
  calc.evalaute("r0");                  // Output: 5
  calc.evaluate("r1 = r0 * r0");        // Output: 25
  calc.evaluate("r1 + r0 * 2");         // Output 60 (or 35)

Create a user interface for the calculator. Your interface will primarily use the read-eval-print loop (aka REPL): read an expression, evaluate that expression, print the result, and do it all over again. You should find a nice way to report errors that the program encounters (e.g., division by 0).

Good designers separate program logic from the underlying computation. Please try to design your program so that it's easy to “swap out” one interface and to “swap in” another one. For example, you might think about what methods should be in the Calculator class so that we could use it with a graphical user interface instead of a textual user interface.

Here's a sample session with one UI.

> 2 + 3
5
> r0
r0 is currently undefined
> r0 = 2 + 3
5
> r1 = r0 * r0
25