SUBMIT Fibonacci.java

Make a new method called bigFastFib and rewrite a better recursion using BigInteger from the Java API:

http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html (Links to an external site.)Links to an external site.

It will be tested using FibDriver.java:

FibDriver.java

import java.math.BigInteger;

public class FibDriver {

public static void main(String[] args) {

Fibonacci test = new Fibonacci(42); // only needed for overload

System.out.println(test.bigFib()); // same as above, but use BigIntegers this one takes a very long time to get output

System.out.println(test.bigFastFib()); // same as above, but MUCH faster This is the one you are testing

}

}

USE THE GIVEN STARTER CODE:

Fibonacci.java

import java.math.BigInteger; public class Fibonacci { // fields, ONE is in any version of Java already // but BigInteger.TWO requires Java 9 or higher, so I make one here private final BigInteger TWO = new BigInteger("2"); private final BigInteger ONE = new BigInteger("1"); private int n; // the boring old 32-bit limited int // only one constructor needed public Fibonacci(int number) { n = number; }

// recursive helper private BigInteger bigFib(BigInteger n) { if (n.compareTo(TWO) }

Now do the same things as the private BigInteger bigFib(BigInteger n) but make a faster version that is still recursive, but far more efficient, and can handle very BIG int's.

The classic Fibonacci calculation can also be done recursively (code below),but is VERY slow. YOUR TASK: Write a faster version that is still recursive, but far more efficient, and can handle very BIG int's. Call your new improved method "bigFastFib" and get the code shown below to work. You should discover that the 45th Fibonacci number (1134903170) takes a long time to calculate with the provided code (like 10 seconds) and the 46th takes even longer The 47th exceeds the size of allowable primitive int in Java. So we need significant changes in this code First, we need to change int to Biginteger, which is a very interesting Class from Oracle, using an int[ ] for the digits of a Biglnteger object, so the size is unlimited. Maybe you did this back in Chapter 7 programming projects? Anyway time to brush up on how Biglnteger works, a lesson in good object oriented programming, like no +operator, but returns result from .add method Second, we need to get rid of the double recursive call shown by our textbook "fibonacci(n-1)+fibonacci(n-2);" which makes twice as many recursive calls for each number you move up, so the 12th Fibonacci number has just 2412 calls but the 45th number has 2A45 calls and takes forever to run.. Re-write a better recursive calculation, using Biginteger from the Java API http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html z This means you will need to pass and return a Biglnteger from bigFastFib method. Requirements: 1. bigFastFib method MUST be recursive, and/or use a recursive helper. 2. Leave the textbook provided Fibonacci methods in your Fibonacci Class, so my FibDriver listing below will work. 3. Start with my Class Fibonaccijavaand add in a "public bigFastFib" method. 4. No static fields are allowed, and adhere to my Class (data structure) Submission Requirements O NOT add additional Class fields, nor class constants (nor global variables). 6. I will test your code to find some Fibonacci number past the 300th, and I can only wait seconds