classification
Title: print() performance problem with very large numbers
Type: Stage: resolved
Components: Interpreter Core Versions: Python 3.6
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: U.W., mark.dickinson, serhiy.storchaka
Priority: normal Keywords:

Created on 2020-05-27 12:03 by U.W., last changed 2020-06-02 13:42 by U.W.. This issue is now closed.

Messages (6)
msg370066 - (view) Author: (U.W.) Date: 2020-05-27 12:03
Printing very large numbers takes forever.

Example:
print((2**24)**(3840*2160))

That number has about 60 Million digits and my machine is busy now for more than an hour and still not finished.

The calculation of the number is no problem, btw. and finishes in under a second.
msg370069 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2020-05-27 12:24
It is not a print() problem, it is a problem with converting an integer to decimal string representation. AFAIK it has quadratic complexity from the size of the integer.
msg370070 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-27 12:31
Right; the naive algorithm for converting the internal binary representation to the decimal representation is quadratic time. In *theory* we could implement a subquadratic time algorithm, but the complexity of such an implementation outweighs the benefits. Python really isn't targeted at super-fast million-digit arithmetic; that's more the domain of libraries like GMP.

Closing as "won't fix". I'd recommend using gmpy2[1] instead. Alternatively, you may be able to make the `Decimal` type work with a suitably huge precision.

Related: #26256.

[1] gmpy2: https://gmpy2.readthedocs.io/en/latest/intro.html
msg370279 - (view) Author: (U.W.) Date: 2020-05-29 07:04
That's ok for me. It *is* a rare edge case.

FYI, printing this 60 Million digit number took about 12 hours on my i7.
msg370294 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-29 10:38
> FYI, printing this 60 Million digit number took about 12 hours on my i7.

That sounds about right: on my machine, it takes around 10 seconds to convert a 1 million-digit number to a string. Multiplying by 60**2 gives 10 hours.

I do have to wonder what you're doing with all those digits now that you have them, though ...
msg370609 - (view) Author: (U.W.) Date: 2020-06-02 13:42
Well, the number in itself is not so useful, but...

- I encountered a performance problem in Python where I did not expect one
- Other people will encounter that, too, and now they easily find the reason behind it (I would not have opened this bug if I had found an explanation)
- Hopefully someone is bored enough to fix it and that will make Python an even better tool than it is already. This number can then be used as an example to recretew the problem and verify the solution.

- Hopefully no bad guy exploits this weakness by sending large numbers like this one to servers just to see if it triggers a denial of service...
History
Date User Action Args
2020-06-02 13:42:37U.W.setmessages: + msg370609
2020-05-29 10:38:02mark.dickinsonsetmessages: + msg370294
2020-05-29 07:04:52U.W.setmessages: + msg370279
2020-05-27 12:31:43mark.dickinsonsetstatus: open -> closed
resolution: wont fix
messages: + msg370070

stage: resolved
2020-05-27 12:24:27serhiy.storchakasetnosy: + mark.dickinson, serhiy.storchaka
messages: + msg370069
2020-05-27 12:03:59U.W.create