How to get decimal form of largest known prime?

David Fraser 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)

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

> "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
>>(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.



More information about the Python-list mailing list