Lengthy numbers

[Gilmeh Serda]

Was just playing with numbers and stumbled on something I've never seen
before.

9**9**2

196627050475552913618075908526912116283103450944214766927315415537966391196809

9**9**3

439328503696464329829774782657072712058010308177126710621676697750466344744764
029773301412612482563729435064854354299095570379503452515853238520182740967398
746503532324400000659505126023955913142968176998364877699089666171297275956245
407453033190168644894850576346492691458695174281789557994923607783461486426448
617667076393901104477324982631297641034277093818692823488603426279473674368943
609268871793467206677285688478458498235002859256706389043030847945506577080623
430066283504397583789044245429585982964571774605868466160379567432725704121260
940939343217905975847365096315872153240969882363435363449775254393010368267343
970426230801390250903399147001650831878665172798468587509747439118815689

9**9**4

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string conversion;
use sys.set_int_max_str_digits() to increase the limit

Explanation:
https://discuss.python.org/t/int-str-conversions-broken-in-latest-python-bugfix-releases/18889


Though, it would have been funnier had it been 4400...

[Lawrence D'Oliveiro]

Post by Gilmeh Serda
File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string
conversion;
use sys.set_int_max_str_digits() to increase the limit
https://discuss.python.org/t/int-str-conversions-broken-in-latest-python-bugfix-releases/18889

This is a feature, not a bug. It’s to guard against an attacker
exhausting system resources (CPU) by forcing the execution of an O(N²)
operation with large N.

[Gilmeh Serda]

Post by Lawrence D'Oliveiro
not a bug.

Who said anything about a bug?

[Lawrence D'Oliveiro]

Post by Gilmeh Serda

Post by Lawrence D'Oliveiro
This is a feature, not a bug.

Who said anything about a bug?

Not sure what this is relevant to, but ... you tell me.

[Oscar Benjamin]

On Sun, 22 Dec 2024 at 19:17, Gilmeh Serda via Python-list

Post by Gilmeh Serda
Was just playing with numbers and stumbled on something I've never seen
before.

...

Post by Gilmeh Serda

9**9**4

File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string conversion;
use sys.set_int_max_str_digits() to increase the limit
https://discuss.python.org/t/int-str-conversions-broken-in-latest-python-bugfix-releases/18889

I think that the original security concern was mainly motivated by the
string to int direction i.e. calling int(s) for a possibly large
string s (possibly from an untrusted source) might be slow with
CPython. To solve that problem conversions from string->int and
int->string were disallowed. Now that more time has passed it becomes
clearer that disabling int->string conversion is more likely to be the
thing that people bump into as a result of this limitation (as you
just did). I find it harder to see what the security problem is in
that direction but I don't think this will be changed.

CPython has an implementation of arbitrarily large integers but an
important part of it is hobbled. If you do want to work with such
large integers then I recommend using either gmpy2's gmpy2.mpz type or
python-flint's flint.fmpz type.

At the same time it is not hard to run into slowness with integers
e.g. 10**10**10 but that won't come up in string parsing if not using
eval. Not a likely security issue but I am suddenly reminded of this
dangerous snippet:

x = [0]; x.extend(iter(x))

If you want to test it then make sure to save your work etc and be
prepared to hard reset the computer. On this machine Ctrl-C doesn't
work for this but Ctrl-\ does if you do it quick enough.

--
Oscar

[Stefan Ram]

Post by Oscar Benjamin
x = [0]; x.extend(iter(x))

Yo, that's a gnarly piece of Python code!

This code whips up an infinite list, but in a pretty slick way.

Here's the lowdown:

- First off, we're cooking up a list x with just one ingredient: 0

- Then we're using extend() to pile more stuff onto x

- The mind-bender is what we're extending with: iter(x)

iter(x) spins up an iterator from the list x. When we extend x
with this iterator, it starts tossing the elements of x back into
itself. But here's the kicker: as x grows, the iterator keeps
chugging along, creating an endless loop.

So in theory, this would crank out an infinite list that looks like
[0, 0, 0, 0, ...]. In the real world, though, if you try to print or
use this list, your program will probably freeze up faster than the
405 at rush hour.

It's a pretty clever (and kind of diabolical) way to create an
infinite data structure. Just watch out using something like
this in actual code - it could cause some serious brain freeze!

[Paul Rubin]

Post by Stefan Ram
So in theory, this would crank out an infinite list that looks like
[0, 0, 0, 0, ...]. In the real world, though, if you try to print or
use this list, your program will probably freeze up faster than the
405 at rush hour.

The freeze-up happens as soon as you create the list. Unfortunately
iterators don't have anything like .extend so I don't see a way to
create recursive ones like that, short of writing more verbose code
using yield. In Haskell it is straightforward:

fibonacci = 0 : 1 : zipWith (+) (tail fibonacci)

main = print (take 10 fibonacci)

should print [0,1,1,2,3,5,8,13,21,34].

[Stefan Ram]

Post by Paul Rubin

Post by Stefan Ram
So in theory, this would crank out an infinite list that looks like
[0, 0, 0, 0, ...]. In the real world, though, if you try to print or
use this list, your program will probably freeze up faster than the
405 at rush hour.

The freeze-up happens as soon as you create the list.

I'm stoked you caught that! You hit the nail on the head -
that resource-hogging calculation goes down when the expression's
evaluated. No need to "print or use this list" to see it happen.

[Paul Rubin]

Post by Oscar Benjamin
To solve that problem conversions from string->int and
int->string were disallowed.

The obvious conversion algorithms use quadratic time but it seems to me
that O(n log n) is doable with some careful programming. For example,
people have computed pi to billions or trillions of decimal places.

I believe GMP uses the Toom-Cook algorithm for multiplication once the
numbers are big enough. I don't know whether that is also used for
decimal conversions.

Page 14 of http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf discusses
base conversion. That link is from a stackexchange thread that I found
with web search.