CODEWITHSUNDEEP
python
Ιωάννης Παπαδόπουλος
Ιωάννης Παπαδόπουλος

Reputation: 49

Why did my computer slow down and become unresponsive running this python program?

x=len(str(2**1000000000))
print(x)

I thought it was funny but my computer started to lag and it was unresponsive,what the heck happened?

Upvotes: 2

Views: 474

Answers (2)

kichik
kichik

Reputation: 34704

You're describing the classic reaction for running out of memory. Your OS starts paging out memory and writing it to hard drive (see Virtual Memory). Your computer will get especially slow if your virtual memory is paged to a spinning hard drive. Any program that tries to run after its memory has been paged out will have to read the memory back from disk which is a very slow process. But your main program that keeps eating more memory is still running, so all of your other processes are left fighting over what little memory is left. Even normal file I/O is slowed down because your storage is busy with the virtual memory. This endless paging in and out of memory is why your computer is so slow.

As others have mentioned in the comments, calculating and storing 2**1000000000 by itself doesn't require a lot of CPU or memory. It's your conversion of that integer to a string that is eating all the memory. You can verify this by running:

x = 2**1000000000

There should be no conversion to a string when you assign it to a variable this way.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476567

In Python, usually calculations in the integer world are done with arbitrary size. So it means that if you calculate 2**1000000000, it will not do this with a 32-bit integer, or a 64-bit integer, but it uses a long in Python-2.x, or an int in Python-3.x (but an int in Python-3.x) has arbitrry size.

2**1000000000 is however a huge number. It would require 1'000'000'000 bits, or 125'000'000 bytes at least. It also will calculate the power using an algorithm and has to represent the intermediate results as well.

In CPython, it requires 133 MB of memory to store the value. But that is not the end of it. Now you want to convert that to a string. The string will take approximately 301'029'995 digits. Each digits takes at least one byte. So this will take an extra 301 MB of memory, furthermore it will require a lot of work to calculate the decimal representation: each iteration, we have to perform a modulo 10 check, and furthermore we need to devide the number by 10, so it works (at least) quadratic in the number of digits of the number. Since the number of digits is huge (~300 million), it thus requires a huge amount of work.

The len(..) operation is not very expensive, but the above steps are expensive in both memory (and somwhat in CPU time, especially the conversion to a string). Memory might seem like a factor we can ignore, but in case we consume huge amounts of memory, the system can slow down, or even freeze. Usually if the system runs out of RAM memory, it will start using swap memory: it will swap out parts of RAM memory to the hard disk drive, which is very slow (compared to RAM memory).

The above sketched way to obtain the number of digits is definitely not a good one. It will for instance not work with negative numbers as well. There is a mathematical concept called logarithms, and if you take the log10 of a number, you get the number of digits minus one. There are some extra problems here:

  1. the log10 of negative numbers is not define; and
  2. nor is the log10 of zero.

But we can work around these issues. For instance by constructing the function:

from math import log10, floor

def number_of_digits(x):
    if x == 0:
        return 1
    else:
        return 1 + floor(log10(abs(x)))

This will work for all integer values. In case you want to calculate the number of digits of a power, we can even prevent calculating 2**1000000000 in the first place:

from math import log10, floor

def number_of_digits_power(x, y):
    return 1 + floor(y * log10(x))

So the number of digits is:

>>> number_of_digits_power(2, 1000000000)
301029996

This works effective in both speed and memory.

Upvotes: 4

Related Questions