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 = 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
More information about the Python-list
mailing list