i need help with this assignment. need to do with an private helper method. No b
ID: 3786589 • Letter: I
Question
i need help with this assignment. need to do with an private helper method. No buffer reader please.
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
import java.io.*;
//class name Fibonacci
public class Fibonacci
{
//declaring private variable numbers array as BigInteger data type
private static BigInteger[] numbers;
//declaring private variables one,zero as BigInteger data type
private static BigInteger one;
private static BigInteger zero;
private static BufferReader stdin = new BufferedReader( new InputStreamReader( System.in ) );
public static void main(String[] args)
{
BigInteger answer;
numbers = new BigInteger[n];
numbers[0] = new BigInteger("1");
numbers[1] = new BigInteger("1");
for(int i = 2; i < n; i++)
numbers[i] = new BigInteger("0");
int test = 45;
BigInteger test2 = new BigInteger("45");
System.out.println(theBigFib(test)); // a fast recursive version
System.out.println(theBigFib(test2)); // using overload
System.out.println(fibonacci(test)); // older version for test
}
//older version
public static int fibonacci(int n)
{
if (n<=2)
{
return 1;
} else
{
return fibonacci(n-1) + fibonacci(n-2);
}
// theBigfib method taking int parameter and returns BigInteger data type
public static BigInteger theBigfib(int n)
{
// numbers[0] is initialized to 1.
if((n == 1) || (n == 2))
return numbers[0];
if(numbers[n-1].compareTo(zero) != 0)
return numbers[n-1];
if(numbers[n-2].compareTo(zero) == 0)
numbers[n-2] = theBigfib(n-1);
// Find fibonacci(n-2), either by
// looking it up in numbers[n-3] or computing it for the first time
if(numbers[n-3].compareTo(zero) == 0)
numbers[n-3] = theBigfib(n-2);
return numbers[n-2].add(numbers[n-3]);
}
}//class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.