package algs14;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac DoublingRatio.java
 *  Execution:    java DoublingRatio
 *  Dependencies: ThreeSum.java Stopwatch.java StdRandom.java StdOut.java
 *
 *
 *  % java DoublingRatio
 *      512 6.48
 *     1024 8.30
 *     2048 7.75
 *     4096 8.00
 *     8192 8.05
 *   ...
 *
 *************************************************************************/

public class DoublingRatio {
  public static double timeTrial(int N) {
    int MAXVAL = 1000000;
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = StdRandom.uniform(-MAXVAL, MAXVAL);
    }
    int T = 1; // number of tests
    double sum = 0;
    for (int t = 0; t < T; t++) {
      Stopwatch s = new Stopwatch();
      //XOneSum.count (a);
      //XTwoSum.count (a);
      ThreeSum.count(a);
      //XFourSum.count(a);
      //XTwoSumFast.count (a);
      //ThreeSumFast.count (a);
      sum +=  s.elapsedTime();
    }
    return sum/T;
  }

  private static final int MIN = 125;
  private static final int MAX = Integer.MAX_VALUE/2;
  //private static final int MAX = 32768000;
  //private static final int MAX = 1024000;
  //private static final int MAX = 64000;
  public static void main(String[] args) {
    double prev = timeTrial(MIN);
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format("%,13d %10.3f %10.3f\n", N, time, time/prev);
      prev = time;
    }
  }
}