| CSC300: 2D Flat Pack [5/19] | |
01 |
for (long i = 1; i <= N; i = i*2) { for (long j = 1; j <= i; j = j+1) { result = result+1; } } |
Output
01 02 02 04 04 04 04 08 08 08 08 08 08 08 08 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 Elapsed count f( 512): 1,023: 2.002 [ 0.000 : NaN] Elapsed count f( 1,024): 2,047: 2.001 [ 0.000 : NaN] Elapsed count f( 2,048): 4,095: 2.000 [ 0.001 : Infinity] Elapsed count f( 4,096): 8,191: 2.000 [ 0.000 : 0.000] Elapsed count f( 8,192): 16,383: 2.000 [ 0.001 : Infinity] Elapsed count f( 16,384): 32,767: 2.000 [ 0.003 : 3.000] Elapsed count f( 32,768): 65,535: 2.000 [ 0.001 : 0.333] Elapsed count f( 65,536): 131,071: 2.000 [ 0.003 : 3.000] Elapsed count f( 131,072): 262,143: 2.000 [ 0.000 : 0.000] Elapsed count f( 262,144): 524,287: 2.000 [ 0.001 : Infinity] Elapsed count f( 524,288): 1,048,575: 2.000 [ 0.001 : 1.000] Elapsed count f( 1,048,576): 2,097,151: 2.000 [ 0.002 : 2.000] Elapsed count f( 2,097,152): 4,194,303: 2.000 [ 0.003 : 1.500] Elapsed count f( 4,194,304): 8,388,607: 2.000 [ 0.010 : 3.333] Elapsed count f( 8,388,608): 16,777,215: 2.000 [ 0.019 : 1.900] Elapsed count f( 16,777,216): 33,554,431: 2.000 [ 0.033 : 1.737] Elapsed count f( 33,554,432): 67,108,863: 2.000 [ 0.041 : 1.242] Elapsed count f( 67,108,864): 134,217,727: 2.000 [ 0.092 : 2.244] Elapsed count f( 134,217,728): 268,435,455: 2.000 [ 0.169 : 1.837] Elapsed count f( 268,435,456): 536,870,911: 2.000 [ 0.292 : 1.728] Elapsed count f( 536,870,912): 1,073,741,823: 2.000 [ 0.553 : 1.894] Elapsed count f(1,073,741,824): 2,147,483,647: 2.000 [ 1.149 : 2.078] Elapsed count f(2,147,483,648): 4,294,967,295: 2.000 [ 2.284 : 1.988]
This is linear: ~ 2N
More accurately: 2N - 1