Compute nth Fibonacci numbers with java

fibonacci sequence in leaf pointsWhat are Fibonacci nth numbers?

Fibonacci numbers are a sequence in the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … The next number is created by adding up the two previous numbers. So the 3 is found by adding the two numbers before it (1+2). “nth” refers to a number that will be provided to you for a problem to solve or sometimes you have to decide on what the “nth” number will be. For example, What is the 9th number in a specific Fibonacci sequence? Using recursion we see that the nth fibonacci number positions in the sequences are n-1 and n-2. We can code this with something like fibonacci(n-1) + fibonacci(n-2) to find the value for the nth fibonacci number.

Where do we compute nth Fibonacci numbers?

Paper, pencil, calculator or software can compute nth Fibonacci numbers. Any programming language can be used to create a program that will compute nth Fibonacci numbers and test the results for accuracy and performance. Register with Browxy to compile, run, test, save, and publish your own java code in a web browser. Learn how to use Eclipse to compile and run your own java code. You can use any software development program to create a program that will compute nth Fibonacci numbers. We are using Java with Browxy in this example.

When is ‘N’ a Fibonacci number?

N is a Fibonacci number if and only if 5 N2 + 4 or 5 N2 – 4 is a square number.Example:

  • 3 is a Fibonacci number because 5×32+4 is 49 which is 72
  • 5 is a Fibonacci number because 5×52–4 is 121 which is 112
  • 4 is not a Fibonacci number because neither 5×42+4=84 nor 5×42–4=76 are perfect squares.
  • 6 is a Fibonacci number because 5×62–4 is 180 which is 902
  • 8 is a Fibonacci number because because 5×82–4 is 316 which is 1582
  • 13 is a Fibonacci number because because 5×132–4 is 841 which is 420.52
  • 21 is a Fibonacci number because because 5×212–4 is 2201 which is 1100.52
  • 34 is a Fibonacci number because because 5×342–4 is 5776 which is 28882

Test if a whole number is square on a calculator by taking its square root and verifying it has nothing after the decimal point.
In a computer programming language, round the square root’s nearest integer and then square the result. If it’s the same as the original whole number then the original was a perfect square.

Who was Fibonacci?

Leonardo Pisano Bigollo (Fibonacci) was an Italian mathematician, considered to be  “the most talented Western mathematician of the Middle Ages.”  Leonardo grew up with a North African education under the Moors. You can read more details about Leonardo Pisano Bigollo at this website link: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibBio.html

Why do we compute nth Fibonacci numbers?

Fibonacci wanted to compute how fast rabbits can breed in an ideal environment, within one year. The first pair of rabbits give birth to a pair of rabbits. Now two pairs of rabbits give birth to another pair of rabbits. This continues for one year and our algorithm can tell us how many pairs of rabbits we will have at the end of the first year. Of course this experiment could lead to genetic problems, but we just want to compute how many pairs of rabbits we will have within one year.Henry Dudeni presented great puzzle examples that we can compute nth Fibonacci numbers for. Honeybee ancestors can also be computed with Fibonacci algorithms. The Golden Ratio or Golden Number (used by artists) is another example of where we find Fibonacci sequences and can create algorithms to compute them. Many designers are aware of Fibonacci rectangles and spirals and use them in their artwork. Fibonacci numbers are also represented with the growing points of plants, the petals on flowers. seed heads, pine cones, leaf arrangements, vegetables, fruit, and our own human fingers. We have 2 hands, each has 5 fingers, each finger has 3 parts separated by 2 knuckles.Review more details about Fibonacci sequences in nature at http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html

How to compute nth Fibonacci numbers with java recursively

Create Java Class “ComputeFibonacciNumbers”.

public class ComputeFibonacciNumbers { 
     //main java function
     //fibonacci java function
}

Create Java Function “fibonacci”.

static long fibonacci(int n) {
        return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);
    }

Test the fibonacci java function in the main java function of the ComputeFibonacciNumbers java class.

public class ComputeFibonacciNumbers {
     public static void main(String []args){
        for ( int i = 0; i < 10; i++ ) {
            System.out.print ( fibonacci(i) + ", " );
        }
        System.out.println ( fibonacci(10) );
     }
}

Compile & run ComputeFibonacciNumbers java class

Use this Browxy link to compile and run this java code in your web browser.

public class ComputeFibonacciNumbers {

     public static void main(String []args){
        for ( int i = 0; i < 10; i++ ) {
            System.out.print ( fibonacci(i) + ", " );
        }
        System.out.println ( fibonacci(10) );
     }
     
   static long fibonacci(int n) {
        return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);
    }
}

Java Algorithm Explanation

  1. public class ComputeFibonacciNumbers {
  2.      public static void main(String []args){
  3.         for ( int i = 0; i < 10; i++ ) {
  4.             System.out.print ( fibonacci(i) + ", " );
  5.         }
  6.         System.out.println ( fibonacci(10) );
  7.      }
  8.    static long fibonacci(int n) {
  9.         return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);
  10.     }

Create ComputeFibonacciNumbers Java Class

public class ComputeFibonacciNumbers { 
     //add main java function here
     //add other java functions after main java function
}

 

Create main Java Function

public static void main(String []args){

}

Every java class must have a main java function. We call to all our other java functions from the main java function. If we call to java classes & functions from separate files, we include an import statement at the top of our java class file. The import statement will tell this java class to look at the java class & functions in the files we referred to with an import statement.”public” tells us this function is available to the ComputeFibonacciNumbers java class. Java classes and functions are private by default so we declare them as public when we want to make them available to other java classes.”static” tells us we have only one copy of this function and to run it once.”void” tells us this java function does not return a value.One “main” function is required in our java classes.”(String [] args)” tells us this main function requires an array of string arguments to run. The square brackets indicate an array.

Create Java Function to compute nth fibonacci numbers

static long fibonacci(int n) {
        return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);
}

“static” tells us we will only have one copy of the fibonacci java function. We want to do a fibonacci computation that initializes  static variables, so we declare a static block because it gets executed exactly once, when our java class is first loaded.”long” is a 64-bit signed type that we use when “int” is not large enough to hold the value. We are computing Nth fibonacci numbers so we want to use “long” here.”fibonacci” is the name of this java function.”( int n  )” tells us this java function requires an integer to run.”return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);”  tells us that this fibonacci java function is calling to itself (recursion). Reading this statement from left to right, it says “return the integer n when it’s less than or equal to 1 otherwise return integer n when it’s 1 less than itself and 2 less than itself.We call to this fibonacci java function from our main java function in our ComputeFibonacciNumbers java class.

Call to ComputeFibonacciNumbers function from main java function

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

The for loop tells us to start with integer i being equal to zero. As long as integer i is less than 10, increment the integer by one and to print a statement showing the value of the integer with a comma.  When the for loop finds that integer i is greater than 10, it breaks out of the for loop and prints 10 of the integers to the screen.

How to compute nth Fibonacci numbers with java iteratively

View and run our source code with Browxy at http://www.browxy.com/user/monigarr/ComputeFibonacciNumbersIteratively.An iterative approach starts from the very beginning of the Fibonacci sequence and continues to sum the numbers until it reaches the nth number in the sequence. When it reaches the nth number we have our answer.We start adding the numbers if n is greater than or equal to 3 because we already return the numbers for n less than 3. We need two variables to represent the two previous numbers in the sequence. They should be initialized to 1 to represent the first and second numbers in the Fibonacci sequence.We want a loop to add and save the sum of the two previous numbers with the previous number. The loop will also keep repeating until we get the nth Fibonacci number.

public class ComputeFibonacciNumbersIteratively {

     public static void main(String []args){
        for ( int i = 0; i < 10; i++ ) {
            System.out.print ( fibonacci(i) + ", " );
        }
        System.out.println ( fibonacci(10) );
     }
     
   //function only runs once and only one copy.
   //takes in 64 byte type to hold the value
   //requires an integer to run
   static long fibonacci(int n) {
    //should give us: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    /*error condition returning -1*/
    if(n < 0)
        return -1;
   
    if (n == 0)
        return 0;

    if(n == 1 || n == 2)
        return 1;

    int int1 = 1;
    int int2 = 1;
    int fib = 0;

    for(int i=1; i<=n-2; i++)
    {
        fibonacci = int1 + int2;
        //swap values out
        int2 = int1;
        int1 = fibonacci;
    }
    return fibonacci;        
 }

}

References