Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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





 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Worlds Largest Photo and Worlds Largest Camera... Somebody Digital Photography 1 08-16-2007 02:51 AM
RE: How to get decimal form of largest known prime? Tim Peters Python 12 06-17-2004 03:11 AM
RE: How to get decimal form of largest known prime? Tim Peters Python 1 06-16-2004 12:16 AM
How to get decimal form of largest known prime? Daniel Yoo Python 11 06-12-2004 11:59 AM



Advertisments