Find the clock time for each Fibonacci(n) in nanoseconds

Question

I'm trying to find how long does each Fibonacci(n) takes in nanoseconds. The clock time in my code is always the same for all n. I think I make a mistake. How can I fix it?

Here is some of my output looks like:

0 used 3792 ns
1 used 3792 ns
1 used 3792 ns
2 used 3792 ns

...............

0 used 2455 ns
1 used 2455 ns
1 used 2455 ns
2 used 2455 ns

...............

0 used 2675 ns
1 used 2675 ns
1 used 2675 ns
2 used 2675 ns

class Fibonacci {
    private static long startTime = System.nanoTime();
    public static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n-1) + fib(n-2);
    }
    private static long endTime = System.nanoTime();

    public static void main (String args[])
    {
        long time = (endTime - startTime);
            for(int n = 0;n < 25; n++) {
                System.out.println(fib(n) + " used " + time + " ns");
        }
    }
}

Probably related: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Ole V.V., Jul 09 '20 at 13:29

score 1 · Accepted Answer · answered Jul 09 '20 at 05:01

Get the start time before calling the method and the end time after in each iteration. Do note that these performance measurements aren't the most accurate.

for(int n = 0;n < 25; n++) {
    long start = System.nanoTime();
    System.out.println(fib(n) + " used " + (System.nanoTime() - start) + " ns");
}

Lotsa · Answer 2 · 2020-07-09T07:45:24.213

In keeping with hev1's answer, note how I've rearranged your code. Note how now both startTime and endTime are declared together. I think you thought that by placing that below your method, that it executed after the method.

No. It doesn't work that way. The before and after execution, are conducted down below in the for loop ... not because of the order you declared them in the class as fields.

Look at this: with a similar fix to hev1's

class Fibonacci  {
    private static long startTime;
    private static long endTime;

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

    public static void main (String args[])
    {
        for(int n = 0;n < 25; n++) {
            startTime = System.nanoTime();
            int result = Fibonacci.fib(n);
            endTime = System.nanoTime();
            //System.out.println(result + " used " + (endTime - startTime) + " ns");
            System.out.format("%d\t\tused\t%d\tns\n", result, (endTime - startTime));
        }
    }
}

Output:

0        used   5100     ns
1        used   1100     ns
1        used   800      ns
2        used   900      ns
3        used   1300     ns
5        used   1800     ns
8        used   3200     ns
13       used   5400     ns
21       used   9300     ns
34       used   81800    ns
55       used   24700    ns
89       used   3700     ns
144      used   4000     ns
233      used   5900     ns
377      used   10100    ns
610      used   19500    ns
987      used   1281600  ns
1597     used   37900    ns
2584     used   30900    ns
4181     used   46100    ns
6765     used   72900    ns
10946    used   117300   ns
17711    used   189500   ns
28657    used   275400   ns
46368    used   492200   ns

Wouldn't it be better to keep the "System.out.println" out of the timing? Printing takes more time than the numeric calculation. Save fib(n) and then print it out later. — Daniel Widdis, Jul 09 '20 at 05:44
That's addressing a different issue, I think, than the question was asking. The question asked why the code wasn't working in the expected way. I tried to teach them something about where I thought their understanding of the language basics was unsteady. Is this a rational way to measure this in any accurate way? I don't think we got there yet, We're still learning how the language even works. I tried to address what I thought was their issue. — Lotsa, Jul 09 '20 at 06:27
@Daniel Widdis ... but since I agree with you, I edited in your suggestion. ;) — Lotsa, Jul 09 '20 at 06:37
Why did 987 take so long to calculate? Or was that when I moved my mouse? — Lotsa, Jul 09 '20 at 07:31
Lots of explanations for random longer times. 0 is longer than it should be simply for warm-up, there's no reason 0 and 1 should be any different. 34 and 55 are unusually long too. Could be compiler optimizations, branch prediction, garbage collection, a mix of all three. For better results you should randomize the order, repeat each calculation thousands of times, and average the results. — Daniel Widdis, Jul 09 '20 at 17:04

Find the clock time for each Fibonacci(n) in nanoseconds

2 Answers2