I need help with this assignment. The classic fibonacci calculation can also be

Question

I need help with this assignment.

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 "theBigFib" 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.

Re-write a better recursive calculation, using BigInteger from the Java API http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html (Links to an external site.)

This means you should return BigInteger from theBigFib method.

Also note I use Class name all start upper case, methods and objects start lower case.

Requirements:

theBigFib method MUST be a recursive, and/or use a recursive helper.

leave the text provided (reprinted below) fibonacci method in your Fibonacci Class, so the listing below will work.

start with class listing below, and add in "public static theBigFib" a method.

do NOT rely on Class fields, nor class constants (nor global variables), as I will test your method with external testing code.*** (see note below)

theBigFib should be an overloaded method, meaning it can accept either int or BigInteger, with the fancy math is all in one of the methods, and the other just calls that method. Either way, a BigInteger is always returned from theBigFib method.

public class Fibonacci {
   public static void main(String[] args) {
       int test = 45; // I will limit my test code to passing int parameters
        BigInteger test2 = new BigInteger("45"); // only needed for overload
        System.out.println(theBigFib(test)); // a fast recursive version
        System.out.println(theBigFib(test2)); // overload, using same as above
        System.out.println(fibonacci(test)); // slow version in text   
   }
  
   public static int fibonacci(int n) {
       if (n<=2) {
           return 1;
       } else {
           return fibonacci(n-1) + fibonacci(n-2);
       }
   }

Explanation / Answer

If your only motto is to find the large fibonacci numbers then the below code will definitely solve your problem. Its a recursive implementation, answers is an array that stores already computed answers, thus preventing multiple calls to fibonacci with the same argument. This is the key to speeding up Fibonacci. Fibonacci(n) is stored in slot n-1 in answers(Kind of dynamic programming). import java.math.*; import java.io.*; public class Fibonacci { private static BigInteger[] answers; private static BigInteger one; private static BigInteger zero; private static BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) ); public static BigInteger fastFibonacci(int n) { if((n == 1) || (n == 2)) return answers[0]; if(answers[n-1].compareTo(zero) != 0) return answers[n-1]; if(answers[n-2].compareTo(zero) == 0) answers[n-2] = fastFibonacci(n-1); if(answers[n-3].compareTo(zero) == 0) answers[n-3] = fastFibonacci(n-2); return answers[n-2].add(answers[n-3]); } public static void main(String[] args) { int n; long time, newTime; BigInteger answer; System.out.println("Type a positive integer." ); try{ String input = stdin.readLine(); n = Integer.parseInt( input ); zero = new BigInteger("0"); BigInteger("1"); // Initializing answers answers = new BigInteger[n]; answers[0] = new BigInteger("1"); answers[1] = new BigInteger("1"); for(int i = 2; i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---