CSC300 / CSC402: 2D lg(N) * lg(N) [7/18] Previous pageContentsNext page

01
02
03
04
05
    for (long i = 1; i <= N; i = i*2) {
      for (long j = 1; j <= N; j = j*2) {
        result = result+1;
      }
    }

Output

01 01 01 01 01 
02 02 02 02 02 
04 04 04 04 04 
08 08 08 08 08 
16 16 16 16 16 











Elapsed count f(          512):              100:      1.235 [     0.000 :        NaN]
Elapsed count f(        1,024):              121:      1.210 [     0.000 :        NaN]
Elapsed count f(        2,048):              144:      1.190 [     0.000 :        NaN]
Elapsed count f(        4,096):              169:      1.174 [     0.000 :        NaN]
Elapsed count f(        8,192):              196:      1.160 [     0.000 :        NaN]
Elapsed count f(       16,384):              225:      1.148 [     0.000 :        NaN]
Elapsed count f(       32,768):              256:      1.138 [     0.000 :        NaN]
Elapsed count f(       65,536):              289:      1.129 [     0.000 :        NaN]
Elapsed count f(      131,072):              324:      1.121 [     0.000 :        NaN]
Elapsed count f(      262,144):              361:      1.114 [     0.000 :        NaN]
Elapsed count f(      524,288):              400:      1.108 [     0.000 :        NaN]
Elapsed count f(    1,048,576):              441:      1.103 [     0.000 :        NaN]
Elapsed count f(    2,097,152):              484:      1.098 [     0.000 :        NaN]
Elapsed count f(    4,194,304):              529:      1.093 [     0.000 :        NaN]
Elapsed count f(    8,388,608):              576:      1.089 [     0.000 :        NaN]
Elapsed count f(   16,777,216):              625:      1.085 [     0.000 :        NaN]
Elapsed count f(   33,554,432):              676:      1.082 [     0.000 :        NaN]
Elapsed count f(   67,108,864):              729:      1.078 [     0.000 :        NaN]
Elapsed count f(  134,217,728):              784:      1.075 [     0.000 :        NaN]
Elapsed count f(  268,435,456):              841:      1.073 [     0.000 :        NaN]
Elapsed count f(  536,870,912):              900:      1.070 [     0.001 :   Infinity]
Elapsed count f(1,073,741,824):              961:      1.068 [     0.000 :      0.000]
Elapsed count f(2,147,483,648):            1,024:      1.066 [     0.000 :        NaN]

This is log squared: ~ lg(N) * lg(N)

Previous pageContentsNext page