strings with moreover of one million of characters

Josiah Carlson jcarlson at nospam.uci.edu
Wed Feb 18 20:49:32 CET 2004


run the following:

import time
for i in xrange(1000, 1000000, 1000):
     a = '1'+i*'0'
     t = time.time()
     c = long(a)
     print i, time.time()-t

Here is some output I get with a 1.7 ghz machine:
67000 3.03100013733
68000 3.10899996758
69000 3.125
70000 3.26499986649
71000 3.39100003242
72000 3.42199993134
73000 3.5
74000 3.65599989891
75000 3.71900010109
76000 3.79600000381
77000 3.93700003624

It is not so much that it cannot do it, it is that it is REALLY slow. 
You will find that this is the case for ALL infinite precision integer 
packages.  Unless the internal representation is equivalent to the 
external representation, the conversion will be slow.

Given 'mylong', which assumes base-16 numbers, which are relatively 
compatible with the internal representation, and generates the long 
integer like so:

def mylong(st):
     r = 0
     for i in xrange(len(st)):
         r += int(st[-i]) * 16**i
     return r

It actually becomes possible to do this in reasonable time:
1000000 0.0
1100000 0.0160000324249
1200000 0.0
1300000 0.0
1400000 0.0
1500000 0.0
1600000 0.0
1700000 0.0
1800000 0.0
1900000 0.0

Base conversion is, in general, a hard problem.  There are some tricks 
to make it fast, but those tricks are very specific.

  - Josiah



More information about the Python-list mailing list