How to get decimal form of largest known prime?

Tim Peters tim.one at comcast.net
Sun Jun 13 18:35:38 CEST 2004


[David Fraser]
> Is it possibile to have a better algorithm for binary to base 10
> conversion, or is that limited to quadratic time?

Sub-quadratic general base-conversion algorithms certainly exist.  Practical
implementations are complex and long-winded, and I doubt Python will ever
have one natively.

> Any links to papers/discussions on this?

There's a huge literature on asymptotic complexity of elementary arithmetic
operations on unbounded ints, and that's relevant because general base
conversion boils down to multiplication and division.  Unless your interest
is purely theoretical, I recommend searching GMP discussions.  For example,
here's a pointer into a thread from last December giving an overview of what
GMP developers were planning to try at that time:

  "mpf_get_str() is slow for big numbers?"
  http://www.swox.com/list-archives/gmp-discuss/2003-December/000901.html








More information about the Python-list mailing list