Java Fibonacci Numbers Timer

Question

The program itself runs fine. Every value I enter return the correct corresponding Fibonacci number. I need to also time the execution of the recursive function and the function using a loop. When I run the program it just returns the time it took the user to actually enter their input instead of the time it takes the run the function. I have tried moving the timers around but I keep getting the same result. I want to return the time it actually took to calculate a fibonacci number recursively and how long it takes to calculate a fibonacci number using a loop.

import java.util.Scanner;

public class FibNumbers {
            public static void main(String[] args) {
            int f;
            int l;
            long num1;
            long num2;
            int choice;
            long t1 = System.currentTimeMillis();
            Scanner sc = new Scanner(System.in);
            Scanner keyboard = new Scanner(System.in);

            System.out.println("For recursion press 1 %n for loop press 2" );
            choice = keyboard.nextInt();
            if(choice == 1) {
                System.out.println("Please enter a value for n");
                f = Integer.parseInt(sc.nextLine());
                System.out.println("The Fibonacci number is " + fibonacciR(f) + " using recursion");
            }
            else {
                System.out.println("Please enter a value for n");
                l = Integer.parseInt(sc.nextLine());
                System.out.println("The Fibonacci number is " + fibonacciL(l) + " using a for loop");
            }
            long t2 = System.currentTimeMillis();
            System.out.println("The elapsed time is " + (t2 - t1) / 1000 + " seconds.");
        }

        public static long fibonacciR(long f) {
            if(f == 0) {
                return 0;
            }
            else if(f == 1) {
                return 1;
            }
            else {
                return fibonacciR(f-1) + fibonacciR(f-2);
            }
        }

        public static long fibonacciL(long l) {
            long num1 = 0;
            long num2 = 1;
            long total = l;
            long sumOfTwo;
            for(int i = 0; i < total; i++) {
                sumOfTwo = num1 + num2;
                num1 = num2;
                num2 = sumOfTwo;
            }
            return num1;
        }
    }

I guess i don't understand the logic behind a timer in java or the placement of the timers in the program. — Austin Johnson, Feb 04 '18 at 04:42
Have you tried setting the first timer right before the call to fibonacci call and the second call directly after? — Jonathan Van Dam, Feb 04 '18 at 04:43

score 1 · Answer 1 · answered Feb 04 '18 at 04:45

1

You should initialize your t1 = System.currentTimeMillis(); right after the user enters a value for n:

long t1;
if(choice == 1) {
    System.out.println("Please enter a value for n");
    f = Integer.parseInt(sc.nextLine());
    t1 = System.currentTimeMillis();
    System.out.println("The Fibonacci number is " + fibonacciR(f) + " using recursion");
}
else {
    System.out.println("Please enter a value for n");
    l = Integer.parseInt(sc.nextLine());
    t1 = System.currentTimeMillis();
    System.out.println("The Fibonacci number is " + fibonacciL(l) + " using a for loop");
}
long t2 = System.currentTimeMillis();

answered Feb 04 '18 at 04:45

Kirill Simonov

8,257
3
18
42

This also returns 0. – Austin Johnson Feb 04 '18 at 05:03
2

@tin because it really takes 0 seconds to run a loop (and a lot more to run a recursion). Try to print milliseconds. – Kirill Simonov Feb 04 '18 at 05:13
1

@tin by the way: if you want a faster recursion approach, take a look at [this interesting tail recursion](https://stackoverflow.com/a/13826877/8629960). It is written in `c++`, but the idea is clear. – Kirill Simonov Feb 04 '18 at 05:40

Jonathan Van Dam · Accepted Answer · 2018-02-04T05:46:18.650

Use System.nanoTime(); for nano seconds.

Also dividing by 1000 will yield 0 if (t2 - t1) is less than 1000 since you are using long you could cast to a float/double and then do the division.

Something like this maybe:

import java.util.Scanner;

public class FibNumbers {
        public static void main(String[] args) {
        int f;
        int l;
        long num1;
        long num2;
        int choice;
        long t1 = 0, t2 = 0;
        Scanner sc = new Scanner(System.in);
        Scanner keyboard = new Scanner(System.in);

        System.out.println("For recursion press 1 %n for loop press 2" );
        choice = keyboard.nextInt();
        if(choice == 1) {
            System.out.println("Please enter a value for n");
            f = Integer.parseInt(sc.nextLine());
            t1 = System.nanoTime();
            System.out.println("The Fibonacci number is " + fibonacciR(f) + " using recursion");
            t2 = System.nanoTime();
        }
        else {
            System.out.println("Please enter a value for n");
            l = Integer.parseInt(sc.nextLine());
            t1 = System.currentTimeMillis();
            System.out.println("The Fibonacci number is " + fibonacciL(l) + " using a for loop");
            t2 = System.nanoTime();
        }
        System.out.println("The elapsed time is " + (t2 - t1) + " nano seconds.");
    }

    public static long fibonacciR(long f) {
        if(f == 0) {
            return 0;
        }
        else if(f == 1) {
            return 1;
        }
        else {
            return fibonacciR(f-1) + fibonacciR(f-2);
        }
    }

    public static long fibonacciL(long l) {
        long num1 = 0;
        long num2 = 1;
        long total = l;
        long sumOfTwo;
        for(int i = 0; i < total; i++) {
            sumOfTwo = num1 + num2;
            num1 = num2;
            num2 = sumOfTwo;
        }
        return num1;
    }
}

yep still getting "For recursion press 1 for loop press 2 2 Please enter a value for n 999999 The Fibonacci number is 7006191581884273890 using a for loop The elapsed time is 0 seconds" — Austin Johnson, Feb 04 '18 at 05:02
ok than it's executing to fast to measure in milliseconds use `System.nanoTime();` instead. — Jonathan Van Dam, Feb 04 '18 at 05:17

Kamil Tomasz Jarmusik · Answer 3 · 2018-02-06T13:03:24.990

class FibonacciRecursionElseStrategy implements Fibonacci {

    @Override
    public long calculate(long f) {

        if(f < 0)
            throw new IllegalArgumentException();

        if(f == 0) {
            return 0;
        } else if(f == 1) {
            return 1;
        } else {
            return calculate(f-1) + calculate(f-2);
        }
    }

    @Override
    public void elapsedTime(long f, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            calculate(f);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for recursionElseIf strategy");

    }

}

class FibonacciRecursionStrategy implements Fibonacci {

    @Override
    public long calculate(long f) {

        if(f < 0)
            throw new IllegalArgumentException();

        return f == 0 || f == 1 ? f : calculate(f - 1) + calculate(f - 2);
    }

    @Override
    public void elapsedTime(long f, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            calculate(f);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for recursion strategy");

    }

}

class FibonacciLoopStrategy implements Fibonacci {

    @Override
    public long calculate(long f) {

        if(f < 0)
            throw new IllegalArgumentException();

        long num1 = 0;
        long num2 = 1;
        long sumOfTwo;

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

            sumOfTwo = num1 + num2;
            num1 = num2;
            num2 = sumOfTwo;
        }

        return num1;
    }

    @Override
    public void elapsedTime(long f, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            calculate(f);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for loop strategy");

    }

}

interface Fibonacci {

    public long calculate(long f);
    public void elapsedTime(long f, int repetitions);

}

public class FibonacciNumbers {

    public static long fibonacciRecursion(long f) {
        return f == 0 || f == 1 ? f : fibonacciRecursion(f - 1) + fibonacciRecursion(f - 2);
    }

    public static long fibonacciRecursionElseIf(long f) {

        if(f == 0) {
            return 0;
        } else if(f == 1) {
            return 1;
        } else {
            return fibonacciRecursionElseIf(f-1) + fibonacciRecursionElseIf(f-2);
        }
    }

    public static long fibonacciLoop(long total) {

        long num1 = 0;
        long num2 = 1;
        long sumOfTwo;

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

            sumOfTwo = num1 + num2;
            num1 = num2;
            num2 = sumOfTwo;
        }

        return num1;
    }
}

class Timer {

    public static void elapsedTimeFibonacciLoop(long value, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            FibonacciNumbers.fibonacciLoop(value);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for loop");
    }

    public static void elapsedTimeFibonacciRecursion(long value, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            FibonacciNumbers.fibonacciRecursion(value);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for recursion");
    }

    public static void elapsedTimeFibonacciRecursionElseIf(long value, int repetitions) {

        long t1, t2;

        t1 = System.nanoTime();

        for (int i = 0; i < repetitions; i++) 
            FibonacciNumbers.fibonacciRecursionElseIf(value);

        t2 = System.nanoTime();

        System.out.println("The elapsed time is " + ((t2 - t1) / 1000000) + " [ms] using a for recursionElseIf");
    }
}

class Start {

    public static void main(String[] args) {

        Timer.elapsedTimeFibonacciLoop(11, 10000000);
        Timer.elapsedTimeFibonacciRecursion(11, 10000000);
        Timer.elapsedTimeFibonacciRecursionElseIf(11, 10000000);

        System.out.println("" + FibonacciNumbers.fibonacciLoop(11) + " for loop");
        System.out.println("" + FibonacciNumbers.fibonacciRecursion(11) + " for recursion");
        System.out.println("" + FibonacciNumbers.fibonacciRecursionElseIf(11) + " for recursionElseIf");

        System.out.println("Strategy");
        Fibonacci loop = new FibonacciLoopStrategy();
        Fibonacci recursion = new FibonacciRecursionStrategy();
        Fibonacci recursionElse = new FibonacciRecursionElseStrategy();

        loop.elapsedTime(11, 10000000);
        recursion.elapsedTime(11, 10000000);
        recursionElse.elapsedTime(11, 10000000);

    }
}

Output:

The elapsed time is 157 [ms] using a for loop
The elapsed time is 7591 [ms] using a for recursion
The elapsed time is 7213 [ms] using a for recursionElseIf
89 for loop
89 for recursion
89 for recursionElseIf
Strategy
The elapsed time is 158 [ms] using a for loop strategy
The elapsed time is 8094 [ms] using a for recursion strategy
The elapsed time is 8183 [ms] using a for recursionElseIf strategy

By changing the order of calculating the method from the loop and the recurrence:

class Start {

    public static void main(String[] args) {

        Timer.elapsedTimeFibonacciRecursion(11, 10000000);
        Timer.elapsedTimeFibonacciLoop(11, 10000000);
        Timer.elapsedTimeFibonacciRecursionElseIf(11, 10000000);

        System.out.println("" + FibonacciNumbers.fibonacciLoop(11) + " for loop");
        System.out.println("" + FibonacciNumbers.fibonacciRecursion(11) + " for recursion");
        System.out.println("" + FibonacciNumbers.fibonacciRecursionElseIf(11) + " for recursionElseIf");

        System.out.println("Strategy");
        Fibonacci loop = new FibonacciLoopStrategy();
        Fibonacci recursion = new FibonacciRecursionStrategy();
        Fibonacci recursionElse = new FibonacciRecursionElseStrategy();

        recursion.elapsedTime(11, 10000000);
        loop.elapsedTime(11, 10000000);
        recursionElse.elapsedTime(11, 10000000);

    }
}

The elapsed time is 7690 [ms] using a for recursion
The elapsed time is 172 [ms] using a for loop
The elapsed time is 7728 [ms] using a for recursionElseIf
89 for loop
89 for recursion
89 for recursionElseIf
Strategy
The elapsed time is 8407 [ms] using a for recursion strategy
The elapsed time is 155 [ms] using a for loop strategy
The elapsed time is 7989 [ms] using a for recursionElseIf strategy

Java Fibonacci Numbers Timer

3 Answers3