0

I'm trying to compute modulo , where may be really huge: up to 10^18 , is n-th Fibonacci number Here's my code , it works well for small numbers but for big numbers it is throwing OutOfMemoryError or NegativeArraySizeException.

import java.util.*;

public class FibonacciHuge {
private static long getFibonacciHugeFast(long n, long m) {
long[] arr = new long[(int) n + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n + 1; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % m;
}
return arr[(int) n];
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
System.out.println(getFibonacciHugeFast(n, m));
}
}
samgak
  • 23,944
  • 4
  • 60
  • 82
Amit Singh
  • 1,790
  • 3
  • 17
  • 27
  • Can you show us the first say 10 numbers in the sequence? – Tim Biegeleisen Sep 21 '16 at 02:28
  • Array sizes would seem to be bound by `Integer.MAX_VALUE` as [this SO answer](http://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size) discusses. Using `10^18` as the value of `n`, which is _much_ larger than `2^32`, should cause an error. – Tim Biegeleisen Sep 21 '16 at 02:32
  • 2
    You may not need array to calculate the nth fibonacci number. Try `private static long getFibonacciHugeFast(long n, long m) { long first = 0; long second = 1; long value = 0; for (int i = 2; i < n + 1; i++) { value = (first + second) % m; first = second; second = value; } return value; }` – Raghav Sep 21 '16 at 02:32

3 Answers3

1

Here's an explanation of your two exceptions/errors.

  1. OutOfMemoryError exception: Due to the fact you're trying to create an array that is HUGE, well past the possible size. Refer to this question Do Java arrays have a maximum size?
  2. NegativeArraySizeException: Due to the fact you're casting a long into an integer (the code long[] arr = new long[(int) n + 1];). Read this: Primitive data types. (Basically you're overflowing at some point and the resulting integer is a negative number)
Community
  • 1
  • 1
silentwf
  • 153
  • 2
  • 8
1

If n can be 10^18, then even if you don't use an array, it will still time out, as you are going to run a loop till n (which is 10^18) to calculate the nth fibonacci number.

You can use the matrix exponentiation method (linear recurrence method). You can find detailed explanation and procedure in this blog. Run time is O(log n).

Hope this helps!!!

User_Targaryen
  • 4,125
  • 4
  • 30
  • 51
1

There are two problems with your code

  1. You only need to know fibonacci elements n-1 and n-2 in order to compute element n, so you don't need an array but just two variables.
  2. You can compute the n-th element modulo m from the n-1 and n-2 elements modulo m, since (a + b) % m == (a % m + b % m). In fact, you wouldn't be able to store the 10^18th fibonacci number in a long, since its value is huge - the fibonacci sequence grows exponentially. The only issue you might have with this is if a % m + b % m overflows, so you should limit m to be Long.MAX_VALUE / 2, since you don't know how large the actual element will be just from knowing n. Or alternatively you could add an overflow check in your function.
D Levant
  • 116
  • 7