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}