Quiero calcular la secuencia de Collatz para un número muy grande, pero supongo que Python está fallando en manejar estos grandes números y no sé cómo hacerlo manejarlo.

Aquí está mi programa:

def collatz(n):
    if (n == -1 or n == 1 or n == -17 or n == -17 -2**4096):
        print('break found',n)
        return
    if str(n)[-1] in ['1','3','5','7','9']:
        #print(n)
        return collatz(3*n + 1)
    else:
        return collatz(n//2)

Quiero usar los números a rango n = 2**4096. Me incrementé la función de límite de recursión por sys.setrecursionlimit. Pero ahora estoy enfrentando un error de falla de segmentación.

>>> sys.setrecursionlimit(10**9)
>>> collatz(2**1000 + 1)
break found: 1
>>> collatz(2**4000 + 1)
Segmentation fault (core dumped)

Por favor, dame algunas sugerencias sobre lo que necesito para modificar para lograr un gran soporte de entrada.

3
Vicrobot 29 may. 2021 a las 21:16

2 respuestas

La mejor respuesta

Hazlo no recursivo, la recursión demasiado profunda se desborda la pila y la pila suele ser solo pocos megabytes. Después del desbordamiento de la pila, su programa se bloquea con falla de segmentación.

Su código modificado para volverse no recursivo (que no se bloquea):

Pruébalo en línea!

def collatz(n):
    while True:
        if (n == -1 or n == 1 or n == -17 or n == -17 -2**4096):
            print('break found', n)
            return
        if str(n)[-1] in ['1','3','5','7','9']:
            #print(n)
            n = 3 * n + 1
        else:
            n = n // 2


collatz(2**4000 + 1)

Salida:

break found 1

BTW, el problema clásico de Collatz se puede resolver con un código mucho más corto y más rápido, por ejemplo, como este:

Pruébalo en línea!

def collatz(n):
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

print('Collatz chain length:', collatz(2**4000 + 1))

Salida:

Collatz chain length: 29400

También solo por una nota lateral. Quiero mencionar la biblioteca de Python gmpy2 basado en la famosa C-basada gmp. Tiene un código de aritméticos entero muy optimizado y se puede usar para aumentar su código si realmente necesita velocidad.

En Windows GMPY2 se puede instalar descargándolo desde aquí e instalando a través de pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl. En Linux se puede instalar a través de sudo apt install python3-gmpy2.

Después de la instalación, puede usar GMPY2 de una manera muy simple, como en la función collatz_gmpy() a continuación:

Pruébalo en línea!

def collatz_py(n):
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

def collatz_gmpy(n):
    from gmpy2 import mpz
    n = mpz(n)
    for i in range(1 << 50):
        if n == 1:
            return i
        n = 3 * n + 1 if n & 1 else n >> 1

def test():
    import timeit
    n = 2 ** 100000 + 1
    for i, f in enumerate([collatz_py, collatz_gmpy]):
        print(f.__name__, round(timeit.timeit(lambda: f(n), number = 1), 3), 'secs')

test()

Salida:

collatz_py 7.477 secs
collatz_gmpy 2.916 secs

Como se puede ver la variante GMPY2 le da a 2.56x Times Times SpeedUp en comparación con la variante regular de Python.

2
Arty 30 may. 2021 a las 09:39

Lo escribiría como:

def collatz(n):
    tmp = -17 - 2**4096            # precompute constant value outside loop
    while 1:                       # in general, iteration is better than recursion in Python for these kinds of functions
        if n in (-1, 1, -17, tmp): # less typing than lots of or clauses
            return n               # return values rather than printing them
        elif n % 2 == 1:           # faster than converting to string and checking last digit
            n = 3*n + 1
        else:
            n //= 2

Llámalo con E.G.:

print(collatz(2**4000 + 1))

Performance: en mi PC, collatz(2**5000-1) con el código anterior toma 0.069 segs. Cambiar el código a elif str(n)[-1] in '13579': hace que sea necesario 1.606 segundos, es decir, 23x más lento.

En collatz(2**40000-1), el código anterior utilizado 3.822 segundos. Cambiando

elif n % 2 == 1:

A cualquiera

elif n % 2:

O

elif n & 1:

Redujo el tiempo a 1.988 segundos (es decir, no hay diferencia).

Cambiando n //= 2 a n >>= 1 Reducido el tiempo adicional a 1.506 segundos.

1
thebjorn 29 may. 2021 a las 19:02