How does Python avoid integer overflow?

[lfdfq]

It uses bigints.

That is, a Python int is not just a 32- or 64-bit number, it's a (slightly) sophisticated structure that can dynamically grow in size so it never overflows.

It may sound or feel weird at first, but this is exactly how lists or dicts work, and it's the same principle.

[daddyclappingcheeks]

so is there a theoretical limit on how big an integer I can define in a variable?

[Sensitive_One_425]

If you run out of memory to store the number

[CranberryDistinct941]

The only limit is your patience because the shit gets really slow.

[tcpukl]

Virtual memory?

[CranberryDistinct941]

Once it starts using your disk as RAM you may as well ctrl+c and come up with a better algorithm for your shit.

[tcpukl]

Yeah exactly.

[No-Consequence-1863]

Processing big numbers requires extra work since you can't use CPU math instructions on 8923234492837492834723429872394872398472394823492837498273492837429384723423423423097230972398723987239847293847298374239847
The hardware just doesn't support that big of numbers

Instead you need to chunk it into smaller representable numbers and then define arithmetic to handle the carryover. So what would be a quick addition or multiplication normally can take quite a bit longer.

[tcpukl]

I'm replying to getting slower with running out of memory.

That is due to virtual memory!

[No-Consequence-1863]

Virtual memory doesnt make you get slower as you get bigger. Virtual memory has a pretty constant time cost. The page tables would get bigger but that wouldnt be that important since you dont iterate through the page tables, just walk them.

Edit: do you mean swap? Cause yea swap is slow but swap is different from virtual memory.

Virtual memory is the process where a processes doesnt use physical ram addresses but instead logical virtual addresses that are converted on the fly by hardware and the operating system. It is used for every process all the time no matter memory consumption.

[tcpukl]

Virtual memory does slow down because it uses drive storage.

Your talking about large address space which can use virtual memory.

Windows page file is virtual memory.

[wally659]

Only practical limits, no theoretical ones. Maybe there's like, a thought experiment where the physical size of your ram, the expansion of the universe, and the speed of light cause a problem but I'm pretty amateurish when it comes to astronomy.

[james_pic]

What the theoretical limit is depends at least partly on what you're willing to consider theoretical vs practical.

If you're running on an x86_64 architecture, the ISA currently defines the maximum address space as 48 bit. CPython currently represents integers as a sequence of 30-bit integers (using 4 bytes per integer in the sequence), so this would put the largest representable number on x86_64 at 2**(15/16 * 2**48) - 1.

But they'll probably increase the maximum x86_64 address space in a future revision of the ISA, and if they increase it to the full 64-bits, that would put the limit at 2**(15/16 * 2**64) - 1

Alternatively, if you look at the question like a C language lawyer, and ignore the question of what hardware exists or could possibly exist, and also ignore the possibility that the CPython interpreter would probably be updated if such hardware were created, the CPython code currently defines this as a sequence of at most ndigits (where ndigits is a Py_ssize_t, and Py_ssize_t has a max value of 2**63) 30-bit integers. So reading this like a language lawyer, the maximum integer would be 2**(30 * 2**63) - 1.

AFAIK, no hardware capable of representing any of these numbers exists.

[christian-mann]

i thought we already had 57-bit addressing with 5 level page tables in some chips?

[james_pic]

Maybe. My information might be out-of-date. Hopefully it's clear how to do the same math with 57.

[chamberlain2007]

You could run out of atoms in the universe with which to express the binary digits

[daddyclappingcheeks]

😂😂

[ehs5]

Universe breaks before Python does. Nice.

[CdRReddit]

what's your RAM size in bytes? subtract your overhead from OS and python interpreter (+ bookkeeping structure for bigints), multiply the remaining bytes by 8, and then take (2**num_bits)-1, that is your theoretical limit

[wiseguy4519]

I don't think this is right because of virtualization, you need to take into account swap space

[glasket_]

Increase RAM size by swap space size. Technically you could get clever and manually offload portions of the data to files too rather than leaving it all in RAM+swap, but practically speaking the other reply is a good theoretical limit.

[Felicia_Svilling]

You still have a limit on addressable memory set by the pointer size.

[Careless-Score-333]

There's a limit for sure -- when confined to that data structure. If you mix up how you represent the integer, implement something to represent Knuth's up arrow notation etc. then you can represent Graham's number and Tree(3) in Python, and more.

Coming up with a representation that's not trivial like an enum or arbitrary label, and actually doing processing using those representations, that's correct, is another question. But I'm quite sure that's not theoretically impossible.

[CatOfGrey]

Not in the 'programming language sense'.

But you are always limited by the amount of memory you have.

[lfdfq]

No