How to get decimal form of largest known prime?
Duncan Booth
me at privacy.net
Fri Jun 11 09:24:10 EDT 2004
Rick Holbert <holbertr at dma.org> wrote in
news:cac91i$5st$1 at charm.magnus.acs.ohio-state.edu:
> So, something like this?
>
> x = 2**2436583 - 1
>
> while x > 0:
> print x%10,
> x/=10
>
If you want to convert a large number to a decimal string reasonably
quickly you should do the conversion recursively and divide by numbers much
larger than 10. For example, the code below will outperform str(x)
significantly for numbers larger than about 2**10000 (according to
timeit.py) and has plenty of scope for further optimisation. It will still
take a very long time for 2**24036583 - 1: I haven't timed it, but even
precalculating the powers list grinds to a halt beyond about 17 or 18
elements.
def toDecimal(x):
digits = 48
powers = [ 10**digits ]
result = []
format = "%%0%dd" % (2*digits)
while x > powers[-1]:
powers.append( 10 ** (digits * 2**len(powers)))
def convert(x, index):
if x==0:
if not result:
return # Ignore leading zeros
result.append('0' * (digits * 2**(index+1)))
return
if index > 0:
q, r = divmod(x, powers[index])
convert(q, index-1)
convert(r, index-1)
else:
result.append(format % x)
if x==0: return '0'
convert(x, len(powers)-1)
result[0] = result[0].lstrip('0')
return ''.join(result)
Notes: the value used for 'digits' is critical. Multiples of 12 seem to
work best for me with 24, 48 or 96 being about best. The calculation of
powers should be done once and cached (preferably outside the program), but
it is still a bottleneck when they get sufficiently large. Squaring the
last element of powers each time is an alternative way to calculate it but
doesn't seem to be any faster.
More information about the Python-list
mailing list