How to get decimal form of largest known prime?

[David Fraser]

Tim Peters wrote:
> [Grégoire Dooms]
> 
>>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)
> 
> 
> There are some GMP wrappers for Python.  Using Marc-Andre Lemburg's mxNumber
> wrapper (which is maximally convenient for me on Windows, since it includes
> a precompiled-for-Windows GMP), the OP's task is spelled like so:
> 
> 
>>>>from mx.Number import *
>>>>Integer(2)**24036583 - 1
> 
> 
> That does call mpz_pow_ui() and mpz_get_str() (with base=10) under the
> covers.
> 
> Since I typed that in, the process has accumulated 59 CPU minutes, with no
> output yet.
> 
> Curiously,
> 
> 
>>>>x = Integer(2)**24036583 - 1
> 
> 
> consumes 112 CPU seconds on its own, while the straight Python
> 
> 
>>>>x = 2**24036583 - 1
> 
> 
> consumes only 2 CPU seconds -- so Python is 50+ times faster than this GMP
> for the computational part.  Python's Karatsuba multiplication gets enormous
> benefit out of special-casing zeroes in this particular case (all the
> squarings when computing the power see an input whose least-significant half
> is entirely zero bits, so huge mounds of needless work get skipped).
> 
> The fastest pure-Python solution I've found consumed about 20 CPU minutes to
> do the whole job, so is at least 3X as fast as the GMP here (which is still
> running as I type this, over an hour of CPU time and climbing).  For that, I
> wrote my own multiplication and exponentiation routines in Python, using
> digits in base 10**5000.  Computing in a form of decimal from the start
> makes "conversion to decimal" a speedy operation.
> 
> 
>>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'
> 
> 
> On the box I'm using here, the straight Python 2.3.4:
> 
> 
>>>>2**1000000
> 
> 
> consumed 80 CPU seconds (which includes decimal display), and the mxNumber
> version:
> 
> 
>>>>from mx.Number import *
>>>>Integer(2)**1000000
> 
> 
> consumed 60 CPU seconds.  I expect Python 2.3.4 is faster at this stuff than
> the version you used (in particular, recent Pythons use base 10000
> internally when converting to decimal, instead of base 10; it's still
> quadratic-time, but the constant factor was slashed).  The box is a 3.2GHz
> P4, which is probably also faster than the box you used.  It could also be
> that the version of GMP shipped with mxNumber isn't optimally compiled for
> this box, and/or getting old.
> 
> Lessons to take home <wink>:
> 
> + The speed of bigint operations can be data-dependent in implementation-
>   specific ways (Python's native pow() ran circles around GMP's for this
>   particular data).
> 
> + That changes over time (recent Pythons are much faster at some of these
>   tasks than the one you used).
> 
> + A better algorithm is always the better answer (computing in decimal
>   from the start allows pure Python to run circles around GMP computing
>   in binary then forced to do a non-trivial 24-million bit base
>   conversion).

Is it possibile to have a better algorithm for binary to base 10 
conversion, or is that limited to quadratic time? Any links to 
papers/discussions on this?

David