Correct usage of Java System.currentTimeMillis() method?

Question

I am comparing the time to compute both iterative and recursive factorial procedures in Java. I am trying to use the System.currentTimeMillis method to compare the time it takes for each algorithm to compute, but I can't seem to calculate the difference. I am not sure what the proper way to use this method is, but any event here is what I am trying to achieve in my code:

// ... more code above

System.out.print("Please enter an integer: ");
int integer = readInt();
System.out.println();

// demonstrate recursive factorial and calculate
// how long it took to complete the algorithm
long time1 = System.currentTimeMillis();
int fact1 = factRecursive(integer);
long time2 = System.currentTimeMillis();
System.out.format("Result of recursive factorial %s is %d\n", integer, fact1);
System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));

// ... more code below

Here is the output:

Please enter an integer: 25

Result of recursive factorial 25 is 2076180480
Algorithm took 0 milliseconds

Result of iterative factorial 25 is 2076180480
Algorithm took 0 milliseconds

Clearly I must be doing something wrong here, as the amount of time expected to compute factorials for both cases shouldn't be zero.

EDIT: Here are my solutions for factorial, if anyone is interested (not particularly unique, but here they are anyway):

// factRecursive uses a recursive algorithm for 
// caluclating factorials.
public static long factRecursive(long n)
{
    return n = (n == 1)? 1 : n * factRecursive(n - 1);
}

// factIterative uses an iterative algorithm for
// calculating factorials.
public static long factIterative(long n)
{
    long product = 1;

    if(n == 1) return n;

    for(int i = 1; i <= n; ++i)
        product *= i;

    return product;
}

And is some output. Surprisingly, the recursive version holds up well. It isn't until about 39! that the iterative version starts performing noticeably better.

Please enter an integer: 39

Result of recursive factorial 39 is 2304077777655037952
Algorithm took 5828 nanoseconds

Result of iterative factorial 39 is 2304077777655037952
Algorithm took 5504 nanoseconds

Answer 1

A well-written factorial function should execute very quickly for n = 25, so having it run in approximately 0ms isn't terribly surprising. You have three options:

1. Use a larger n. This will cause the factorial function to take longer, and give you something to measure.
2. Measure time in approximate nanoseconds rather than milliseconds, using System.nanoTime.
3. I recommend doing both 1 and 2.

As other answerers have pointed out, you are indeed subtracting end from start, which is backwards. Obviously, you should fix that too. But that change only affects the sign of the result, not the absolute value.

---

EDIT: Just to see how fast it is to find the factorial of 25, I wrote this Python implementation

>>> def fact(n):
...     def _fact(n, acc):
...             if n == 1:
...                     return acc
...             return _fact(n - 1, n * acc)
...     if n < 0:
...             return 0 # Or raise an exception
...     if n < 2:
...             return 1
...     return _fact(n, 1)
... 
>>> fact(25)
15511210043330985984000000L
>>> import timeit
>>> t = timeit.Timer("fact(25)", "from __main__ import fact")
>>> print t.timeit()
6.2074379921

Even though Python is an interpreted dynamically typed language without tail call optimization, a simple recursive solution with an accumulator can find fact(25) a million times in 6.2 seconds on my machine. So the average execution time is 6.2 microseconds. Not a chance of measuring a substantial difference between an iterative and recursive solution on a single run with millisecond clock precision.

Answer 2

The resolution of System.currentTimeMillis() can vary, depending on your system; it appears that your algorithm is too fast to measure with this timer.

Use System.nanoTime() instead. Its accuracy is also system dependent, but at least it is capable of high resolution time measurement.

Just-in-time compilation can have a big impact on performance, but most virtual machines require a method to be invoked many times before recompiling it. This makes it difficult to get accurate results from this kind of micro-benchmark.

Answer 3

You need to do (finish time - start time), you have it backward.

try this:

System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));

Answer 4

very usual mistake. You should be subtracting time1 from time2.

It will help if you name your variables sensibly - for example startTime and endTime so you would know or at least spot that you have to do endTime - startTime as endTime > startTime

Answer 5

Looks like your fast recursive may not be doing such a heavy processing after all.

Please use System.nanoTime() instead. It returns nano seconds

http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

nanoTime() Returns the current value of the running Java Virtual Machine's high-resolution time source, in nanoseconds.

---

Another way to test is by iterating your factorial say a 1000 times. then divide the time difference by 1000.00 (double)

Answer 6

To get a meaningful timed result you need to repeat it, and ignore, at least the first 10,000 times you call a method (so the code is compiled) and you need to run it for a further 2-10 seconds (repeatedly).