sys.maxsize is the maximal number of digits a _long_ in python may have.
the `10*sys.maxsize` was just an example to show that, even in Python, long objects have a limit (although very big : 10*9223372036854775807 on 64 bits).
I honestly didn't wait to see if the interpreter will effectively complain about its size (it takes why too much time).
EDIT : According to gvx's comment those limits are not correct (sys.maxsize is not technicaly the max of digits possible, due to a bad interpretation of what Py_Size means on my side)
One important detail: "digit" when talking about sdigit & ob_digit are not base-10 digits, but base 10000 for 32-bit CPython and base 1000000000 for 64-bit CPython!
That means PY_SIZE(-15) is -1, not -2! And the maximum representable integer in Python should be closer to 10000 * (sys.maxsize / 2) for 32-bit and 1000000000 * (sys.maxsize / 4) for 64-bit.
I need to correct myself: on my 64 bit system, given M = ((1 << (30 * N)) - 1, M is the largest integer such that sys.getsizeof(M) = 24 + 4 * N.
Assuming I made no further mistakes, sys.getsizeof(I) <= sys.maxsize for any I, which implies that the largest representable integer in Python is (1 << (30 * Nmax)) - 1, where Nmax = (sys.maxsize - 24) // 4 = 2305843009213693945, so the actual maximum integer is (1 << 69175290276410818350) - 1 which is approximately 10 ** 2.082383733196259e+19 (for comparison, 10 ** sys.maxsize is approximately 10 ** 9.223372036854776e+18)
Do they really store bignums as base-(10^x) chunks instead of base-(2^x) chunks? That wastes quite a lot of memory, but for what reason? It makes printing it out slightly easier?
Python 2 had distinct `int` and `long` types, but Python 3 merged them together into just `int`.
I wasn't sure if the internal C implementation code still used `long`/`Long` for naming, but this blog post and official source code shows that the naming still exists.
One of my favourite things about Python is that its integers are true integers: they do not overflow or wrap. In my opinion, this is the correct default for most programming languages (in fact, I would have gone a step further and made integer division return fractions rather than floats by default, as well). It removes so many problems (especially for beginners) since it is the way that integers work in the real world: for example x + 1 > x always, with no exceptions.
Of course for efficiency concerns, programmers should have access to fixed-width integers as well, but I think that true integers should be the default. It was also contemplated for Go [1], and was pointed out that true integers benefit from being a core language feature, since the compiler can perform a lot of SMI (SMall Integer) optimisations, which essentially use machine integers for small enough integers, before switching to a more complicated implementation. They also recognise that the biggest benefit to a bigint type is making it the default integer type.
> in fact, I would have gone a step further and made integer division return fractions rather than floats by default, as well
This was decided against in Python:
> ABC had two types of numbers at run time; exact numbers which were represented as arbitrary precision rational numbers and approximate numbers which were represented as binary floating point with extended exponent range. The rational numbers didn’t pan out in my view. (Anecdote: I tried to compute my taxes once using ABC. The program, which seemed fairly straightforward, was taking way too long to compute a few simple numbers. Upon investigation it turned out that it was doing arithmetic on numers with thousands of digits of precision, which were to be rounded to guilders and cents for printing.)
BTW, the use of a size 1 array in the struct is a common 'hack', which has some form of dynamic arrays in structs. When the object is allocated through malloc, the size of the struct is actually smaller than the size you want for the array, so you allocate the size you want for the struct and add it to the size you want for the array. You can then access this memory after the structure, since it's technically allocated a part of it. As to why it is size 1, and not size 0, some compilers don't accept a size 0 array, so it's probably size 1 to ensure compatibility with those compilers. This is commonly referred to as the 'C Struct Hack'.
This reminds me of my favourite gotcha in python - that parsing integers is O(n^2).
This is because (conceptually at least - there might be some optimizations that change the details slightly) an integer is parsed by parsing each digit in a loop, and keeping a running total `value = 10 * value + digit`. This seems O(n), until you realise that the "10 * value + digit" operation takes O(log(value)) because of the internal digit-based representation. log(value) is proportional to the number of parsed digits so far, so we can say that the `value = 10 * value + digit` step is O(n), making the whole loop O(n^2).
Some basic timing tests bear this out - on my machine, a 1000-digit number takes ~10us to parse but a 1000000-digit number (which is a 1MB payload - within the possibility of maliciously provided input) takes 5sec (that is, 5000000x longer for a 1000x longer input).
As a fun aside, I was able to write a replacement int() function optimised for numbers this large that is O(n log n). It does this by splitting the input string in two, parsing both sides recursively (switching to native int() below a size threshold) then joining them together with `left * 10*len(right_str) + right`.
Though given that we're parsing base10 digits and the internal representation uses a power of 10 as digits (which I only learned today - I'd assumed the internal digits would be powers of 2), it would be possible to special-case parsing of base10 integers so that it's O(n), by just grouping digits directly into internal digits instead of doing true multiply operations. Given base10 parsing is by far the most common case, that's an optimization that may be worth doing.
14 comments
[ 3.0 ms ] story [ 47.6 ms ] threadsys.maxsize is the maximal number of digits a _long_ in python may have.
the `10*sys.maxsize` was just an example to show that, even in Python, long objects have a limit (although very big : 10*9223372036854775807 on 64 bits).
I honestly didn't wait to see if the interpreter will effectively complain about its size (it takes why too much time).
EDIT : According to gvx's comment those limits are not correct (sys.maxsize is not technicaly the max of digits possible, due to a bad interpretation of what Py_Size means on my side)
That means PY_SIZE(-15) is -1, not -2! And the maximum representable integer in Python should be closer to 10000 * (sys.maxsize / 2) for 32-bit and 1000000000 * (sys.maxsize / 4) for 64-bit.
Assuming I made no further mistakes, sys.getsizeof(I) <= sys.maxsize for any I, which implies that the largest representable integer in Python is (1 << (30 * Nmax)) - 1, where Nmax = (sys.maxsize - 24) // 4 = 2305843009213693945, so the actual maximum integer is (1 << 69175290276410818350) - 1 which is approximately 10 ** 2.082383733196259e+19 (for comparison, 10 ** sys.maxsize is approximately 10 ** 9.223372036854776e+18)
I'll update the article.
Python 2 had distinct `int` and `long` types, but Python 3 merged them together into just `int`.
I wasn't sure if the internal C implementation code still used `long`/`Long` for naming, but this blog post and official source code shows that the naming still exists.
Of course for efficiency concerns, programmers should have access to fixed-width integers as well, but I think that true integers should be the default. It was also contemplated for Go [1], and was pointed out that true integers benefit from being a core language feature, since the compiler can perform a lot of SMI (SMall Integer) optimisations, which essentially use machine integers for small enough integers, before switching to a more complicated implementation. They also recognise that the biggest benefit to a bigint type is making it the default integer type.
[1]: https://github.com/golang/go/issues/19623
This was decided against in Python:
> ABC had two types of numbers at run time; exact numbers which were represented as arbitrary precision rational numbers and approximate numbers which were represented as binary floating point with extended exponent range. The rational numbers didn’t pan out in my view. (Anecdote: I tried to compute my taxes once using ABC. The program, which seemed fairly straightforward, was taking way too long to compute a few simple numbers. Upon investigation it turned out that it was doing arithmetic on numers with thousands of digits of precision, which were to be rounded to guilders and cents for printing.)
https://python-history.blogspot.com/2009/02/early-language-d...
This is because (conceptually at least - there might be some optimizations that change the details slightly) an integer is parsed by parsing each digit in a loop, and keeping a running total `value = 10 * value + digit`. This seems O(n), until you realise that the "10 * value + digit" operation takes O(log(value)) because of the internal digit-based representation. log(value) is proportional to the number of parsed digits so far, so we can say that the `value = 10 * value + digit` step is O(n), making the whole loop O(n^2).
Some basic timing tests bear this out - on my machine, a 1000-digit number takes ~10us to parse but a 1000000-digit number (which is a 1MB payload - within the possibility of maliciously provided input) takes 5sec (that is, 5000000x longer for a 1000x longer input).
As a fun aside, I was able to write a replacement int() function optimised for numbers this large that is O(n log n). It does this by splitting the input string in two, parsing both sides recursively (switching to native int() below a size threshold) then joining them together with `left * 10*len(right_str) + right`.
Though given that we're parsing base10 digits and the internal representation uses a power of 10 as digits (which I only learned today - I'd assumed the internal digits would be powers of 2), it would be possible to special-case parsing of base10 integers so that it's O(n), by just grouping digits directly into internal digits instead of doing true multiply operations. Given base10 parsing is by far the most common case, that's an optimization that may be worth doing.