Determining whether a number is a Fibonacci number

Question

I need to write Java code that checks if a user-entered number is in the Fibonacci sequence.

I have no problem writing the Fibonacci sequence for output, but (probably due to its late night) I am struggling to imagine the sequence “be it the Fibonacci number”. I continue again and again. This is really my head.

I currently have the nth.

public static void main(String[] args) { ConsoleReader console = new ConsoleReader(); System.out.println("Enter the value for your n: "); int num = (console.readInt()); System.out.println("\nThe largest nth fibonacci: "+fib(num)); System.out.println(); } static int fib(int n){ int f = 0; int g = 1; int largeNum = -1; for(int i = 0; i < n; i++) { if(i == (n-1)) largeNum = f; System.out.print(f + " "); f = f + g; g = f - g; } return largeNum; } 

Answer 1

Read the section entitled “Fibonacci number recognition” on wikipedia .

Alternatively, a positive integer z is a Fibonacci number if and only if one of 5z ^ 2 + 4 or 5z ^ 2 - 4 is a perfect square. [17]

Alternatively, you can continue to generate the Fibonacci number until it becomes equal to your number: if so, then your number is the Fibonacci number, if not, the numbers will become larger than your number over time, and you can stop. However, this is quite inefficient.

Answer 2

If I understand correctly what you need to do (instead of writing the first n Fibonacci numbers), you need to determine if n is a Fibonacci number.

So, you have to change your method to continue generating the Fibonacci sequence until you get the number> = n. If it is equal, n is the Fibonacci number, otherwise not.

Update: Listening to @Moron has repeatedly stated that the formula-based algorithm is superior in performance to the simpler one above, I actually made a comparative comparison - specifically between Jacopo's solution as a generator algorithm and StevenH last version as a formula-based algorithm. For reference, here is the exact code:

 public static void main(String[] args) { measureExecutionTimeForGeneratorAlgorithm(1); measureExecutionTimeForFormulaAlgorithm(1); measureExecutionTimeForGeneratorAlgorithm(10); measureExecutionTimeForFormulaAlgorithm(10); measureExecutionTimeForGeneratorAlgorithm(100); measureExecutionTimeForFormulaAlgorithm(100); measureExecutionTimeForGeneratorAlgorithm(1000); measureExecutionTimeForFormulaAlgorithm(1000); measureExecutionTimeForGeneratorAlgorithm(10000); measureExecutionTimeForFormulaAlgorithm(10000); measureExecutionTimeForGeneratorAlgorithm(100000); measureExecutionTimeForFormulaAlgorithm(100000); measureExecutionTimeForGeneratorAlgorithm(1000000); measureExecutionTimeForFormulaAlgorithm(1000000); measureExecutionTimeForGeneratorAlgorithm(10000000); measureExecutionTimeForFormulaAlgorithm(10000000); measureExecutionTimeForGeneratorAlgorithm(100000000); measureExecutionTimeForFormulaAlgorithm(100000000); measureExecutionTimeForGeneratorAlgorithm(1000000000); measureExecutionTimeForFormulaAlgorithm(1000000000); measureExecutionTimeForGeneratorAlgorithm(2000000000); measureExecutionTimeForFormulaAlgorithm(2000000000); } static void measureExecutionTimeForGeneratorAlgorithm(int x) { final int count = 1000000; final long start = System.nanoTime(); for (int i = 0; i < count; i++) { isFibByGeneration(x); } final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9; System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds"); } static void measureExecutionTimeForFormulaAlgorithm(int x) { final int count = 1000000; final long start = System.nanoTime(); for (int i = 0; i < count; i++) { isFibByFormula(x); } final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9; System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds"); } static boolean isFibByGeneration(int x) { int a=0; int b=1; int f=1; while (b < x){ f = a + b; a = b; b = f; } return x == f; } private static boolean isFibByFormula(int num) { double first = 5 * Math.pow((num), 2) + 4; double second = 5 * Math.pow((num), 2) - 4; return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second)); } private static boolean isWholeNumber(double num) { return num - Math.round(num) == 0; } 

The results surprised me even:

 Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds Running formula algorithm 1000000 times for 1 took 0.223365539 seconds Running generator algorithm 1000000 times for 10 took 0.017330694 seconds Running formula algorithm 1000000 times for 10 took 0.279445852 seconds Running generator algorithm 1000000 times for 100 took 0.030283179 seconds Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds 

In short, the generator algorithm algorithm is superior to the solution based on the formula for all positive values ​​of int - even close to the maximum value of int, it is more than twice as fast! -)

To write, modifying the above code to use long variables instead of int , the generator algorithm becomes slower (as expected, since it should now add long values) and the intersection point where the formula starts to be faster - about 1000000000000L, i.e. 10 ¹² .

Update2: As Ivlad and Moron noted, I am not a very expert in floating point calculations :-), based on my suggestions, I improved the formula for this:

 private static boolean isFibByFormula(long num) { double power = (double)num * (double)num; double first = 5 * power + 4; double second = 5 * power - 4; return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second)); } 

This has led to a decrease in the intersection point of approx. 10 ⁸ (for the long version, the generator with int is still faster for all int values). Undoubtedly, replacing sqrt calls with something like the one suggested by @Moron will further lower the jump point.

My (and IVlad's) point was simply that there would always be an intersection point below which the generator algorithm would be faster. Therefore, statements that one of them works better do not make sense at all, only in context.

Answer 3

Instead of passing the index, n , write a function that takes a limit and forces it to generate Fibonacci numbers down to that limit. Get it to return a boolean value depending on whether it falls within or misses the limit, and you can use it to check if that value is in sequence.

Since this is homework, something like this is probably all we should give you ...

Answer 4

Ok Since people claimed that I was simply saying thin air (“facts” versus “guesses”), without any data to support it, I wrote my own test.

Not java, but C # code below.

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SO { class Program { static void Main(string[] args) { AssertIsFibSqrt(100000000); MeasureSequential(1); MeasureSqrt(1); MeasureSequential(10); MeasureSqrt(10); MeasureSequential(50); MeasureSqrt(50); MeasureSequential(100); MeasureSqrt(100); MeasureSequential(100000); MeasureSqrt(100000); MeasureSequential(100000000); MeasureSqrt(100000000); } static void MeasureSequential(long n) { int count = 1000000; DateTime start = DateTime.Now; for (int i = 0; i < count; i++) { IsFibSequential(n); } DateTime end = DateTime.Now; TimeSpan duration = end - start; Console.WriteLine("Sequential for input = " + n + " : " + duration.Ticks); } static void MeasureSqrt(long n) { int count = 1000000; DateTime start = DateTime.Now; for (int i = 0; i < count; i++) { IsFibSqrt(n); } DateTime end = DateTime.Now; TimeSpan duration = end - start; Console.WriteLine("Sqrt for input = " + n + " : " + duration.Ticks); } static void AssertIsFibSqrt(long x) { Dictionary<long, bool> fibs = new Dictionary<long, bool>(); long a = 0; long b = 1; long f = 1; while (b < x) { f = a + b; a = b; b = f; fibs[a] = true; fibs[b] = true; } for (long i = 1; i <= x; i++) { bool isFib = fibs.ContainsKey(i); if (isFib && IsFibSqrt(i)) { continue; } if (!isFib && !IsFibSqrt(i)) { continue; } Console.WriteLine("Sqrt Fib test failed for: " + i); } } static bool IsFibSequential(long x) { long a = 0; long b = 1; long f = 1; while (b < x) { f = a + b; a = b; b = f; } return x == f; } static bool IsFibSqrt(long x) { long y = 5 * x * x + 4; double doubleS = Math.Sqrt(y); long s = (long)doubleS; long sqr = s*s; return (sqr == y || sqr == (y-8)); } } } 

And here is the conclusion

 Sequential for input = 1 : 110011 Sqrt for input = 1 : 670067 Sequential for input = 10 : 560056 Sqrt for input = 10 : 540054 Sequential for input = 50 : 610061 Sqrt for input = 50 : 540054 Sequential for input = 100 : 730073 Sqrt for input = 100 : 540054 Sequential for input = 100000 : 1490149 Sqrt for input = 100000 : 540054 Sequential for input = 100000000 : 2180218 Sqrt for input = 100000000 : 540054 

The sqrt method is superior to the naive method when n = 50 itself, possibly due to the availability of hardware support on my machine. Even if it was 10 ^ 8 (as in the Peter test), under this cutoff there are no more than 40 fibonacci numbers that can be easily placed in the lookup table and still outperform the naive version for lower values.

In addition, Peter has a poor implementation of SqrtVersion. He really does not need to calculate two square roots or calculate powers using Math.Pow. He could try to do it better before posting test results.

In any case, I will allow these facts to speak for themselves, and not the so-called "guesses".

Answer 5

A positive integer x is a Fibonacci number if and only if one of 5x ^ 2 + 4 and 5x ^ 2 - 4 is an ideal square

Answer 6

There are several methods that can be used to determine if a given number is in a Fibonacci sequence, a selection of which can be seen on wikipedia .

Given what you have already done, I would probably use a more crude approach, for example:

• Create Fibonacci Number
• If it is less than the target number, generate the next fibonacci and repeat
• If this is the target number, then success
• If it is greater than the target number, then a failure.

I would probably use a recursive method, passing the current n-value (i.e. calculating the nth fibonacci number) and the target number.

Answer 7

 //Program begins public class isANumberFibonacci { public static int fibonacci(int seriesLength) { if (seriesLength == 1 || seriesLength == 2) { return 1; } else { return fibonacci(seriesLength - 1) + fibonacci(seriesLength - 2); } } public static void main(String args[]) { int number = 4101; int i = 1; while (i > 0) { int fibnumber = fibonacci(i); if (fibnumber != number) { if (fibnumber > number) { System.out.println("Not fib"); break; } else { i++; } } else { System.out.println("The number is fibonacci"); break; } } } } //Program ends 

Answer 8

If my Java is not too rusty ...

 static bool isFib(int x) { int a=0; int b=1; int f=1; while (b < x){ f = a + b; a = b; b = f; } return x == f; } 

Answer 9

Trying to use the code you already wrote, I would suggest the following first, as this is the simplest solution (but not the most efficient):

 private static void main(string[] args) { //This will determnine which numbers between 1 & 100 are in the fibonacci series //you can swop in code to read from console rather than 'i' being used from the for loop for (int i = 0; i < 100; i++) { bool result = isFib(1); if (result) System.out.println(i + " is in the Fib series."); System.out.println(result); } } private static bool isFib(int num) { int counter = 0; while (true) { if (fib(counter) < num) { counter++; continue; } if (fib(counter) == num) { return true; } if (fib(counter) > num) { return false; } } } 

I would suggest a more elegant Fibonacci number generation solution that uses recursion as follows:

 public static long fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); } 

For additional credit: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

You will see that there are several more effective ways of testing if the number is in the Fibonacci series , namely: (5z ^ 2 + 4 or 5z ^ 2 - 4) = perfect square.

 //(5z^2 + 4 or 5z^2 − 4) = a perfect square //perfect square = an integer that is the square of an integer private static bool isFib(int num) { double first = 5 * Math.pow((num), 2) + 4; double second = 5 * Math.pow((num), 2) - 4; return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second)); } private static bool isWholeNumber(double num) { return num - Math.round(num) == 0; } 

Answer 10

I don’t know if there is an actual formula that you can apply to user input, however you can generate a fibonacci sequence and check it for user input until it is less than the last generated number.

 int userInput = n; int a = 1, b = 1; while (a < n) { if (a == n) return true; int next = a + b; b = a; a = next; } return false; 

Answer 11

You can do this in two ways: recursive and mathematical. recursive path start generating the fibonacci sequence until you click the number or go through its mathematical method, well described here ... http://www.physicsforums.com/showthread.php?t=252798

good luck.

Answer 12

Consider the sequence of Fibonacci numbers 1,1,2,3,5,8,13,21, etc. It is advisable to build 3 stacks each of capacity 10 containing numbers from the above sequences, as follows:

Stack 1: The first 10 numbers from the sequence. Stack 2: The first 10 primes from the sequence. Stack 3: The first 10 odd numbers from the sequence.

(i) Give the flowchart algorithm (ii) Write the program (in BASIC, C ++ or Java) for its implementation.

Conclusion: as you perform stack operations, you should display 3 stacks in any convenient form along with the values ​​contained in them.

Answer 13

Find out if the Fibonacci number is by the formula:

 public static boolean isNumberFromFibonacciSequence(int num){ if (num == 0 || num == 1){ return true; } else { //5n^2 - 4 OR 5n^2 + 4 should be perfect squares return isPerfectSquare( 5*num*num - 4) || isPerfectSquare(5*num*num - 4); } } private static boolean isPerfectSquare(int num){ double sqrt = Math.sqrt(num); return sqrt * sqrt == num; } 

Answer 14

Thought it was simple until I had to rack my brains for a few minutes. Its difference from the generation of a fibonacci sequence. This function returns 1 if Fibonnaci or 0 if not

 public static int isFibonacci (int n){ int isFib = 0; int a = 0, b = 0, c = a + b; // set up the initial values do { a = b; b = c; c = a + b; if (c == n) isFib = 1; } while (c<=n && isFin == 0) return isFib; } public static void main(String [] args){ System.out.println(isFibonacci(89)); }