Ideas on how to measure the time to get 45th Fibonacci number

Question

I'm working on a variation of a problem noted in Problem 19 Chapter 12 of the textbook "Building Java Programs". Essentially, I'm doing a recursion problem using a Fibonacci sequence. Though the program I've made works, part of the problem I'm working on is I also need to measure the time to get 45th Fibonacci number by using the implementations by 1, 2 and the one given in problem, print out how many times your implementations are faster than the one given in the problem . While I've looked at this page (Calculating a Fibonacci number with array), I was wondering is there was a way implement this without a lot of code change. This is the original method used:

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

And this is what I've done I did the problem using two java files: one that serves as a test main class with and the other with the recursion algorithm :

PrintValues.java

import java.util.Scanner;

public class PrintValues {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter the number value: ");
        int n = scan.nextInt();
        HelperBinary.countBinary(n);
        //fib(double nth);
    }
}

HelperBinary.Java:

public class HelperBinary {

    public static void countBinary(int n) {
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        countBinary(new char[n], n);
    }

    private static void countBinary(char[] preFx, int n) {
        if (n == 0) {
            /* This is the base case
            */
            System.out.println(preFx);
        } else {
            /* This is the "recursive" case.
            */
            final int i = preFx.length - n;

            /* Assign a '0' preFx and recurse
            */
            preFx[i] = '0';
            countBinary(preFx, n - 1);

            /*Assign a '1' preFx  and recurse
            */
            preFx[i] = '1';
            countBinary(preFx, n - 1);
        }
    }
}

Any help would be seriously appreciated.

Matt · Answer 1 · 2017-12-11T05:44:16.480

There are many subtleties when timing a program (see the question in the duplicate link), but here's two quick'n'dirty ways to get an idea of the run time.

The first way depends on what operating system you are using. If you use Linux or OS X, you could use the time command to measure how long a command takes to execute. Then you could run your java program like this:

time java -jar myJavaProgram.jar

and time will print to the console how long it took.

The second way is to time it in Java.

class SomeClass {

    private static void main(String[] args) {
        // record the start time
        long startTime = System.currentTimeMillis();

        // run your fibonnaci method and calculate the 45th number
        long fib45 = fib(45);

        // record the finishing time
        long endTime = System.currentTimeMillis();

        // calculate the time taken in milliseconds
        long runTime = endTime - startTime;

        System.out.println("45th Fibonacci number: " + fib45);
        System.out.println("Run time: " + runTime);
    }
}

Run it a few times and take the average run time.

Nice, but how do you make long fib45 = fib(45) work since all the methods are void? — Java Newbie, Dec 05 '17 at 15:49
That's just a placeholder for running your method, you can run it however you need. If it doesn't return anything, just call it. However, I feel like a method that calculates a fibonacci number should probably return the fibonacci number, otherwise it doesn't seem useful. — Matt, Dec 06 '17 at 06:53

Ideas on how to measure the time to get 45th Fibonacci number

1 Answers1