CODEWITHSUNDEEP
pythonperformancenumber-theory
Cecilia Chen
Cecilia Chen

Reputation: 45

Python exponentiation speed

Any idea how do I estimate how long this program will take? I have already ran the program for 8 hours and have no idea how much longer I will need to wait.

print (9 ** ((9 ** 9) + 9))

I know the answer is huge (I know it will spill out billion of digits). I just want to know how long it will take.

Upvotes: 0

Views: 172

Answers (2)

casevh
casevh

Reputation: 11404

As commented above, you are doing two separate calculations. The first is the exponentiation of 9**((9**9) + 9). The second is the conversion of that result to a decimal string format. The second calculations becomes slow much quicker than the first calculation.

Let's look at approximate running times for 9**((N**N)+N) on my computer.

For N=6, the exponentiation requires 0.01 seconds. The conversion to a decimal string requires 0.02 seconds.

For N=7, the exponentiation requires 0.15 seconds. The conversion to a decimal string requires 6.9 seconds.

For N=8, the exponentiation requires 16.9 seconds. The conversion to a decimal string requires 48 minutes.

For N=9, the exponentiation requires 40 minutes. The conversion to a decimal string will require a very long time - probably a couple of weeks.

Python's integer to string conversion algorithm is O(n^2) and its running time will eventually dominate. There are other libraries that can perform the calculations faster. GMPY2 will perform both calculations in less than 2 minutes. For more details, check the second answer to this question:

How can I convert an absolutely massive number to a string in a reasonable amount of time?

Upvotes: 3

DYZ
DYZ

Reputation: 57033

The time to do arithmetics (9**(N**N+N)) scales very nicely (and exponentially) with N, as you can see from the following chart. It would take my comp approximately 48 minutes to calculate the answer for N=9. However, at some point the literal representation of your number would not fit into the RAM, and that's where swapping/paging kicks in and slows the whole thing down by an unpredictable factor. enter image description here

(I understand that this does not answer your question, but I still wanted to share the chart. Feel free to flag/downvote.)

Upvotes: 3

Related Questions