# RE: How to get decimal form of largest known prime?

Discussion in 'Python' started by Tim Peters, Jun 13, 2004.

1. ### Tim PetersGuest

[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

Tim Peters, Jun 13, 2004

2. ### David FraserGuest

Tim Peters wrote:
> [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

Thanks Tim

David

David Fraser, Jun 14, 2004