How to get decimal form of largest known prime?

[Tim Peters]

[Tim Peters]
>> The fastest pure-Python solution I've found consumed about 20 CPU minutes
>> ...

[Claudio Grondi]
> I have already used such approach (see code below), but was not able to
> get any improvement, even the opposite because of increase of time needed
> for calculation for each next iteration step.
>
> Is my code not well designed? What is the difference to yours? (consider
> please, that I started with Python some weeks ago and just trying to
> check out the advantages and the limits)

Sorry, I really can't make time to review unfamiliar code today.  Instead
I'll just show the code I used.  It implements just enough of the BigDec
class to get the problem solved (multiplication, power, and squaring), but
in a general way (i.e., __mul__(), __pow__() and square() don't rely on any
specifics of the problem instance).  Note that BigDec instances are (like
all numeric types in Python) conceptually immutable.

# Compute in decimal, using 5,000-digit "digits".
EXP = 5000
BASE = (5L ** EXP) << EXP  # 10**EXP

class BigDec(object):
    def __init__(self, digits):
        # digits is a list of base-BASE digits, least-
        # significant first.
        self.digits = digits

    def __mul__(self, other):
        # Force 'other' to have the fewer # of digits.
        if len(self.digits) < len(other.digits):
            self, other = other, self
        # Straightforward cross-product.  Don't worry about digits
        # getting out of range for the duration.
        result = [0] * (len(self.digits) + len(other.digits) - 1)
        for baseindex, otherdigit in enumerate(other.digits):
            for i, selfdigit in enumerate(self.digits):
                result[baseindex + i] += selfdigit * otherdigit
        normalize(result)
        return BigDec(result)

    __imul__ = __mul__

    def __pow__(self, n):
        # "The usual" left-to-right efficient exponentiation algorithm.
        # n must be vanilla integer, not BigDec.
        mask = 1L
        while mask <= n:
            mask <<= 1
        mask >>= 1  # position of n's most-significant bit
        result = BigDec([1])
        while mask:
            result = result.square()
            if n & mask:
                result *= self
            mask >>= 1
        return result

    def square(self):
        # Efficient divide-and-conquer squaring, based on
        # (a*x+b)**2 = a**2*x**2 + 2*a*b*x + b**2.
        n = len(self.digits)
        if n <= 5:
            return self * self
        nlo = n // 2
        lo, hi = BigDec(self.digits[:nlo]), BigDec(self.digits[nlo:])
        result = lo.square().digits
        result += [0] * (2*nlo - len(result))
        result += hi.square().digits
        for elt in (lo * hi).digits:
            result[nlo] += elt << 1
            nlo += 1
        normalize(result)
        return BigDec(result)

    def __str__(self):
        result = map(str, self.digits)
        # Pad all digits except for the MSD with leading zeroes.
        for i in xrange(len(result) - 1):
            digit = result[i]
            if len(digit) < EXP:
                result[i] = "0" * (EXP - len(digit)) + digit
        result.reverse()
        return "".join(result)

def normalize(x):
    # Force the digits in x into range(BASE), by propagating
    # carries.  x is modified in-place.
    carry = 0
    for i, elt in enumerate(x):
        carry += elt
        carry, x[i] = divmod(carry, BASE)
    while carry >= BASE:
        carry, leftover = divmod(carry, BASE)
        x.append(leftover)
    if carry:
        x.append(carry)
    # Strip insignificant leading 0 digits.
    while x and x[-1] == 0:
        x.pop()

x = BigDec([2]) ** 24036583
# subtract 1
assert x.digits[0] != 0
x.digits[0] -= 1

print x