001package algs14;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac DoublingRatioLong.java
005 *  Execution:    java DoublingRatioLong
006 *  Dependencies: Stopwatch.java StdOut.java
007 *
008 *  This version is suited for testing functions that require very large N
009 *  to run long enough to measure.
010 *
011 *  % java DoublingRatioLong
012 *      512 6.48
013 *     1024 8.30
014 *     2048 7.75
015 *     4096 8.00
016 *     8192 8.05
017 *   ...
018 *
019 *************************************************************************/
020
021public class DoublingRatioLong {
022        static private long f1 (long N) {
023                long sum = 0;
024                for (long i = 1; i <= N; i += 1) {
025                        sum++;
026                }
027                return sum;
028        }
029        static private long f2(long N) {
030                long sum = 0;
031                for (long i = 1; i <= N; i += 1) {
032                        for (long j = 1; j <= N; j += 1) {
033                                sum++;
034                        }
035                }
036                return sum;
037        }
038        static private long f3(long N) {
039                long sum = 0;
040                for (long i = 1; i <= N; i += 1) {
041                        for (long j = i; j <= N; j += 1) {
042                                for (long k = j; k <= N; k += 1) {
043                                        sum++;
044                                }
045                        }
046                }
047                return sum;
048        }
049        public static double timeTrial(long N) {
050                long T = 1; // number of tests
051                double sum = 0;
052                for (long t = 0; t < T; t++) {
053                        Stopwatch s = new Stopwatch();
054                        //sum += f1(N);
055                        f1(N);  sum +=  s.elapsedTime();
056                }
057                return sum/T;
058        }
059
060        private static final long MIN = 10;
061        private static final long MAX = 40960L;
062        //private static final long MAX = Long.MAX_VALUE/2;
063        public static void main(String[] args) {
064                double prev = timeTrial(MIN);
065                for (long N = MIN*2; N<=MAX; N += N) {
066                        double time = timeTrial(N);
067                        StdOut.format("%19d %9.3f %5.1f\n", N, time, time/prev);
068                        prev = time;
069                }
070        }
071}
072