Python exponentiation speed

Question

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.

The time needed is shrewed because you print it. IO to console is _s l o w_ . -you are measuring output to console - not the time needed to calc it. — Patrick Artner, Jul 07 '18 at 17:26
Time depends on your machine, meaning your CPU, your RAM, your Hard Disk (cause no, your RAM won't be large enough I think), your OS... I don't think anyone has made a benchmark for this program ;) — politinsa, Jul 07 '18 at 17:31
Order of magnitude estimation is okay, are we talking hours, days or months? The machine is Windows10, i7, with 1TB of RAM and SSD — Cecilia Chen, Jul 07 '18 at 17:39
Well this should be less than 10**10 digits. Python needs about 0.45 bytes per digit. That means the final number is about 5 GB in ram. Expect approx. 2 temp variables need for calculation of the same size. So about 15 GB. So just start the calculation and monitor your RAM usage. Then extrapolate how long it will take to reach that number. That should give you an order of magnitude estimate... — C. Yduqoli, Jul 07 '18 at 17:40
The RAM usage is weird, it looks like the program just stuck with using only 300MB of ram. I expect it to be much larger but it isn't the case (and it is unable to use more than 1 core) — Cecilia Chen, Jul 07 '18 at 17:42
You can answer this question in terms of Big-O, but it's not possible to answer it precisely because we don't know what hardware you are running and a bunch of other details that make it a pointless question to ask if you want a precise answer. Go look up Big-O notation. — reka18, Jul 07 '18 at 18:01
`a = (9 ** ((9 ** 9) + 9))` took 3974.617 seconds on my computer. So the string conversation really must be the problem as others pointed out. Peak memory usage was 770 MB, so I was a little bit off with my prediction... — C. Yduqoli, Jul 08 '18 at 04:01

score 3 · Answer 1 · edited Jun 20 '20 at 09:12

3

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.

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

edited Jun 20 '20 at 09:12

Community

1
1

answered Jul 07 '18 at 17:42

DYZ

55,249
10
64
93

1

What is your y-axis scale? – Cecilia Chen Jul 07 '18 at 17:46
Time in seconds, as measured by `%timeit`. – DYZ Jul 07 '18 at 17:47
If I read correctly, you were able to compute 9 ** (8 ** 8 + 8) is less than a second? I don't believe it. – Cecilia Chen Jul 07 '18 at 17:57
So this is running in O(n^2) time or worse if you are using Big-O notation to describe it's running time. – reka18 Jul 07 '18 at 18:03
@CeciliaChen No, in 29 seconds - but, again, as measured by `%timeit`. The real running time was much longer. – DYZ Jul 07 '18 at 19:01
@data83 Close to O(exp(N)). – DYZ Jul 07 '18 at 19:02
@DyZ yeah, worse than n^2 – reka18 Jul 08 '18 at 03:09

score 3 · Accepted Answer · answered Jul 08 '18 at 01:51

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?

Python exponentiation speed

2 Answers2