How to get decimal form of largest known prime?

D

Daniel Yoo

: According to latest news the largest known prime is:
: 2**24036583 - 1
: (right?)

: Do someone of you know how long would it take on
: a 2.8 GHz Pentium 4 machine to write a _decimal_ form
: (hexadecimal form can be written in less than one second)
: of this prime to a file and what should be the Python code
: to use for it?

Hi Claudio,


Let's see... how many digits would it be?

###.... return int(math.log(n) / math.log(10)) + 1
....733485
###

Ok, that doesn't sound too bad at all. It's about 750,000 digits long.


It's actually not difficult to get the last decimal digit of this
humongous number:

###7L
###


It's also not too difficult to get the second to last digit of this
number:

###0L
###

At least we can figure out that the number ends with a '07'. If we
continue this way, we can quickly get the other digits.


Hope this helps!
 
D

Daniel Yoo

: : According to latest news the largest known prime is:
: : 2**24036583 - 1
: : (right?)


: Let's see... how many digits would it be?

: ###
:>>> def digits(n):
: ... return int(math.log(n) / math.log(10)) + 1
: ...
:>>> x = 2**2436583 - 1
:>>> digits(x)
: 733485
: ###

: Ok, that doesn't sound too bad at all. It's about 750,000 digits long.


Yikes. I introduced an order-of-magnitude bug when defining x. Let
me recalculate that:

###7235733
###

Ok, so there's about 7 million digits in that thing. Slightly more
difficult to print out. *grin*


My apologies for the mistake!
 
I

Irmen de Jong

Daniel said:
[...]

0L
###

At least we can figure out that the number ends with a '07'. If we
continue this way, we can quickly get the other digits.
^^^^^^^
Sadly, no you can't. Just try it ;-)
.... print (x/i)%10,
.... i*=10
....
7 0 4 9 6 9 5 4 4 4 1 8...... slower and slower.....

--Irmen
 
C

Claudio Grondi

According to latest news the largest known prime is:
2**24036583 - 1
(right?)

Do someone of you know how long would it take on
a 2.8 GHz Pentium 4 machine to write a _decimal_ form
(hexadecimal form can be written in less than one second)
of this prime to a file and what should be the Python code
to use for it?

Claudio
P.S. file.write( '%i' % (2**24036583 - 1,) )
takes 100% CPU for a long time without any result
and the critical part is the '%i' % (2**24036583 - 1,)
conversion.
 
C

Carl Banks

Daniel said:
Yikes. I introduced an order-of-magnitude bug when defining x. Let
me recalculate that:

###
7235733
###

Ok, so there's about 7 million digits in that thing. Slightly more
difficult to print out. *grin*

It's usually easier than that to get an estimate: the number of digits
in 2**n is roughly n/3 (n/3.32192809488736234786 to be exact. :).
 
R

Rick Holbert

So, something like this?

x = 2**2436583 - 1

while x > 0:
print x%10,
x/=10
Daniel said:
x = 2**2436583 - 1 [...]

(x / 10) % 10

0L
###

At least we can figure out that the number ends with a '07'. If we
continue this way, we can quickly get the other digits.
^^^^^^^
Sadly, no you can't. Just try it ;-)
i=1
while True:
... print (x/i)%10,
... i*=10
...
7 0 4 9 6 9 5 4 4 4 1 8...... slower and slower.....

You should perform destructive division.
 
R

Rick Holbert

Yes, for base ten the ratio can be computed as follows:

from math import log

print log(10)/log(2)
 
D

Duncan Booth

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.
 
D

David Fraser

Claudio said:
If I understand right all your responses
there is no way to get the decimal form
of the prime within let me say minutes?
Any other ideas how to get it similar fast
as the hexadecimal form?
I think it's clear from other posts that this is an *algorithmic*
question. The question is not just how to express this in Python, it is
whether there is a faster-than-quadratic approach to converting binary
numbers to decimal. It just happens to be a one-liner to tell Python to
do it, but its a fairly complex problem to optimize it.
Also note that the hexadecimal form is very simple - 7 followed by loads
of ffffffff (any power of 2, - 1 will follow a similar pattern, possibly
with a different leading digit)
Claudio
P.S. the divmod() approach takes about
four hours on a Pentium 4 2.8 GHz with
400 MHz dual RAM, where on Pentium III
900 MHz with 100 MHz RAM it lasts
twice so long... mhhh... Is Pentium 4
slower than Pentium III running Pythons
divmod() (compared at same Hz)?
Yes, processing speed is not neccessarily linearly dependent on clock
speed. This may be because this problem ends up using more memory access
in Python, and the memory access process is more complicated than the
RAM speed reflects.
 
C

Claudio Grondi

If I understand right all your responses
there is no way to get the decimal form
of the prime within let me say minutes?
Any other ideas how to get it similar fast
as the hexadecimal form?

Claudio
P.S. the divmod() approach takes about
four hours on a Pentium 4 2.8 GHz with
400 MHz dual RAM, where on Pentium III
900 MHz with 100 MHz RAM it lasts
twice so long... mhhh... Is Pentium 4
slower than Pentium III running Pythons
divmod() (compared at same Hz)?
 
?

=?ISO-8859-1?Q?Gr=E9goire_Dooms?=

Claudio said:
If I understand right all your responses
there is no way to get the decimal form
of the prime within let me say minutes?
Any other ideas how to get it similar fast
as the hexadecimal form?
If speed is the matter, go for C:

with the GNU MP library use
void mpz_pow_ui (mpz_t rop, mpz_t base, unsigned long int exp) and
char * mpz_get_str (char *str, int base, mpz_t op)

I did a small contest about the decimal repr of 2**1000000 a a couple
years ago. A few languages were compared on a time-to-result basis.
Python won with 7 minutes (10 sec devel, 6:50 comput.) and
C + GMP was second: 15 min devel(including reading the doc) + a few sec
of comput.
I bet you can expect a 30-100 fold speedup using C + GMP compared to
python -c 'print 2**24036583 - 1'

If you try this approach I'd like to know which results you get.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top