2

I'm working on a homework project where I must have the user input a number, and the computer spits out the Fibonacci numbers up to that one. I'd normally be able to do this, with int values, except that for this program, I need to use the BigInteger type instead, because int, long, double, etc. types are too small to hold the values I'll need. So, this is the code I've got. The problem is that it doesn't print the numbers it's supposed to. My imports:

import java.math.*;
import java.util.Scanner;

And the rest of the code:

    public static void main(String args[]) {

       //input to print Fibonacci series up to how many numbers
        System.out.println("Enter number up to which Fibonacci series to print: ");
        BigInteger i = BigInteger.valueOf(new Scanner(System.in).nextLong());

        System.out.println("First " + i + " Fibonacci numbers: ");
        //printing Fibonacci series upto number
        for(int j=1; i.compareTo(BigInteger.valueOf(j))<0; j++){
            System.out.print(fibonacci2(BigInteger.valueOf(j)) +" ");
        }


    } 







    public static BigInteger fibonacci2(BigInteger number){
        if(number.compareTo(BigInteger.valueOf(1)) == 0 || number.compareTo(BigInteger.valueOf(2)) == 0){
            return BigInteger.valueOf(1);
        }
        BigInteger fibo1=BigInteger.valueOf(1), fibo2=BigInteger.valueOf(1), fibonacci=BigInteger.valueOf(1);
        for(int i=3; number.compareTo(BigInteger.valueOf(i))<=0; i++){

          //Fibonacci number is sum of previous two Fibonacci number
          fibonacci = fibonacci.add(fibo1.add(fibo2));             
          fibo1 = fibo2;
          fibo2 = fibonacci;

        }
        return fibonacci; //The current Fibonacci number

    }   
}

I know it should work, because I was able to use it with the int type, but then I started to need values that were waaay bigger, so I was forced into BigInteger. Can someone see what's wrong with it? I think the problem is in the return for fibonacci2 method.

public static void
  • 95
  • 1
  • 6
  • 13

1 Answers1

3

The return value is the one that needs to be a BigInteger, not your argument number. Your initial tests are 1 and 2 (not 0 and 1 - which is how developers count). Basically, the quick and dirty solution is something like

public static BigInteger fibonacci2(int n) {
    if (n == 0 || n == 1) {
        return BigInteger.ONE;
    }
    return fibonacci2(n - 2).add(fibonacci2(n - 1));
}

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        System.out.println(fibonacci2(i));
    }
}

If you need to calculate large values then I suggest using a memoization like

private static Map<Integer, BigInteger> memo = new HashMap<>();

public static BigInteger fibonacci3(int n) {
    if (n == 0 || n == 1) {
        return BigInteger.ONE;
    }
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger v = fibonacci3(n - 2).add(fibonacci3(n - 1));
    memo.put(n, v);
    return v;
}

Note that fibonacci3 will be significantly faster than the initial recursive version.

Elliott Frisch
  • 198,278
  • 20
  • 158
  • 249
  • Thanks for the help, after looking it over and inserting it in, it worked perfectly. You're a lifesaver! – public static void Apr 14 '15 at 01:03
  • Why a map? The values of n are consecutive, so a simple array should do, and that ought to be faster (both entering and retrieving) than a map, especially for large values. Since we only need n-1 and n-2, these should be in the array already, so the check can be discarded too. – Rudy Velthuis Dec 07 '15 at 12:03
  • @RudyVelthuis we cant use an array, because we do not know the size of it. – Superluminal Oct 30 '18 at 13:54
  • Then use something extensible, like a list. A map needs hashing instead of simple indexing. **But you only need to remember the last two BigIntegers, as far as I can tell**. So an array with size 2 would be good enough. Or two variables. – Rudy Velthuis Oct 30 '18 at 16:03
  • I think we can use an array here. The size of the array can be initialized with (n+1). – Ultimate Fighter Feb 08 '22 at 23:00