Velocity Reviews > RE: How to get decimal form of largest known prime?

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

Tim Peters
Guest
Posts: n/a

 06-13-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/gm...er/000901.html

David Fraser
Guest
Posts: n/a

 06-14-2004
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/gm...er/000901.html

Thanks Tim

David