# How to get decimal form of largest known prime?

Tim Peters tim.one at comcast.net
Sun Jun 13 23:49:10 CEST 2004

```[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 >>= 1  # position of n's most-significant bit
result = BigDec([1])
result = result.square()
result *= self
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)
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

```