Fibonacci sequence using BigInteger Does not yield an answer

Question

Im to find 100th element of a Fibonacci Sequence, I initially tried to store the value of numbers using an int but it overflowed and switched to negative values just like long.
Then I came across BigInteger I did get the solution using a simple for loop and an array to store the results, and access the previous elements.
Now as Im trying to do the same problem using recursion The program does not seem to be terminating. Am I missing something here? Or are BigInteger's not suggested to used with recursion?

Here is the code:

import java.math.BigInteger;

class Test {
  public static void main(String[] args) {
    BigInteger n = BigInteger.valueOf(100);
    System.out.println(fib(n));
  }

  public static BigInteger fib(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(1)) == 0 || n.compareTo(BigInteger.valueOf(1)) == -1)
      return n;
    return fib(n.subtract(BigInteger.valueOf(1))).add(fib(n.subtract(BigInteger.valueOf(2))));
  }
}

Going until 100 is just very long, and your method is not the best performant, as you compute a lot of values multiple times — azro, Feb 13 '21 at 13:36
How did you determine that the program is not terminating? You call `fib` 354224848179261915075 times, so that's gonna take a while, obviously. — Jörg W Mittag, Feb 13 '21 at 13:37
See how to make it faster [here](https://stackoverflow.com/questions/13826810/fast-fibonacci-recursion). — Sweeper, Feb 13 '21 at 13:38
@MrakVladar: Well, if we assume that `fib` only takes one clock cycle to execute (which is a pretty optimistic assumption, since a simple `ADD` of a `long` on a Core i9 already takes on the order of a dozen clock cycles) and we further assume that you have 4GHz CPU, then `fib(100)` will take roughly 2800 years. — Jörg W Mittag, Feb 13 '21 at 13:42
Write `if (n.compareTo(BigInteger.valueOf(1)) <= 0)` instead of `if (n.compareTo(BigInteger.valueOf(1)) == 0 || n.compareTo(BigInteger.valueOf(1)) == -1)`. `compareTo` is **not guaranteed to return -1** for a "less-than" result, only _some_ negative number. — Kevin Anderson, Feb 13 '21 at 14:27

score 2 · Accepted Answer · answered Feb 13 '21 at 14:12

In the comments, you mentioned that your assumption that the program doesn't terminate is based on the fact that it ran for over 5 minutes. That is not how you prove non-termination.

If you observe the program terminating within a certain amount of time, then you can conclude that it does, indeed, terminate. However, if you don't observe it terminating within a certain amount of time, then you can say precisely nothing about whether it terminates or not. It may terminate if you wait a little bit longer, it may terminate if you wait a lot longer, it may even theoretically terminate but take longer than the heat death of the universe.

In your specific case, the algorithm is perfectly correct, and it always terminates. It is simply not a very efficient algorithm: for computing fib(n), fib gets called fib(n) times, because you compute the same numbers over and over and over and over again.

If we assume that you can execute fib once per clock cycle (which is an optimistic assumption since a single call to fib performs one condition, two subtractions, one addition, and two calls to fib in most cases, and a single addition may already take multiple clock cycles depending on the CPU), and we further assume that you have a 100 core CPU and your code is actually executed in parallel, and you have 100 CPUs, and each CPU is clocked at 100 GHz, and you have a cluster of 100 computers, then it will still take you about an hour.

Under some more realistic assumptions, the time it takes your program to finish is more on the order of tens of thousands of years.

Since your code is not parallelized, in order for your code to finish in 5 minutes on a more realistic 4 GHz CPU, it would need to execute fib almost 300 million times per clock cycle.

It often helps to do some very rough guesstimates of the expected performance of your code. As you can see, you don't need to be an expert in Java or JVM or compilers or optimization or computer organization or CPU design or performance engineering. You don't need to know what, exactly, your code gets compiled down to. You don't need to know how many clock cycles an integer ADD takes. Because even when you make some totally over-the-top ridiculous assumptions, you can still easily see that your code cannot possibly finish in minutes or even hours.

Fibonacci sequence using BigInteger Does not yield an answer

1 Answers1