How to get decimal form of largest known prime?
davidf at sjsoft.com
Fri Jun 11 23:39:36 CEST 2004
Claudio Grondi wrote:
> 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)
> 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.
> "Claudio Grondi" <claudio.grondi at freenet.de> schrieb im Newsbeitrag
> news:2is27mFqeen8U1 at uni-berlin.de...
>>According to latest news the largest known prime is:
>> 2**24036583 - 1
>>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?
>>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,)
More information about the Python-list