How to get decimal form of largest known prime?

Grégoire Dooms dooms at info.LESS.ucl.SPAM.ac.be
Sun Jun 13 09:46:10 CEST 2004


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
> 

< snip ... >

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

Could you tell us more about the computational complexity of that 
operation in base 10 compared to the same one in base 2 and 
base2->base10 conversion  ?
--
Grégoire Dooms



More information about the Python-list mailing list