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...

--
Gilmeh

The best definition of a gentleman is a man who can play the accordion --
but doesn't. -- Tom Crichton

On Sat, 21 Dec 2024 11:49:30 GMT, Gilmeh Serda wrote:

> 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

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.

On Sat, 21 Dec 2024 21:03:52 -0000 (UTC), Lawrence D'Oliveiro wrote:

> not a bug.

Who said anything about a bug?

--
Gilmeh

Barbie says, Take quaaludes in gin and go to a disco right away! But Ken
says, WOO-WOO!! No credit at "Mr. Liquor"!!

On Sun, 22 Dec 2024 at 19:17, Gilmeh Serda via Python-list
<python-list@python.org> wrote:
>
> Was just playing with numbers and stumbled on something I've never seen
> before.
....
>
> >>> 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

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

Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote or quoted:
>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!

Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
> 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.

On Sun, 22 Dec 2024 09:18:26 GMT, Gilmeh Serda wrote:

> On Sat, 21 Dec 2024 21:03:52 -0000 (UTC), Lawrence D'Oliveiro wrote:
>
>> This is a feature, not a bug.
>
> Who said anything about a bug?

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

ram@zedat.fu-berlin.de (Stefan Ram) writes:
> 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].

Paul Rubin <no.email@nospam.invalid> wrote or quoted:
>ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>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.