more efficient Fibonacci for BigInteger

Question

I am working on a class project to create a more efficient Fibonacci than the recursive version of Fib(n-1) + Fib(n-2). For this project I need to use BigInteger. So far I have had the idea to use a map to store the previous fib numbers.

public static BigInteger theBigFib(BigInteger n) {

    Map<BigInteger, BigInteger> store = new TreeMap<BigInteger, BigInteger>(); 

    if (n.intValue()<= 2){
        return BigInteger.ONE;

    }else if(store.containsKey(n)){         
        return store.get(n);    

    }else{
        BigInteger one = new BigInteger("1");
        BigInteger two = new BigInteger("2");
        BigInteger val = theBigFib(n.subtract(one)).add(theBigFib(n.subtract(two)));
        store.put(n,val);           
        return val;
    }

}

I think that the map is storing more than it should be. I also think this line

BigInteger val = theBigFib(n.subtract(one)).add(theBigFib(n.subtract(two)));

is an issue. If anyone could shed some light on what i'm doing wrong or possible another solution to make it faster than the basic code. Thanks!

You can use a normal ArrayList as well if u want to store all the fibonacci numbers upto n. — Amit Kumar, Feb 02 '17 at 06:14
I think you are over complicating the problem, all you need is the last 2 results so `BigInteger[2]` acting like a stack suffices. — Aimee Borda, Feb 02 '17 at 06:16
@AimeeBorda agree, if op just need the final answer , it can be done with 3 variables as well — Amit Kumar, Feb 02 '17 at 06:17
If you want to generate ***really*** big Fibonacci numbers you shouldn't attempt to store all prior values, and you won't want to use an O(n) approach. Consider the O(log n) matrix approach in [this answer](http://stackoverflow.com/questions/24438655/ruby-fibonacci-algorithm/24439070#24439070). It will easily map to Java. — pjs, Feb 02 '17 at 15:42

Uma Kanth · Answer 1 · 2017-02-02T06:45:05.417

You don't need all the previous BigIntegers, you just need the last 2.

Instead of a recursive solution you can use a loop.

public static BigInteger getFib(int n) {
    BigInteger a = new BigInteger.ONE;
    BigInteger b = new BigInteger.ONE;

    if (n < 2) {
        return a;
    }
    BigInteger c = null;
    while (n-- >= 2) {
        c = a.add(b);
        a = b;
        b = c;
    }
    return c;
}

If you want to store all the previous values, you can use an array instead.

static BigInteger []memo = new BigInteger[MAX];
public static BigInteger getFib(int n) {
    if (n < 2) {
        return new BigInteger("1");
    }

    if (memo[n] != null) {
        return memo[n];
    }

    memo[n] = getFib(n - 1).add(getFib(n - 2));
    return memo[n];
}

If you just want the nth Fib value fast and efficient.

You can use the matrix form of fibonacci.

A = 1 1
    1 0

A^n = F(n + 1) F(n)
      F(n)     F(n - 1)

You can efficiently calculate A^n using Exponentiation by Squaring.

Replace `new BigInteger("1")` with [`BigInteger.ONE`](https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#ONE), and get rid of `new BigInteger("0")`. You should just declare `c` where it's used, i.e. `BigInteger c = a.add(b);`. — Andreas, Feb 02 '17 at 06:43

score 0 · Answer 2 · answered Feb 02 '17 at 06:30

I believe the main issue in your code is that you create a new Map on each function call. Note that it's still local variable, despite that your method is static. So, you're guaranteed that the store.containsKey(n) condition never holds and your solution is not better than naive. I.e. it still has exponential complexity of n. More precisely, it takes about F(n) steps to get to the answer (basically because all "ones" that make up your answer are returned by some function call).

I'd suggest making the variable a static field instead of a local variable. Then number of calls should become linear instead of exponential and you will see a significant improvement. Other solutions include for loop with three variables which iteratively calculate Fibonacci numbers from 0, 1, 2 up to n-th and the best solutions I know involve matrix exponentiation or explicit formula with real numbers (which is bad for precision), but it's a question better suited for computer science StackExchange website, imho.

more efficient Fibonacci for BigInteger

2 Answers2