Assignment #2 Solution

Recursion (10 points)







Create a file called `Factorial.java`. This file should have the following method:




`public static long calculate(long n)`




`Factorial.calculate` should recursively calculate `n!`, where `0! = 1` and `n! = n(n − 1)!`. The method should also print out an error and exit if `n < 0` or `n 20`, since factorial is not defined for negative numbers and will overflow Java’s long variable with larger numbers (if we used an int, it would overflow even sooner!).




Inside `Factorial.java`, also include a `main` method which runs a couple of tests on `Factorial.calculate`:




```sh

java Factorial

Factorial.calculate(0) returned 1. Test passed!

Factorial.calculate(5) returned 120. Test passed!

```




(Obviously, if these tests do not return 1 and 120 respectively, the tests should fail and print out an appropriate message.)




Fibonacci revisited (10 points)




Create a file called `FibTest.java`. Refactor your `Fib.java` from assignment 1 to be a `static` method in `FibTest`. Odds are that your assignment 1 answer is coded in iterative style, where you are looping from `1` to `n` and adding up numbers as you go. If not, you should write an iterative Fibonacci calculator that does so (and refactor the version that you wrote for assignment 1 for the next part of the problem). This method should be called:




`public static int fibIter(int n)`




The recurrence relation for the Fibonacci sequence is the following:




```

f ib(1) = 1

f ib(2) = 1

f ib(n) = f ib(n − 1) + f ib(n − 2)

```




Write another `static` method in the same `FibTest` class, this time in recursive style, using this relationship.




`public static int fibRecur(int n)`




In FibTest’s `main` method, write a series of tests that establishes that both of these functions work correctly. Finally, using Java’s `System.currentTimeMillis()` function, print out the time it takes to execute `FibTest.fibIter(40)` and `FibTest.fibRecur(40)`.




Pi Revisited (10 points)




In Assignment 1, you used the Gregory formula to compute an approximation of π. Here, you will use Ramanujan’s series, discovered in 1910. It converges much faster than Gregory’s, and has been used to calculate π to billions of digits. Implement `Ramanujan.java` exactly like `Gregory.java`, taking a number n specified by the user on the command line and calculating π using the first `n` terms of the Ramanujan series. The program should print this approximate value of π, as well as the percentage error between this value and the one provided by Java in the constant `Math.PI`.








Notice that this formula makes use of the factorial function. Call your `Factorial.calculate` method from Problem 1.




**Extra credit:** Look at the Java API definitions of `BigDecimal` and `BigInteger`. Rework your Factorial and Ramanujan code (call the classes something else, like `RamanujanBig`, so that you don’t overwrite your regular-credit work) to use these instead, and calculate π to 100 digits or more. Note that, in order for the terms to be perfectly accurate, you also need a `BigDecimal` representation of √2. There is unfortunately no native library support for calculating this; however, you can implement it yourself using a `BigDecimal` version of the evaluate method you will write in Problem 6.

You will get a little extra credit simply by explaining (in comments in your Ramanujan code) how `BigDecimal` and `BigInteger` differ from ordinary doubles and ints, and why the latter are insufficient for calculating very precise values of π




Pi Revisited (10 points)




In Assignment 1, you used the Gregory formula to compute an approximation of π. Here, you will use Ramanujan’s series, discovered in 1910. It converges much faster than Gregory’s, and has been used to calculate π to billions of digits. Implement `Ramanujan.java` exactly like `Gregory.java`, taking a number n specified by the user on the command line and calculating π using the first `n` terms of the Ramanujan series. The program should print this approximate value of π, as well as the percentage error between this value and the one provided by Java in the constant `Math.PI`.








Notice that this formula makes use of the factorial function. Call your `Factorial.calculate` method from Problem 1.




**Extra credit:** Look at the Java API definitions of `BigDecimal` and `BigInteger`. Rework your Factorial and Ramanujan code (call the classes something else, like `RamanujanBig`, so that you don’t overwrite your regular-credit work) to use these instead, and calculate π to 100 digits or more. Note that, in order for the terms to be perfectly accurate, you also need a `BigDecimal` representation of √2. There is unfortunately no native library support for calculating this; however, you can implement it yourself using a `BigDecimal` version of the evaluate method you will write in Problem 6.

You will get a little extra credit simply by explaining (in comments in your Ramanujan code) how `BigDecimal` and `BigInteger` differ from ordinary doubles and ints, and why the latter are insufficient for calculating very precise values of π




Root finding (20 points)




The roots of a continuous function are points at which the value of the function is equal to zero.




If we happen to know a value for which the function is positive and another value for which it is negative, then we know for certain that somewhere between the two values lies a zero. In other words, if `f(a) 0` and `f(b) < 0`, then there exists a value `x` between `a` and `b` for which `f(x) = 0`.

This fact suggests that we can zero in on the value of `x` using the following algorithm, where epsilon is the amount of error we are willing to tolerate:




1. Compute x, where x is halfway between `a` and `b`, ie `x = (a+b)/2`.

2. If `|a − x| < epsilon` return `x`.

3. If `f(x)` has the same sign as `f(a)`, the root lies between `x` and `b`. Recursively perform the algorithm with `x` as the new `a`.

4. Otherwise, the root lies between `a` and `x`. Recursively perform the algorithm with x as the new `b`.




Write a class `FunctionTest.java` and implement the following method:




`public static double findRoot(double a, double b, double epsilon)`




Within `findRoot()`, use `Math.sin()` as the function to be evaluated. In your main function, print out the root of `sin(x)` that falls between 3 and 4, to within 0.00000001.




Does the number look familiar?




Polynomials (30 points)




Write a class `Poly.java` to represent polynomials (ie, functions of the form `ax^n + bx^(n−1) +· · ·+ cx^2 + dx + e)`.




Implement the following methods:




- `Poly(int[] coefficients)`: Constructor for an array of coefficients where `c[n]` is the coefficient of `x^n`. In other words, the polynomial `2x^5 + 3x^4 − 8x^2 + 4` would be represented by the array `[4, 0, −8, 0, 3, 2]`. This way, if I want to know the coefficient of `x`, I look at `c[2]`, and get `−8`. This convenience is worth the confusion that arises because we usually write arrays left-to-right starting from the smallest index, whereas we usually write polynomials left-to-right starting from the largest coefficient.




- `int degree()`: Return the power of the highest non-zero term

- `String toString()`: Overriding the `Object` class’s `toString` method, this should return a `String` representation of the polynomial using `x` as the variable, arranged in decreasing order of exponent and printing nothing for terms with a coefficient of zero. For example, the `Poly` represented by the array `[4, 0, −8, 0, 3, 2]` should return the string: `2x^5+3x^4-8x^2+4`

- `Poly add(Poly a)`: To add two polynomials, simply add together each scale degree in turn.

Thus, `(2x^5 + 3x^4 − 8x^2 + 4)` + `(x^3 + 4x^2 − 2x)` = `(2x^5 + 3x^4 + x^3 − 4x^2 − 2x + 4)`. Create a method that constructs and returns a new `Poly` object with a new coefficient array created by adding the coefficients of the current object and the Poly object a passed as an argument to the `add()` function.

- `double evaluate(double x)`: Return the value of the function at the point `x`. In other words, if the `Poly` object represents `2x^5 + 3x^4 − 8x^2 + 4` and `evaluate(2.0)` is called, the method should calculate `2(2)^5 + 3(2)^4 − 8(2)^2 + 4` and return `84`.







Within the `main()` method of the `Poly` class, create a series of tests which exercise each of these methods and report their success or failure.