Comprueba si un número es un cuadrado perfecto.

¿Cómo puedo comprobar si un número es un cuadrado perfecto?

La velocidad no es una preocupación, por ahora, solo funciona.

_{Ver también: Raíz cuadrada entera en Python .}

Mar 22 '10 07:03

Utilice el método de Newton para concentrarse rápidamente en la raíz cuadrada entera más cercana, luego elevarla al cuadrado y ver si es su número. Ver isqrt .

Python ≥ 3,8 tiene math.isqrt. Si utiliza una versión anterior de Python, busque la " def isqrt(n)" implementación aquí .

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

Mar 22 '2010 01:03 President James K. Polk

Si está interesado, tengo una respuesta puramente matemática a una pregunta similar en Math Stackexchange, "Detectar cuadrados perfectos más rápido que extrayendo la raíz cuadrada" .

Puede que mi propia implementación de isSquare(n) no sea la mejor, pero me gusta. Me tomó varios meses de estudio en teoría matemática, computación digital y programación en Python, comparándome con otros contribuyentes, etc., para realmente hacer clic con este método. Aunque me gusta su simplicidad y eficiencia. No he visto nada mejor. Dime que piensas.

def isSquare(n):
    ## Trivial checks
    if type(n) != int:  ## integer
        return False
    if n < 0:      ## positivity
        return False
    if n == 0:      ## 0 pass
        return True

    ## Reduction by powers of 4 with bit-logic
    while n&3 == 0:    
        n=n>>2

    ## Simple bit-logic test. All perfect squares, in binary,
    ## end in 001, when powers of 4 are factored out.
    if n&7 != 1:
        return False

    if n==1:
        return True  ## is power of 4, or even power of 2


    ## Simple modulo equivalency test
    c = n%10
    if c in {3, 7}:
        return False  ## Not 1,4,5,6,9 in mod 10
    if n % 7 in {3, 5, 6}:
        return False  ## Not 1,2,4 mod 7
    if n % 9 in {2,3,5,6,8}:
        return False  
    if n % 13 in {2,5,6,7,8,11}:
        return False  

    ## Other patterns
    if c == 5:  ## if it ends in a 5
        if (n//10)%10 != 2:
            return False    ## then it must end in 25
        if (n//100)%10 not in {0,2,6}: 
            return False    ## and in 025, 225, or 625
        if (n//100)%10 == 6:
            if (n//1000)%10 not in {0,5}:
                return False    ## that is, 0625 or 5625
    else:
        if (n//10)%4 != 0:
            return False    ## (4k)*10 + (1,9)


    ## Babylonian Algorithm. Finding the integer square root.
    ## Root extraction.
    s = (len(str(n))-1) // 2
    x = (10**s) * 4

    A = {x, n}
    while x * x != n:
        x = (x + (n // x)) >> 1
        if x in A:
            return False
        A.add(x)
    return True

Muy claro. Primero comprueba que tenemos un número entero, y además positivo. De lo contrario no tiene sentido. Permite que 0 se deslice como Verdadero (es necesario o, de lo contrario, el siguiente bloque es un bucle infinito).

El siguiente bloque de código elimina sistemáticamente potencias de 4 en un subalgoritmo muy rápido que utiliza operaciones lógicas y de desplazamiento de bits. En última instancia, no encontramos el isSquare de nuestro n original, sino de un k<n que ha sido reducido en potencias de 4, si es posible. Esto reduce el tamaño del número con el que estamos trabajando y realmente acelera el método babilónico, pero también hace que otras comprobaciones sean más rápidas.

El tercer bloque de código realiza una simple prueba booleana de lógica de bits. Los tres dígitos menos significativos, en binario, de cualquier cuadrado perfecto son 001. Siempre. De todos modos, salvo los ceros iniciales resultantes de potencias de 4, que ya se han contabilizado. Si no pasa la prueba, inmediatamente sabrás que no es un cuadrado. Si pasa, no puedes estar seguro.

Además, si terminamos con un 1 para un valor de prueba, entonces el número de prueba era originalmente una potencia de 4, incluido quizás el 1 mismo.

Al igual que el tercer bloque, el cuarto prueba el valor de las unidades en decimal usando un operador de módulo simple y tiende a detectar valores que pasan desapercibidos en la prueba anterior. También una prueba de mod 7, mod 8, mod 9 y mod 13.

El quinto bloque de código busca algunos de los patrones cuadrados perfectos más conocidos. Los números que terminan en 1 o 9 van precedidos de un múltiplo de cuatro. Y los números que terminan en 5 deben terminar en 5625, 0625, 225 o 025. Había incluido otros, pero me di cuenta de que eran redundantes o que nunca se usaban.

Por último, el sexto bloque de código se parece mucho a la respuesta del principal respondedor, Alex Martelli. Básicamente encuentra la raíz cuadrada usando el antiguo algoritmo babilónico, pero restringiéndolo a valores enteros ignorando el punto flotante. Hecho tanto para la velocidad como para ampliar las magnitudes de los valores que son comprobables. Utilicé conjuntos en lugar de listas porque lleva mucho menos tiempo, utilicé cambios de bits en lugar de división por dos y elegí inteligentemente un valor inicial mucho más eficiente.

Por cierto, probé el número de prueba recomendado por Alex Martelli, así como algunos números de muchos órdenes de magnitud mayores, como por ejemplo:

x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
    print(i, isSquare(i))

imprimió los siguientes resultados:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

Y lo hizo en 0,33 segundos.

En mi opinión, mi algoritmo funciona igual que el de Alex Martelli, con todos sus beneficios, pero tiene el beneficio adicional de rechazos de pruebas simples altamente eficientes que ahorran mucho tiempo, sin mencionar la reducción del tamaño de los números de prueba por potencias de 4, que mejora la velocidad, la eficiencia, la precisión y el tamaño de los números comprobables. Probablemente sea especialmente cierto en implementaciones que no son de Python.

Aproximadamente el 99% de todos los números enteros se rechazan como no cuadrados incluso antes de que se implemente la extracción de raíces babilónicas, y en 2/3 del tiempo que le tomaría a los babilónicos rechazar el número entero. Y aunque estas pruebas no aceleran el proceso de manera significativa, la reducción de todos los números de las pruebas a un número impar al dividir todas las potencias de 4 realmente acelera la prueba babilónica.

Hice una prueba de comparación de tiempos. Probé todos los números enteros del 1 al 10 millones sucesivamente. Usando solo el método babilónico (con mi suposición inicial especialmente diseñada), mi Surface 3 tardó un promedio de 165 segundos (con 100% de precisión). Usando solo las pruebas lógicas en mi algoritmo (excluyendo el babilónico), tomó 127 segundos, rechazó el 99% de todos los números enteros como no cuadrados sin rechazar por error ningún cuadrado perfecto. De los números enteros que pasaron, sólo el 3% eran cuadrados perfectos (una densidad mucho mayor). Utilizando el algoritmo completo anterior que emplea tanto las pruebas lógicas como la extracción de raíces babilónicas, tenemos una precisión del 100% y la prueba se completa en solo 14 segundos. La prueba de los primeros 100 millones de enteros tarda aproximadamente 2 minutos y 45 segundos.

EDITAR: He podido reducir aún más el tiempo. Ahora puedo probar los números enteros del 0 al 100 millones en 1 minuto y 40 segundos. Se pierde mucho tiempo comprobando el tipo de datos y la positividad. Elimine las dos primeras comprobaciones y reduzco el experimento en un minuto. Se debe asumir que el usuario es lo suficientemente inteligente como para saber que los negativos y los flotantes no son cuadrados perfectos.

Aug 16 '2017 23:08 CogitoErgoCogitoSum

Dado que nunca se puede depender de comparaciones exactas cuando se trata de cálculos de punto flotante (como estas formas de calcular la raíz cuadrada), sería una implementación menos propensa a errores.

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

Imagínense integeres 9. math.sqrt(9)podría ser 3.0, pero también podría ser algo como 2.99999o 3.00001, por lo que elevar el resultado al cuadrado no es confiable. Sabiendo que esto inttoma el valor mínimo, aumentar el valor flotante primero 0.5significa que obtendremos el valor que estamos buscando si estamos en un rango donde floattodavía tenemos una resolución lo suficientemente fina como para representar números cercanos al que estamos buscando. .

Mar 22 '2010 01:03 Mike Graham