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