Home Original page

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