Java Fibonacci - elapsedTime(); formula

Question

I'm working on a small project for the fibonacci algorithm.

I'm using the following method to calculate the algorithm. Note that elapsedTime() returns a double.

public static void fibonacciSequence(long n1, long n2) {

    t0 = stopwatch.elapsedTime();
    System.out.print("index: " + index + " -> " + n1 + "\t");
    t1 = stopwatch.elapsedTime();
    lapTime = (1000 * t1 - 1000 * t0) / 1000;
    StdOut.println(" (" + lapTime + "\t " + t1 + ")");

    if (index == stoppingPoint) {
        return;
    }
    index++;
    fibonacciSequence(n2, n1 + n2);
}

Now don't pay too much attention about the algorithm itself - it gets fixed. I only don't understand the formula for lapTime. Why can't it be

lapTime = t1-t0;

What does elapsedTime() return---means which datatype and time in ms/ns or sec??? The answer is hidden in that! — Am_I_Helpful, Sep 09 '14 at 17:54
I'm new to programming, but i found it's a return double second. In that way it makes sense to /1000 because most of the values are 0.001 - 0.005. Thanks ! — , Sep 09 '14 at 18:00
@dz3k If it a `double` type, that is because you are using `double` types. A simpler alternative is to use `long t0 = System.currentTimeMillis()`. btw why are you timing how long the print statement takes? You realise the calculation is less than 1/1000th the work that your method is doing. — Peter Lawrey, Sep 09 '14 at 18:02
Note: using the difference of elapse times, is the same as the difference of times. — Peter Lawrey, Sep 09 '14 at 18:07
@PeterLawrey For school I tried 2 methods to calculate the Fibonacci algorithm. It came down to having an old method that took hours to calculate a index of around >45. I used this timer to compare the time for both the methods to calculate the algorithm. — , Sep 09 '14 at 18:10

score 1 · Answer 1 · edited May 23 '17 at 12:31

1

The expression you use for calculating the variable lapTime can be simplified, and you've posted the simplest representation it can have.

lapTime = (1000 * t1 - 1000 * t0) / 1000;

Can instead be :

lapTime = t1 - t0;

Which can be determined through simple algebra. It's even possible, given that t1 and t0 are double that the two expressions could result in a different value even if they mathematically equivalent. See here.

As far as the problem you're trying to solve, measuring the execution time of a Java program, there be dragons. Here's my own attempt at measuring with a micro-benchmark, which I ultimately believe was a failure.

edited May 23 '17 at 12:31

Community

1
1

answered Sep 09 '14 at 18:31

jdphenix

15,022
3
41
74

Your answer is correct but your explanation can be incorrect if some other datatypes are involved like int,double,etc. So,you shouldn't out points related to `simple algebra`! ALso,check my answer for more insight! – Am_I_Helpful Sep 09 '14 at 18:34
@shekharsuman As stated, without clarification on data types no answer can be 100% _absolutely positively correct_. Making points about fundamental mathematics is valid, especially with the behavior that comes with using floating-point values. – jdphenix Sep 09 '14 at 18:38
Actually,OP gave datatypes as of double type as return type of `elaapsedTime()` method! You must check comments beneath OP's question! – Am_I_Helpful Sep 09 '14 at 18:40
good point of editing question!Please modify your answer accordingly,I'll upvote your answer! – Am_I_Helpful Sep 09 '14 at 18:44
Please remove that point,related to floating point as time will be bounded and won't ever be something like `0.333...`... I already mentioned that your answer seems correct,but floating point condition doesn't suit this question. – Am_I_Helpful Sep 09 '14 at 18:48

score 0 · Accepted Answer · edited May 23 '17 at 11:50

This belongs to Stopwatch class from Java Princeton Stdlib. This class is meant to measure the time of the execution of an algorithm. The implementation goes like this (removed comments and such data):

public class Stopwatch { 

    private final long start;

    public Stopwatch() {
        start = System.currentTimeMillis();
    } 

    public double elapsedTime() {
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }
}

Since it uses System.currentTimeMillis() it will work with milliseconds. But the elapsedTime method already convert it back to seconds but as a double. So your current formula:

lapTime = (1000 * t1 - 1000 * t0) / 1000;

Is making sure to convert the data into a pure double operation. So, the formula can be rewritten as:

lapTime = t1 - t0;

With no problem.

Note that still this is not the right way to measure time of execution for Java code. You should use System.nanoTime() instead.

More info:

How do I measure time elapsed in Java?

Going deeper to understand if there's no difference between these operations, let's create a basic test:

public class FormulaTest {
    static double formula1(double t0, double t1) {
        return (1000 * t1 - 1000 * t0) / 1000;
    }

    static double formula2(double t0, double t1) {
        return t1 - t0;
    }

    static void printResults(double t0, double t1) {
        System.out.println("t0: " + t0);
        System.out.println("t1: " + t1);
        System.out.println("Formula1: " + formula1(t0, t1));
        System.out.println("Formula2: " + formula1(t0, t1));
        System.out.println("---------------------------------------------------");
    }

    public static void main(String[] args) throws java.lang.Exception {
        // your code goes here
        printResults(0, 10);
        printResults(System.currentTimeMillis(), System.currentTimeMillis());
        printResults(System.currentTimeMillis(), System.currentTimeMillis() + 142);
        printResults(1.7976931348623157e+300 - 5000, 1.7976931348623157e+300);
        printResults(
            109999999999999999999999999999999999999999999999999999999999999999999999.0,
            119999999999999999999999999999999999999999999999999999999999999999999999.0);
        printResults(
            10.9999999999999999999999999999999999999999999999999999999999999999999999,
            11.9999999999999999999999999999999999999999999999999999999999999999999999);
        printResults(
            823145321462149234.651985149616914621346234923149621346921394613293423951932415934159213226314,
            844329146321496321.532159341563149513495139159341593415793415431951349513891585443951391593151);
        printResults(
            82314532.1462149234651985149616914621346234923149621346921394613293423951932415934159213226314,
            84432914.6321496321532159341563149513495139159341593415793415431951349513891585443951391593151);
        printResults(1.7976931348623157e+307, 4.9e-323);
        printResults(Double.MAX_VALUE, Double.MAX_VALUE);
        printResults(Double.MIN_VALUE - 10, Double.MIN_VALUE);
    }
}

Output:

t0: 0.0
t1: 10.0
Formula1: 10.0
Formula2: 10.0
---------------------------------------------------
t0: 1.410290897577E12
t1: 1.410290897577E12
Formula1: 0.0
Formula2: 0.0
---------------------------------------------------
t0: 1.410290897577E12
t1: 1.410290897719E12
Formula1: 142.0
Formula2: 142.0
---------------------------------------------------
t0: 1.7976931348623156E300
t1: 1.7976931348623156E300
Formula1: 0.0
Formula2: 0.0
---------------------------------------------------
t0: 1.1E71
t1: 1.2E71
Formula1: 9.999999999999985E69
Formula2: 9.999999999999985E69
---------------------------------------------------
t0: 11.0
t1: 12.0
Formula1: 1.0
Formula2: 1.0
---------------------------------------------------
t0: 8.2314532146214925E17
t1: 8.4432914632149632E17
Formula1: 2.1183824859347024E16
Formula2: 2.1183824859347024E16
---------------------------------------------------
t0: 8.231453214621492E7
t1: 8.443291463214964E7
Formula1: 2118382.4859347227
Formula2: 2118382.4859347227
---------------------------------------------------
t0: 1.7976931348623158E307
t1: 4.9E-323
Formula1: -Infinity
Formula2: -Infinity
---------------------------------------------------
t0: 1.7976931348623157E308
t1: 1.7976931348623157E308
Formula1: NaN
Formula2: NaN
---------------------------------------------------
t0: -10.0
t1: 4.9E-324
Formula1: 10.0
Formula2: 10.0
---------------------------------------------------

Not even at edge cases Double.MAX_VALUE and Double.MIN_VALUE are differences between the results of the formula. Even when the result is -Infinity or NaN (not a number).

In short: use the last formula:

lapTime = t1 - t0;

+0 "Is making sure to convert the data into a pure int operation." this is not converting the `double` into an `int` or a `long` — Peter Lawrey, Sep 09 '14 at 18:07
Even your answer is wrong,the datatype for t0 and t1 ca't be assumed `long`,unless OP clarifies! I have chnged my votes,a -1 to you! — Am_I_Helpful, Sep 09 '14 at 18:09
You have demonstrated that `t0` and `t1` must be `double`, see `double elapseTime()` not `long` and if it was `long` multiplying by 1000 wouldn't make any difference. As it is `double` doing `1000 * ` would still be a double. — Peter Lawrey, Sep 09 '14 at 18:12
Note: I suspect the original author may have intended that it "Is making sure to convert the data into a pure long operation" but is not actually doing that. — Peter Lawrey, Sep 09 '14 at 18:15

Jean Logeart · Answer 3 · 2014-09-09T18:07:38.990

-1

Well it should be.

(a * x - a * y) / a == (x - y) * a / a == x - y

In your case:

(1000 * t1 - 1000 * t0) / 1000 == (t1 - t0) * 1000 / 1000 == t1 - t0

So writing lapTime = t1-t0 is a good idea as it makes the code easier to understand.

In addition, you also avoid risking overflowing long by not multiplying by 1000 any more.

edited Sep 09 '14 at 18:07

answered Sep 09 '14 at 17:58

Jean Logeart

52,687
11
83
118

Because the answer is not `synced` with question as well as the answer is a poor summary!!! – Am_I_Helpful Sep 09 '14 at 18:03
@JeanLogeart perhaps you could use `-` instead of `+` in your explanation. – Peter Lawrey Sep 09 '14 at 18:03
@JeanLogeart-See Luiggi's answer. – Am_I_Helpful Sep 09 '14 at 18:06
@PeterLawrey-i doubt how this answer was upvoted 3 times,check Luiggi's answer! I can't believe even you support this answer!!! – Am_I_Helpful Sep 09 '14 at 18:07
@shekharsuman Given Luggi's explanation is non-sense, I don't see how it got upvoted. – Peter Lawrey Sep 09 '14 at 18:09
@PeterLawrey-SORRY,I downvoted his also,that's pure CRAP!!! But,neither is this OK, One can't assume t1 and t0 to be of long type unless OP clarifies! I can very well claim that program execution time can be of even int/double unless clarified! – Am_I_Helpful Sep 09 '14 at 18:11
When I try lapTime = t1-t0; StdOut.println(" (" + lapTime + "\t " + t1 + ")"); The decimals can be quite big for example (@ index 40 value is): 0.5030000000000001 But if i use the formula: 0.504 – Sep 09 '14 at 18:26
@PeterLawrey-Kindly check my answer and place some comments if free to do so! – Am_I_Helpful Sep 09 '14 at 18:33

Java Fibonacci - elapsedTime(); formula

3 Answers3