001package algs14;
002import stdlib.*;
003public class XCountingLoops {
004        // To Print: StdOut.printf ("N=%3d i=%3d N-i=%d\n", N, i, N-i);
005        //
006        // Test variant with one, two or three nested loops
007        //
008        // Outermost:
009        // for (long i = 1; i <= N; i = i+1) {
010        // for (long i = 1; i <= N; i = i*2) {
011        //
012        // Next:
013        // for (long j = 1; j <= N; j = j+1) {
014        // for (long j = 1; j <= i; j = j+1) {
015        // for (long j = 1; j <= N; j = j*2) {
016        // for (long j = 1; j <= i; j = j*2) {
017        //
018        // Next:
019        // for (long k = 1; k <= N; k = k+1) {
020        // for (long k = 1; k <= j; k = k+1) {
021        // for (long k = 1; k <= N; k = k*2) {
022        // for (long k = 1; k <= j; k = k*2) {
023
024        // f counts the number of times the innermost loop executes 
025        static long f (long N) {
026                long result = 0;
027                for (long i = 1; i <= N; i = i+1) {
028                        for (long j = 1; j <= N; j = j+1) {
029                                result = result+1;
030                                if (N <= 64) StdOut.format ("%02d ", i);
031                        }
032                        if (N <= 64) StdOut.println ();
033                }
034                return result;
035        }
036        public static void main (String[] args) {
037                f(16);
038
039                long MIN = 256L; // for powers of ten, start with 500L
040                long MAX = 3_200_000_000L;
041                Stopwatch sw = new Stopwatch ();
042                double prevCount = f(MIN);
043                double prevTime = sw.elapsedTime ();
044                for (long N = MIN*2; N <= MAX; N=N*2) {
045                        sw = new Stopwatch ();
046                        long count = f(N);
047                        double time = sw.elapsedTime ();
048                        StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime);
049                        //StdOut.format ("Elapsed count f(%,13d): %,16d: %10.3f\n", N, count, count / prevCount);
050                        prevCount = count;
051                        prevTime = time;
052                }
053        }
054}