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.

Title: pow() of huge input does not complete
Type: resource usage Stage: resolved
Components: Interpreter Core Versions: Python 3.8
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: minipython, serhiy.storchaka, steven.daprano
Priority: normal Keywords:

Created on 2020-12-29 09:49 by minipython, last changed 2022-04-11 14:59 by admin. This issue is now closed.

File name Uploaded Description Edit minipython, 2020-12-29 09:49
Messages (8)
msg383969 - (view) Author: (minipython) Date: 2020-12-29 09:49
The code can only computed based on python 3.7.Python 3.9 and python 3.6 cannot compute the code.It is very strange problem.
msg383980 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2020-12-29 11:43
What error are you getting?

Can you demonstrate the error without gmpy2, as that is a third-party library and nothing to do with us.
msg383982 - (view) Author: (minipython) Date: 2020-12-29 11:49
The issue is that if i use function pow(c,e),it can be computed in python37 in 3 minutes.But it cannot be computed in python36 or python39.Without gmpy2 library,i find the bug.
msg383987 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2020-12-29 12:21
I cannot replicate that. On my computer, I can compute pow(c, e) in approximately two minutes using Python 3.9:

>>> from time import time
>>> t = time(); a = pow(c, e); time()-t
>>> math.log10(a)

Can you give more information please?

- exact version number used
- OS
- how much memory?
- if you leave pow(c, e) running for 10 minutes, does it complete?
- can you compute pow(c, 10000)? how long does that take?
- how about pow(c, 1000)?
msg383997 - (view) Author: (minipython) Date: 2020-12-29 13:07
Here are my information.
1.python 3.8.6 10(build 19042 20h2)
3. 16Gb memory
4. It doesn't complete.It takes about 30 minutes but it gives no output.
5. It takes 6.346898794174194s
6. It takes 0.3690004348754883s.
msg384005 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2020-12-29 14:05
Are you sure that this is a time of calculating pow() and not the time of calculating decimal representation of the result?

On my computer:

>>> t = time(); a = pow(c, 2**14+1); time()-t
>>> t = time(); a = pow(c, 2**15+1); time()-t
>>> t = time(); a = pow(c, 2**16+1); time()-t

The computational complexity is O((log(c)*e)**1.5). And it needs not so much memory: around 20 MB for final result, and few times more for intermediate results, so this is not matter of swapping.
msg384008 - (view) Author: (minipython) Date: 2020-12-29 14:30
ohhhhhhhhhhhhh.You are right.If i directly compute the huge result without printing,it only takes 115s.Thank you very much.I'm sorry to forget noting the print function.
msg384009 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2020-12-29 14:41
The computational complexity of algorithm used to convert integer to decimals is proportional to the cube of the size of the number. It is known issue. There are better algorithms (perhaps gmpy2 uses them), but they benefit only extremely large numbers, for which exact decimal form is not very useful.
Date User Action Args
2022-04-11 14:59:39adminsetgithub: 86945
2020-12-29 14:41:38serhiy.storchakasetstatus: open -> closed
resolution: not a bug
messages: + msg384009

stage: resolved
2020-12-29 14:30:30minipythonsetmessages: + msg384008
2020-12-29 14:05:51serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg384005
2020-12-29 13:07:15minipythonsetmessages: + msg383997
versions: + Python 3.8, - Python 3.6, Python 3.9
2020-12-29 12:22:45steven.dapranosettitle: Pow compute can only available in python3.7 -> pow() of huge input does not complete
components: + Interpreter Core, - C API
versions: + Python 3.6, Python 3.9, - Python 3.7
2020-12-29 12:21:01steven.dapranosetmessages: + msg383987
2020-12-29 11:49:37minipythonsetmessages: + msg383982
2020-12-29 11:43:26steven.dapranosetnosy: + steven.daprano
messages: + msg383980
2020-12-29 09:49:50minipythoncreate