How to determine the highest number of fibonacci

Question

I was asked to determine the largest number of fibonacci that can be displayed on my system, and I am wondering how to do it.

here is my simple application that determines the nth fibonacci number

import java.util.Scanner; public class FibonacciTest { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.printf("please enter the nth fibonacci number: "); int n = input.nextInt(); System.out.printf("%d\n", fibonacci(n)); }// end main public static int fibonacci(int n) { // determines nth fibonacci number int fib = 1; int temp = 0; if (n == 1) return 0; else { for (int i = 2; i < n; i++) { int last = fib; fib += temp; temp = last; } return fib; } }// end fibonacci } 

Answer 1

determine the largest number of fibonacci that can be displayed on my system

For this you need to use BigInteger

Run this until your application stops because you have run out of resources.

 public static void main(String... args) { BigInteger a = BigInteger.ONE; BigInteger b = BigInteger.ONE; String last = null; try { for (long count = 1; ; count++) { BigInteger c = a.add(b); last = c.toString(); a = b; b = c; if (count % 10000 == 0) System.out.println("... " + count); } } catch (Throwable e) { System.out.println("The largest value which was calculated was"); System.out.println(last); } } 

I would try it with a minimum amount of memory, for example, -mx16m

Update: even with a limit of 16 MB, it calculated 13 thousand terms and continues to work.

Answer 2

The maximum number of Fibonacci int in Java:

 public class FibonacciTest { public static void main(String[] args) { System.out.printf("%d\n", largestFibonacciInt()); } public static int largestFibonacciInt() { int temp; int last = 1; int fib = 1; while (fib + last > fib) { temp = fib; fib += last; last = temp; } return fib; } } 

You can also do this with long , simply replacing all occurrences of int .

Answer 3

If your goal is to find the largest fibonacci number that can be represented as an int in Java, you can simply calculate the following number until it overflows:

 public static void main(String[] args) { System.out.println("Largest integer Fibonacci number: " + maxFibonacci()); } public static int maxFibonacci() { int n = Integer.MAX_VALUE; int fib = 1; int temp = 0; for (int i = 2; i < n; i++) { int last = fib; fib += temp; if (fib < 0) return last; //overflow, we are done temp = last; } return 0; //unreachable } 

Now, obviously, your system can calculate a much larger number, for example, using BigInteger. In this case, the limit will be one of the following:

• time of processing
• available memory or
• (if you have a lot of memory and a lot of time) BigInteger restriction, which is supported by int[] and therefore is limited by the size of the array 2 ^ 31.

---

Finally, it is probably worth saying that your problem can be solved mathematically.

If you need to find the largest Fibonacci number that is less than a certain number N , you can also use rounding calculation :

 phi^n / sqrt(5) < N 

which gives you:

 n < log(N x sqrt(5)) / log(phi) 

Then you can calculate the right side for your chosen N , round it to find N , and calculate the corresponding Fibonacci number with:

 F(n) = floor(phi^n / sqrt(5)) 

Answer 4

You can calculate a value of 100K or even more. For 100k on my computer, it only takes 1.4 seconds to calculate the result.

 private static final Map<Integer, BigInteger> fbNumbers = new HashMap<>(); public static void main(String[] args) { fbNumbers.put(0, BigInteger.valueOf(1)); fbNumbers.put(1, BigInteger.valueOf(1)); long start = System.currentTimeMillis(); System.out.println(fbCalculationForBigNumbers(100000)); System.out.println(String.format("%d ms", System.currentTimeMillis() - start)); } private static BigInteger fbCalculationForBigNumbers(int num) { return IntStream.rangeClosed(0, num).mapToObj(i -> fbCalculation(i)).max((x,y) -> x.compareTo(y)).get(); } private static BigInteger fbCalculation(int num) { if (fbNumbers.containsKey(num)) { return fbNumbers.get(num); } BigInteger result = fbCalculation(num - 1).add(fbCalculation(num - 2)); fbNumbers.put(num, result); return result; }