Raíz cuadrada entera en Python

¿Existe una raíz cuadrada entera en algún lugar de Python o de las bibliotecas estándar? Quiero que sea exacto (es decir, que devuelva un número entero) y generar una excepción si la entrada no es un cuadrado perfecto.

Intenté usar este código:

def isqrt(n):
    i = int(math.sqrt(n) + 0.5)
    if i**2 == n:
        return i
    raise ValueError('input was not a perfect square')

Pero es feo y realmente no confío en él para números enteros grandes. Podría recorrer los cuadrados y rendirme si excedí el valor, pero supongo que sería un poco lento hacer algo así. Además, ¿seguramente esto ya está implementado en alguna parte?

_{Ver también: Comprobar si un número es un cuadrado perfecto .}

Mar 13 '13 23:03 wim

Nota: Ahora está math.isqrten stdlib, disponible desde Python 3.8.

El método de Newton funciona perfectamente con números enteros:

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Esto devuelve el entero más grande x para el cual x * x no excede n . Si quieres comprobar si el resultado es exactamente la raíz cuadrada, simplemente realiza la multiplicación para comprobar si n es un cuadrado perfecto.

Hablo de este algoritmo y de otros tres algoritmos para calcular raíces cuadradas en mi blog .

Mar 13 '2013 16:03 user448810

Actualización: ¡ Python 3.8 tiene una math.isqrtfunción en la biblioteca estándar!

Aquí comparé cada función (correcta) tanto en entradas pequeñas (0…2 ²² ) como grandes (2 ⁵⁰⁰⁰¹ ). Los claros ganadores en ambos casos son gmpy2.isqrtlos sugeridos por Mathmandan en primer lugar, seguido por Python 3.8 math.isqrten segundo lugar, seguido por la receta ActiveState vinculada por NPE en tercer lugar. La receta ActiveState tiene un montón de divisiones que pueden ser reemplazadas por turnos, lo que la hace un poco más rápida (pero aún por detrás de las funciones nativas):

def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1 >> 1)
        while True:
            y = (x + n // x) >> 1
            if y >= x:
                return x
            x = y
    elif n == 0:
        return 0
    else:
        raise ValueError("square root not defined for negative numbers")

Resultados de referencia:

gmpy2.isqrt()(mathmandan) : 0,08 µs pequeño, 0,07 ms grande
int(gmpy2.isqrt())*: 0,3 µs pequeño, 0,07 ms grande
Python 3.8 math.isqrt: 0,13 µs pequeño, 0,9 ms grande
ActiveState (optimizado como arriba) : 0,6 µs pequeño, 17,0 ms grande
ActiveState (NPE) : 1,0 µs pequeño, 17,3 ms grande
Castlebravo de mano larga : 4 µs pequeño, 80 ms grande
Mathmandan mejorado : 2,7 µs pequeño, 120 ms grande
martineau (con esta corrección ): 2,3 µs pequeño, 140 ms grande
nibot : 8 µs pequeño, 1000 ms grande
Mathmandan : 1,8 µs pequeño, 2200 ms grande
Método de Castlebravo Newton : 1,5 µs pequeño, 19000 ms grande
user448810 : 1,4 µs pequeño, 20000 ms grande

(* Dado que gmpy2.isqrtdevuelve un gmpy2.mpzobjeto, que se comporta principalmente pero no exactamente como un int, es posible que deba volver a convertirlo en an intpara algunos usos).

Dec 31 '2018 04:12 Anders Kaseorg

Perdón por la respuesta tan tardía; Me acabo de topar con esta página. En caso de que alguien visite esta página en el futuro, el módulo de Python gmpy2 está diseñado para funcionar con entradas muy grandes e incluye, entre otras cosas, una función de raíz cuadrada entera.

Ejemplo:

>>> import gmpy2
>>> gmpy2.isqrt((10**100+1)**2)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L)
>>> gmpy2.isqrt((10**100+1)**2 - 1)
mpz(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L)

Por supuesto, todo tendrá la etiqueta "mpz", pero los mpz son compatibles con los int:

>>> gmpy2.mpz(3)*4
mpz(12)

>>> int(gmpy2.mpz(12))
12

Consulte mi otra respuesta para obtener una discusión sobre el rendimiento de este método en relación con otras respuestas a esta pregunta.

Descargar: https://code.google.com/p/gmpy/

Jul 05 '2013 19:07 mathmandan