Message7660

The following code, which formats an increasingly large number as hexadecimal

###############

import time

for power in range(0, 23):
    start = time.time()
    s = "%x" % (2**(2**power))
    print "%d (%d digits) took %1.3lf seconds" % (power, len(s), (time.time() - start))

###############

gives the following output

0 (1 digits) took 0.000 seconds
1 (1 digits) took 0.000 seconds
2 (2 digits) took 0.000 seconds
3 (3 digits) took 0.000 seconds
4 (5 digits) took 0.000 seconds
5 (9 digits) took 0.000 seconds
6 (17 digits) took 0.000 seconds
7 (33 digits) took 0.000 seconds
8 (65 digits) took 0.000 seconds
9 (129 digits) took 0.000 seconds
10 (257 digits) took 0.015 seconds
11 (513 digits) took 0.000 seconds
12 (1025 digits) took 0.000 seconds
13 (2049 digits) took 0.000 seconds
14 (4097 digits) took 0.016 seconds
15 (8193 digits) took 0.047 seconds
16 (16385 digits) took 0.125 seconds
17 (32769 digits) took 0.531 seconds
18 (65537 digits) took 2.031 seconds
19 (131073 digits) took 8.188 seconds
20 (262145 digits) took 33.328 seconds
21 (524289 digits) took 138.281 seconds
22 (1048577 digits) took 625.562 seconds

This appears to be O(N^2)