Maximum Recursions on Windows but not Linux on Python 3.12.10, 3.13.12

[purplearmadillo77]

Bug report

Bug description:

Running the following simplified exponentiation code from https://github.com/ethereum/py_ecc produces maximum recursion errors on Windows but not Linux, and does not seem to be helped by increasing the recursion limit. Note the (maybe too generous) recursion limit of 1 million.

class FQ:
    n: int
    field_modulus = 21888242871839275222246405745257275088696311157297823662689037894645226208583

    def __init__(self , val) -> None:
        if isinstance(val, FQ):
            self.n = val.n
        elif isinstance(val, int):
            self.n = val % self.field_modulus
        else:
            raise TypeError(f"Expected an int or FQ object, but got object of type {type(val)}")

    def __mul__(self, other):
        if not isinstance(other, FQ):
            raise TypeError(f"Expected FQ object, but got object of type {type(other)}")
        return FQ((self.n * other.n) % self.field_modulus)
    
    def __pow__(self, other: int):
        if other == 0:
            return FQ(1)
        elif other == 1:
            return FQ(self.n)
        elif other % 2 == 0:
            return (self * self) ** (other // 2)
        else:
            return ((self * self) ** (other // 2)) * self

import sys
sys.setrecursionlimit(1000000)

bigexponent = 5524842336132240963126171267831731470973821037629576541888827343141969108399075412139745027615406298170096085486546803436277011538294467478109073732568415510062016396777261399460291999684125988048823917022730190836532720475663165843655597764930274954582383739028759376599435048732205541615505259263023033317474635156447118766531771295783031910959009091916248178265666882418044080818927857259679317140977167095260922612780719525601711114440720492291235650574837501614600243533462841672824527562176623355288135191398082911705390721253812308157290715448616027509369648293136081373254263837351221752295411553763464360939302874020895174269731789175697133847480818272554725769374714961957527271882614356332712387101317360962997981688529255405493423307752798770067843548014222497225737835616851796188164800376950055154261623624310722456383247444
x = FQ(3)
y = x ** bigexponent
print(y)

When running it on 64-bit Windows 10, one runs into:

(lots of printouts)
    return FQ((self.n * other.n) % self.field_modulus)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded

However, this runs fine on Ubuntu Linux.

For comparison, here's a non-class, but still highly recursive version that runs fine on both operating systems and reports the right answer, even with a much more reasonable recursion limit of 10,000.

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
bigexponent = 5524842336132240963126171267831731470973821037629576541888827343141969108399075412139745027615406298170096085486546803436277011538294467478109073732568415510062016396777261399460291999684125988048823917022730190836532720475663165843655597764930274954582383739028759376599435048732205541615505259263023033317474635156447118766531771295783031910959009091916248178265666882418044080818927857259679317140977167095260922612780719525601711114440720492291235650574837501614600243533462841672824527562176623355288135191398082911705390721253812308157290715448616027509369648293136081373254263837351221752295411553763464360939302874020895174269731789175697133847480818272554725769374714961957527271882614356332712387101317360962997981688529255405493423307752798770067843548014222497225737835616851796188164800376950055154261623624310722456383247444

def sillymul(x, y):
    return (x * y) % p

def sillypow(x, other):
    if other == 0:
        return 1
    elif other == 1:
        return x
    elif other % 2 == 0:
        return sillypow(sillymul(x, x), (other // 2)) % p
    else:
        return sillymul(sillypow(sillymul(x, x), (other // 2)), x)

import sys
sys.setrecursionlimit(10000)

x = 3
y = sillypow(x, bigexponent)
print(y)
print(pow(3, bigexponent, p))

Some more context might be found at ethereum/py_ecc#134 and ethereum/py_ecc#133

CPython versions tested on:

3.12, 3.13

Operating systems tested on:

Linux, Windows

[aisk]

sys.setrecursionlimit only sets the maximum stack depth in the Python interpreter, but the OS also has a stack limit. On Windows, its default is 1 MB according to https://learn.microsoft.com/en-us/windows/win32/procthread/thread-stack-size, which is much smaller than in a typical Linux environment, so on Linux it may not trigger a RecursionError.

Based on this, I think this is not a bug in Python, but rather a limitation of the underlying OS, so I'll tag this issue as pending. If you have more advice or information, please let me know and we can change it.

[aisk]

I haven't tried this because I don't currently have access to a Windows machine, but you can try using threading.stack_size to increase the stack size for a newly created thread and run your code in that thread.

[zooba]

@aisk is correct, the default stack size on Windows is lower than on Linux, and so the default recursion limit is lower to match, since it has to trigger before the native stack is exhausted or your program will simply terminate.

Newer versions of Python already use a different calculation method, so it should be possible to set the maximum higher without crashing. I don't think we're likely to change anything in the older versions at this stage.