01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package algs14;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac DoublingRatioLong.java
 *  Execution:    java DoublingRatioLong
 *  Dependencies: Stopwatch.java StdOut.java
 *
 *  This version is suited for testing functions that require very large N
 *  to run long enough to measure.
 *
 *  % java DoublingRatioLong
 *      512 6.48
 *     1024 8.30
 *     2048 7.75
 *     4096 8.00
 *     8192 8.05
 *   ...
 *
 *************************************************************************/

public class DoublingRatioLong {
  static private long f1 (long N) {
    long sum = 0;
    for (long i = 1; i <= N; i += 1) {
      sum++;
    }
    return sum;
  }
  static private long f2(long N) {
    long sum = 0;
    for (long i = 1; i <= N; i += 1) {
      for (long j = 1; j <= N; j += 1) {
        sum++;
      }
    }
    return sum;
  }
  static private long f3(long N) {
    long sum = 0;
    for (long i = 1; i <= N; i += 1) {
      for (long j = i; j <= N; j += 1) {
        for (long k = j; k <= N; k += 1) {
          sum++;
        }
      }
    }
    return sum;
  }
  public static double timeTrial(long N) {
    long T = 1; // number of tests
    double sum = 0;
    for (long t = 0; t < T; t++) {
      Stopwatch s = new Stopwatch();
      //sum += f1(N);
      f1(N);  sum +=  s.elapsedTime();
    }
    return sum/T;
  }

  private static final long MIN = 10;
  private static final long MAX = 40960L;
  //private static final long MAX = Long.MAX_VALUE/2;
  public static void main(String[] args) {
    double prev = timeTrial(MIN);
    for (long N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format("%19d %9.3f %5.1f\n", N, time, time/prev);
      prev = time;
    }
  }
}