Fibonacci number java method?

Question

Can someone tell me what's wrong with the following program of mine. I'm trying to get the Fibonacci sequence and have the user input which number on the sequence he wants it for(eg 4th number).


package fibonacci.numbers;
import java.util.Scanner;


public class FibonacciNumbers {
static final int Num1=0;
static final int Num2=1;


/**
* @param args the command line arguments
*/
public static void main(String[] args) {

Scanner keyboard= new Scanner(System.in);
System.out.println("Enter your number on the Fibonnaci sequence that you would like");
int Number = keyboard.nextInt();
System.out.println("0,1");
int NumSeq = fibonnaci(Number);
System.out.printf("0,1",+NumSeq);


}
public static int fibonnaci(int c) {
int j;
for( j=0; c>j;j++){
int Num3 = Num1 +Num2;
System.out.print(Num3);
int Num4 = Num2 +Num3;
// System.out.print(Num4);
// int Num5 = Num3+Num4;
// System.out.println(Num5);
}
return j;
}

}

Thanks

Answer 1

A fine cross section of methods there.

I will address the mathematics involved, since that's more my specialty, and since you've already got some good coding answers.

But first, let's look at some of the possible error traps you'll need to consider.



Two things you haven't mentioned are

1) What if any restrictions are to be placed on n?

2) What kinds of errors do you have to check for?



There's some overlap there, of course. If the user enters 7.3, or 7.8, do you want both of those to come in as n=7 (i.e., truncated), or as 7 and 8 respectively (i.e., rounded)? I assume that Java, if it allows a floating input to be stored into an int variable, will truncate. If you want rounding, you will need to input into a float, and do the usual +½ before storing into an int. For negative n (see next paragraph), you'd have to -½ instead of +½. If there is a Floor function, then +½ will work for all.



Do you want to allow negative integers for n? Keep in mind that Fibonacci numbers are defined for all integers, positive, negative, and 0, through their defining recursion. A little scribbling will reveal that the negative-n terms are just the positive-n terms, with alternating signs:

F(-n) = (-1)^(n-1) F(n); i.e.,

for odd n, F(-n) = F(n)

for even n, F(-n) = -F(n)

so that, for instance, F(-8) can be found by computing F(8), and then negating it.

F(..., -8, ... , 8, ...) = ..., -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...



Do you want to allow very large-index Fibonacci numbers, which will fit into a double float, but are too large for a double int? You will of course, get a value that isn't exact, but is as close as double precision allows.



As for the pure mathematics of it, you can compute the n'th Fibonacci number for any n (positive, negative, non-integer, or non-real complex) by the closed formula:



F(n) = (φ^[n] - (-φ)^[-n]) / √5, where φ == ½(1 + √5) = 1.61803398874989...



Note two things, however.

First, when n is a non-integer, this will be a non-real complex value. I'm guessing that you don't care to let n be a non-integer.

Second, even for integers n, you will want to enclose that expression in a rounding function, to eliminate any deviation from an integer answer. Like the usual

Round(x) = Int(x+½)



Finally, note that if n is positive and large enough, the error introduced in reducing the formula to

F(n) ≈ φ^[n] / √5

will be smaller than the precision you are keeping for F(n), so you can use that shortcut for sufficiently large n.



EDIT:

In fact, for non-negative integers, n, rounding that expression to the nearest integer, IS just F(n):



F(n) = Round(φ^[n] / √5), n=0,1,2,...



/EDIT



You could even find F(n) for really large n, like, n=1,000,000, by taking log₁₀ of that expression, separate into int and frac, and then take 10^(frac):

log₁₀F(n) = n·log₁₀φ - ½log₁₀5 = 208987.290764977...

F(1,000,000) = 1.953282...·10²⁰⁸⁹⁸⁷

Answer 2

The following method is the most efficient* for integer input up to 46. You could use a long number version for numbers above the 46th term in the series. Or use the BigInteger class. Good luck!



*Tested using values 40-46 as input, recursion takes ages to run, compared with my iterative version which I include here.



public static int fibonacci(int input) {

int a = 0;

int b = 1;



for (int i = 0; i < input; i++) {

a += b;

b = a - b;

if (a<0) {

System.out.println("Error! Number too big for int");

return 0;

}

//System.out.println("Term "+(i+1)+": "+a);

}

return a;

} // end fibonacci()

Answer 3

It looks like you got ideas from somewhere about implementing this. Those Num1 and Num2 constants (declaring a variable "static" creates a named constant in Java) are the first two numbers of the sequence: Num1==F(0) and Num2==F(1). The only reason I can think of for having them is that there are related sequences that use the same rule F(n+1) = F(n) + F(n-1), but different starting values. Once you get the program working for Fibonacci numbers, you can quickly convert it to one of those other sequences just by changing Num1 and Num2.



They are constant becasue EVERY call to fibonacci() must start with those specific values. If you were allowed to change them (as your method tries to do) then the second call would have whatever values were left over from the previous call. That's not what you want.



Instead, use them to initialize local variables at the beginning of your function.



int j = 1; // a counting number that will count up to c

int fib_j = Num2; // value of F(j)

int fib_jm1 = Num1; // Value of F(j-1)



Now you can use a while loop (or a for loop, but I think while is clearer here) to increase the value of j by 1, repeatedly, until j==c. If you are careful to keep those statements in the comments above true at the end of each loop, then when you are done you will end up with j==c, and then fib_j==F(c) will be the value to return to the caller.



One loop that does that is:



while (j < c) {

.... int fib_jp1 = fib_j + fib_jm1; // compute F(j+1) = F(j) + F(j-1)

.... j = j+1; // count up by 1

.... fib_jm1 = fib_j; // new F(j-1) is old F(j)

.... fib_j = fib_jp1; // new F(j) is old F(j+1)

}



You can rewrite that while as a "for (j=1; j

Answer 4

You can get the nth Fibonacci number using recursion:



public static int getNthFibonacci(int n) {

if (n < 3) return 1;

return getNthFibonacci(n-2) + getNthFibonacci(n-1);

}



Full example:

http://ideone.com/h98Xis