CSC300: 2D Flat Pack [5/19] Previous pageContentsNext page

01
02
03
04
05
    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

Previous pageContentsNext page