Start and Stop time of a function keeps returning 0 or 1

Question

I'm doing a homework assignment where we're testing the runtime of a couple algorithms (greatest common divisor, or GCD) using 10-digit prime numbers.

We are to capture the runtime as milliseconds, which I capture using System.currentTimeMillis().

The way I do it is to have a start time variable and a stop time variable, then find the difference between those two in another variable.

So far, it works perfectly for one method, but returns 0 or 1 for the other method.

I went through the debugger, and it seemed to work correctly, but when I run it, it returns 0 or 1.

Here are the variables I'm using and the main method. The commented-out line works as intended, but the fastgcd method is the one that returns 0 or 1.

public class GCD {

    public static long startTime;
    public static long stopTime;
    public static long elapsedTime;

    public GCD(){

    }

    public static void main(String[] args){
        startTime = System.currentTimeMillis();

        //System.out.println(gcd(3267000013L, 1500450271L));
        System.out.println(fastgcd(3267000013L, 1500450271L));

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println(Long.toString(elapsedTime));
    }

Here's the method that works:

public static String gcd(long a, long b) {
        long n = Long.min(a, b);
        for (long i = n; i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return "Done";
            }
        }
        // If error
        return null;
    }

And here's the method that doesn't work:

public static String fastgcd(long a, long b){
        if(b == 0){
            return "Done";
        }
        else{
            return fastgcd(b, a%b);
        }
    }

So for the method that works, I will get somewhere between 12000 - 12500 milliseconds for a 10-digit number.

The fastgcd method returns 0 or 1 milliseconds, which isn't right, especially a 10-digit prime number.

No idea where it's going wrong...

Count the number if iterations for the first one vs the second. — 001, Sep 10 '19 at 18:28
How confident are you that 1ms must be wrong? The first formula is doing literally tens of millions of times more work. — resueman, Sep 10 '19 at 18:32
And another hint: **never** include print statements within your measurement! Printing to the console can take significant amounts of time, and also vary greatly. So: exclude printing. Also see https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java ... you dont need to apply everything. But you should at least understand what problems you should consider when benchmarking code. — GhostCat, Sep 10 '19 at 18:39
hmm... ran it through the debugger and even with a 10-digit number it didn't take long. Maybe 0 or 1 is in fact accurate ‍♂️ — ESM, Sep 10 '19 at 18:42
Then tell your teacher that GhostCat from the interwebs told you to ask your money back. That, or politely send him that link I gave youl — GhostCat, Sep 11 '19 at 19:29

score 2 · Accepted Answer · answered Sep 10 '19 at 18:28

2

Your code is fine (in terms of getting time), and the values that you're getting are "correct". What you're measuring is wall-clock time (see here), which is inherently slightly inaccurate, and also not granular enough to measure code that is running as quickly as your fastgcd method.

For measuring elapsed time with a high degree of precision, use System.nanoTime() instead of System.currentTimeMillis().

answered Sep 10 '19 at 18:28

Jordan

2,273
9
16

that makes sense, tried it and it works. Thanks a bunch!! – ESM Sep 10 '19 at 18:48

Gaurav Jeswani · Answer 2 · 2019-09-10T18:34:28.213

0

If you run your method and check the recursion count, it will be called recursively only 19 times. And for these modern days compiler and machines, it is not huge operation. So completing it in 1 millisecond is totally justified. If you check it in nanoseconds using System.nanoTime(), fastgcd is taking around 280675 nanoseconds on my Windows machine Java 8, 32 GB RAM and 8th Gen Core I7. So nothing going wrong here.

edited Sep 10 '19 at 18:34

answered Sep 10 '19 at 18:31

Gaurav Jeswani

4,410
6
26
47

1

To expand on what you said, 280675 is .28 milliseconds, which rounds down to 0 because it is returned as a `long` and does not hold decimals with `.currentTimeMillis()` and does not have the precision of `.nanoTime()`. – Nexevis Sep 10 '19 at 18:32

Start and Stop time of a function keeps returning 0 or 1

2 Answers2