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

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

  1. Tim Peters

    Tim Peters Guest

    [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
    #1
    1. Advertising

  2. Tim Peters

    David Fraser Guest

    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
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Daniel Yoo
    Replies:
    11
    Views:
    733
    =?ISO-8859-1?Q?Gr=E9goire_Dooms?=
    Jun 12, 2004
  2. Tim Peters
    Replies:
    12
    Views:
    842
    Tim Peters
    Jun 17, 2004
  3. Tim Peters
    Replies:
    1
    Views:
    399
    Claudio Grondi
    Jun 16, 2004
  4. Davy
    Replies:
    7
    Views:
    219
    DouhetSukd
    Nov 13, 2007
  5. Jeremy Fischer
    Replies:
    0
    Views:
    177
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page