This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author mark.dickinson
Date 2007-07-03.14:22:31
SpamBayes Score
Marked as misclassified
I'd call this a feature request rather than a bug.

If I understand correctly, an O(n^(1+epsilon)) printing algorithm would rely on having an FFT-based fast multiplication algorithm, together with some form of divide-and-conquer division---is this right?  These algorithms are nontrivial to implement efficiently, and even then the crossover point (where the FFT-based method becomes faster than the quadratic method) is likely to be in the thousands of digits.  So I can't imagine there's much demand for this---even a 4096-bit RSA key is only 1233 (or 1234) digits long.  If you just want subquadratic printing (O(n^1.585) or so) then you'd still need a subquadratic division (Python already has Karatsuba multiplication for large integers); here I guess the crossover would be smaller.  A subquadratic division for Python might well be of interest to the developers, if someone could be persuaded to write and test one, and demonstrate a significant positive impact on performance.

What's your use-case for printing huge integers fast?  It doesn't seem like a very common need.

Regarding GMP, I believe there are licensing issues:  it's not legal to include GMP in core Python and release Python under its current non-GPL license, or something like that---I don't know anything about the details.  But have you encountered Martelli's gmpy?

Date User Action Args
2007-08-23 14:58:15adminlinkissue1746088 messages
2007-08-23 14:58:15admincreate