Java Fibonacci - elapsedTime (); formula
I am working on a small project for the fibonacci algorithm.
I am using the following method to calculate the algorithm. Note what a elapsedTime()
returns 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 to the algorithm itself - it is being fixed. I just don't understand the formula for lapTime. Why can't he be
lapTime = t1-t0;
This refers to the Stopwatch
class from Java Princeton Stdlib . This class is designed to measure the execution time of an algorithm. The implementation goes like this (deleted comments and data like this):
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 is using System.currentTimeMillis()
it will run in milliseconds. But the method is elapsedTime
already converting it back to seconds, but how double
. So your current formula is:
lapTime = (1000 * t1 - 1000 * t0) / 1000;
It is imperative to convert the data to a pure operation double
. Thus, the formula can be rewritten as:
lapTime = t1 - t0;
No problem.
Note that this is still the wrong way to measure the execution time of Java code . Should be used instead System.nanoTime()
.
Additional Information:
Going deeper, to see if there is any 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
---------------------------------------------------
Even in edge cases Double.MAX_VALUE
, Double.MIN_VALUE
there are differences between the results of the formula. Even if the result is -Infinity
or NaN
(not a number).
In short: use the last formula:
lapTime = t1 - t0;
source to share
You can simplify the expression you are using to evaluate the variable lapTime
and you have posted the simplest view it can have.
lapTime = (1000 * t1 - 1000 * t0) / 1000;
Instead it could be:
lapTime = t1 - t0;
This can be determined using simple algebra. It is even possible, given what t1
and t0
are double
, that the two expressions can lead to a different value, even if they are mathematically equivalent. See here .
As for the problem you are trying to solve by measuring the execution time of a Java program, there are dragons . Here is my own attempt at measuring with a micro benchmark, which I find ultimately unsuccessful.
source to share
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
Thus, writing lapTime = t1-t0
is a good idea as it makes the code easier to understand.
Moreover, you also avoid the risk of overflow long
without increasing 1000
.
source to share