Can anyone TL;DR why? Why wouldn't it just return that long integer of all 1s?
The CVE hasn't been published, but for example there's an explanation at
Technically speaking, yes, there should be some limit if you are accepting an untrusted input. But there is a good argument for making this limit built-in for integers but not lists: integers are expected to be atomic while lists are wildly understood as aggregates, therefore large integers can more easily propagate throughout unsuspecting code base than large lists.
(Or, if you are just saying that once you have sub-quadratic algorithms you don't need language-imposed limits anymore, maybe you are right.)
Even a naive divide and conquer decimal to binary algorithm is only logarithmically slower than multiplication.
https://github.com/python/cpython/issues/95778
https://github.com/python/cpython/issues/90716
Is there something bad going on with Python's internal representation of big integers, too? I thought I might have understood Tim Peters to be saying that in the latter thread.
It does look like gmpy2.mpz() is like 100 times faster than int() or something. Is this just because it's doing it all in assembly rather than in Python bytecodes, or are the Python data structures here also not so hot?
It's not the data structures. The data structures are really more or less the same: you have some array of words, with a length and a sign. The only real differences are in the particular length of word that you choose, which is not a very interesting difference.
Assembly language optimizations do tend to matter here, because you're working with the carry bit for lots of these operations, and each architecture also has some different way of multiplying numbers. Multiplying numbers is "funny" because it produces two words of output for one word of input.
There are also sometimes some different algorithms in use, and GMP uses some different algorithms depending on the size. Here's a page describing the algorithms used by GMP:
https://gmplib.org/manual/Multiplication-Algorithms
Here's a description of how carries are propagated:
https://gmplib.org/manual/Assembly-Carry-Propagation
IMO, I wouldn't expect my language's built-in bigint type to use the best, most cutting-edge algorithms and lots of hand-tuned assembly. GMP is a specialized library for doing special things.
‘1234’ => 1x1000 + 2x100 + 3x10 + 4x1
Is faster and has room to improve
There are d additions, so the addition is linear time.
Each multiplication is potentially quadratic, but it seems optimizable since it’s never multiplication of two large numbers—always one large and one small number.
Another issue you have not accounted for is how you convert to base two. If you want the final product to be in base two, your additions have to be in base two, so the result of your multiplications have to be in base two, which means you will have to convert 1000, 100, 10, 1 into base two as well. Again this takes \Theta(n^2) time if you cache results (1000_2 = 100_2 *_2 10_2): you're doing n operations, and the cost of each operation is 1, 2, 3, 4, ..., n (times some constant. 10^(n-1) * 10 all in base two takes \Theta(n) time).
But it's not actually worse than O(n^2), my mistake.
In a power-of-2 base, the result of the multiplication is a constant number of digits (because the multiplication is just a shift of a single digit), so the additions could each be constant time in that case.