Compruebe si un número es un cuadrado perfecto

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

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

El problema de confiar en cualquier cálculo de punto flotante ( math.sqrt(x) , o x**0.5 ) es que realmente no puede estar seguro de que sea exacto (para enteros suficientemente grandes x , no lo será, e incluso podría rebosar). Afortunadamente (si uno no tiene prisa 😉 hay muchos enfoques de enteros puros, como los siguientes …

 def is_square(apositiveint): x = apositiveint // 2 seen = set([x]) while x * x != apositiveint: x = (x + (apositiveint // x)) // 2 if x in seen: return False seen.add(x) return True for i in range(110, 130): print i, is_square(i) 

Sugerencia: se basa en el “algoritmo babilónico” para la raíz cuadrada, vea wikipedia . Funciona para cualquier número positivo para el que tenga suficiente memoria para que el cálculo continúe hasta completarse ;-).

Edición : veamos un ejemplo …

 x = 12345678987654321234567 ** 2 for i in range(x, x+2): print i, is_square(i) 

esto se imprime, según se desee (y en un tiempo razonable, también ;-):

 152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False 

Por favor, antes de proponer soluciones basadas en resultados intermedios de punto flotante, asegúrese de que funcionen correctamente en este simple ejemplo. No es tan difícil (solo necesita unos cuantos controles adicionales en caso de que el valor de sqrt computado esté un poco apagado). un poco de cuidado

Y luego intente con x**7 y encuentre una manera inteligente de solucionar el problema que obtendrá.

 OverflowError: long int too large to convert to float 

Tendrás que ser más inteligente a medida que los números sigan creciendo, por supuesto.

Si tuviera prisa, por supuesto, usaría gmpy , pero entonces, estoy claramente sesgado ;-).

 >>> import gmpy >>> gmpy.is_square(x**7) 1 >>> gmpy.is_square(x**7 + 1) 0 

Sí, lo sé, eso es tan fácil que se siente como hacer trampa (un poco de la manera en que me siento hacia Python en general 😉 – no hay inteligencia en absoluto, solo una franqueza perfecta y simplicidad (y, en el caso de gmpy, pura velocidad ; -) …

Use el método de Newton para concentrarse rápidamente en la raíz cuadrada del entero más cercano, luego enmarque y vea si es su número. Ver isqrt .

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

 import math def is_square(integer): root = math.sqrt(integer) if int(root + 0.5) ** 2 == integer: return True else: return False 

Imagina que el integer es 9 . math.sqrt(9) podría ser 3.0 , pero también podría ser algo como 2.99999 o 3.00001 , por lo que cuadrar el resultado de inmediato no es confiable. Sabiendo que int toma el valor de piso, boost el valor de flotación en 0.5 primero significa que obtendremos el valor que estamos buscando si estamos en un rango donde el float todavía tiene una resolución lo suficientemente fina como para representar números cerca del valor para el que nosotros estamos mirando.

 import math if (math.sqrt(number)-int(math.sqrt(number))): print "it's not a perfect square" 

Un cuadrado perfecto es un número que se puede express como el producto de dos enteros iguales. math.sqrt(number) devuelve un float . int(math.sqrt(number)) el resultado en int .

Si la raíz cuadrada es un número entero, como 3, por ejemplo, entonces math.sqrt(number) - int(math.sqrt(number)) será 0, y la sentencia if será False . Si la raíz cuadrada es un número real como 3.2, entonces será True e imprimirá “no es un cuadrado perfecto”.

Si está interesado, tengo una respuesta matemática pura a una pregunta similar en el intercambio de stack de matemáticas, “Detectar cuadrados perfectos más rápido que extrayendo la raíz cuadrada” .

Mi propia implementación de isSquare (n) puede no ser la mejor, pero me gusta. Me llevó varios meses de estudio en teoría matemática, computación digital y progtwigción en python, comparándome con otros colaboradores, etc., para realmente hacer clic con este método. Aunque me gusta su sencillez y eficiencia. No he visto 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 verifica que tengamos un entero y uno positivo. De lo contrario no tiene sentido. Permite que el 0 se deslice como Verdadero (necesario o el siguiente bloque es un bucle infinito).

El siguiente bloque de código elimina sistemáticamente las potencias de 4 en un sub-algoritmo muy rápido que utiliza el desplazamiento de bits y las operaciones lógicas de bits. En última instancia, no estamos encontrando la IsSquare de nuestra n original, sino una k

El tercer bloque de código realiza una prueba simple de lógica de bits booleana. Los tres dígitos menos significativos, en binario, de cualquier cuadrado perfecto son 001. Siempre. Salvo para los ceros iniciales resultantes de potencias de 4, de todos modos, que ya se han contabilizado. Si falla la prueba, inmediatamente sabes 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 fue originalmente una potencia de 4, incluido quizás 1.

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 capturar los valores que se deslizan a través de la prueba anterior. También pruebas de mod 7, mod 8, mod 9 y mod 13.

El quinto bloque de código comprueba algunos de los conocidos patrones cuadrados perfectos. Los números que terminan en 1 o 9 están precedidos por un múltiplo de cuatro. Y los números que terminan en 5 deben terminar en 5625, 0625, 225 o 025. Incluí otros, pero me di cuenta de que eran redundantes o que nunca fueron usados.

Por último, el sexto bloque de código se parece mucho a lo que responde el contestador principal, Alex Martelli. Básicamente encuentra la raíz cuadrada usando el algoritmo babilónico antiguo, pero restringiéndolo a valores enteros mientras ignora 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, usé cambios de bits en lugar de división por dos, y elegí inteligentemente un valor de inicio inicial de manera mucho más eficiente.

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

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

imprimió los siguientes resultados:

  True 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, por no mencionar la reducción en el 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 que se pueden probar. Probablemente especialmente cierto en implementaciones que no sean de Python.

Aproximadamente el 99% de todos los enteros se rechazan como no cuadrados antes de que se implemente la extracción de la raíz babilónica, y en 2/3 el tiempo que tomaría el babilonio para rechazar el entero. Y aunque estas pruebas no aceleran el proceso de manera significativa, la reducción de todos los números de prueba a un número extraño dividiendo todos los poderes de 4 realmente acelera la prueba de Babilonia.

Hice una prueba de comparación de tiempo. Probé todos los enteros de 1 a 10 millones en sucesión. Usando solo el método babilónico solo (con mi estimación inicial especialmente adaptada), mi Surface 3 tomó un promedio de 165 segundos (con 100% de precisión). Usando solo las pruebas lógicas en mi algoritmo (excluyendo el babilonio), tomó 127 segundos, rechazó el 99% de todos los enteros como no cuadrados sin rechazar por error ningún cuadrado perfecto. De esos enteros que pasaron, solo el 3% eran cuadrados perfectos (una densidad mucho mayor). Usando el algoritmo completo anterior que emplea tanto las pruebas lógicas como la extracción de la raíz babilónica, tenemos el 100% de precisión y la finalización de la prueba en solo 14 segundos. Los primeros 100 millones de enteros tardan aproximadamente 2 minutos y 45 segundos en probarse.

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

Soy nuevo en Stack Overflow e hice una revisión rápida para encontrar una solución. Acabo de publicar una ligera variación en algunos de los ejemplos anteriores en otro hilo ( Encontrando cuadrados perfectos ) y pensé que incluiría una ligera variación de lo que publiqué aquí (usando nsqrt como una variable temporal), en caso de que sea de interés / utilizar:

 import math def is_perfect_square(n): if not ( isinstance(n, (int, long)) and ( n >= 0 ) ): return False else: nsqrt = math.sqrt(n) return nsqrt == math.trunc(nsqrt) 

Esto se puede resolver utilizando el módulo decimal para obtener raíces cuadradas de precisión arbitraria y verificaciones fáciles de “exactitud”:

 import math from decimal import localcontext, Context, Inexact def is_perfect_square(x): # If you want to allow negative squares, then set x = abs(x) instead if x < 0: return False # Create localized, default context so flags and traps unset with localcontext(Context()) as ctx: # Set a precision sufficient to represent x exactly; `x or 1` avoids # math domain error for log10 when x is 0 ctx.prec = math.ceil(math.log10(x or 1)) + 1 # Wrap ceil call in int() on Py2 # Compute integer square root; don't even store result, just setting flags ctx.sqrt(x).to_integral_exact() # If previous line couldn't represent square root as exact int, sets Inexact flag return not ctx.flags[Inexact] 

Para demostraciones con valores verdaderamente enormes:

 # I just kept mashing the numpad for awhile :-) >>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324 >>> sqr = base ** 2 >>> sqr ** 0.5 # Too large to use floating point math Traceback (most recent call last): File "", line 1, in  OverflowError: int too large to convert to float >>> is_perfect_power(sqr) True >>> is_perfect_power(sqr-1) False >>> is_perfect_power(sqr+1) False 

Si aumenta el tamaño del valor que se está probando, esto eventualmente se vuelve más lento (toma cerca de un segundo para un cuadrado de 200,000 bits), pero para números más moderados (por ejemplo, 20,000 bits), es aún más rápido de lo que un humano notaría. valores individuales (~ 33 ms en mi máquina). Pero como la velocidad no era su principal preocupación, esta es una buena manera de hacerlo con las bibliotecas estándar de Python.

Por supuesto, sería mucho más rápido usar gmpy2 y solo probar gmpy2.mpz(x).is_square() , pero si los paquetes de terceros no son lo tuyo, lo anterior funciona bastante bien.

Mi respuesta sería:

 def checkSquare(x):return x**.5%1==0 

Básicamente, esto hace una raíz cuadrada, luego módulo por 1 para eliminar la parte entera y, si el resultado es 0, devuelve True si no, devuelve False . En este caso, x puede ser cualquier número grande, pero no tan grande como el número máximo de flotación que Python puede manejar: 1.7976931348623157e + 308

Este es mi metodo

 int(n**0.5)**2 == int(n) 

tome la raíz cuadrada del número, conviértalo a entero, luego tome el cuadrado si los números son iguales, de lo contrario, es un cuadrado perfecto.

Podrías buscar binario para la raíz cuadrada redondeada. Cuadrar el resultado para ver si coincide con el valor original.

Probablemente esté mejor con la respuesta de FogleBirds, aunque tenga cuidado, ya que la aritmética de punto flotante es aproximada, lo que puede deshabilitar este enfoque. En principio, podría obtener un falso positivo de un entero grande, que es uno más que un cuadrado perfecto, por ejemplo, debido a la pérdida de precisión.

  1. Decide cuánto tiempo será el número.
  2. tomar un delta 0.000000000000 ……. 000001
  3. vea si (sqrt (x)) ^ 2 – x es mayor / igual / menor que delta y decida en función del error delta.

Esta respuesta no corresponde a su pregunta establecida, sino a una pregunta implícita que veo en el código que publicó, es decir, “¿cómo verificar si algo es un número entero?”

La primera respuesta que generalmente obtendrás a esa pregunta es “¡No!” Y es cierto que en Python, la comprobación de tipos no suele ser lo correcto.

Sin embargo, para esas raras excepciones, en lugar de buscar un punto decimal en la representación de la cadena del número, lo que hay que hacer es usar la función isinstance :

 >>> isinstance(5,int) True >>> isinstance(5.0,int) False 

Por supuesto, esto se aplica a la variable en lugar de un valor. Si quisiera determinar si el valor era un entero, haría esto:

 >>> x=5.0 >>> round(x) == x True 

Pero como todos los demás han cubierto en detalle, hay problemas de punto flotante que deben considerarse en la mayoría de los ejemplos que no son de juguete de este tipo de cosas.

Si quieres recorrer un rango y hacer algo por cada número que NO sea un cuadrado perfecto, podrías hacer algo como esto:

 def non_squares(upper): next_square = 0 diff = 1 for i in range(0, upper): if i == next_square: next_square += diff diff += 2 continue yield i 

Si desea hacer algo por cada número que sea un cuadrado perfecto, el generador es aún más fácil:

 (n * n for n in range(upper)) 

Creo que esto funciona y es muy simple:

 from math import sqrt def is_perfect_square(num): return int(sqrt(num)) == sqrt(num) 

Esto es numéricamente una solución tan ingenua como posiblemente puedas tener. Funciona para pequeños números.

 def is_perfect_square(n): return (n ** .5).is_integer() 

Evidentemente, falla para un gran número, como 152415789666209426002111556165263283035677490.

No estoy seguro de Python, pero podrías hacer algo como:

 function isSquare(x) = x == floor(sqrt(x) + 0.5)^2 

Es decir, tomar un número, encontrar la raíz cuadrada, redondearlo al número entero más cercano, cuadrarlo y probar si es el mismo que el número original. (el floor y la adición de 0.5 se realizan para evitar que los casos como sqrt(4) devuelvan 1.9999999... debido a las matemáticas de punto flotante, como señaló Mike Graham).

En caso de que esté interesado, hubo una vez una muy buena discusión sobre la forma más rápida de determinar si la raíz cuadrada de un entero es un entero .

Editado para su aclaración.

 a = math.sqrt(n) b = int(a) a == b 

Tengo una leve mejora en la solución original utilizando el enfoque babilónico. En lugar de utilizar un conjunto para almacenar todas las aproximaciones generadas anteriormente, solo las dos aproximaciones más recientes se almacenan y se verifican con la aproximación actual. Esto ahorra la enorme cantidad de tiempo perdido en la comprobación de todo el conjunto de aproximaciones anteriores. Estoy usando java en lugar de python y una clase BigInteger en lugar de un entero primitivo normal.

  BigInteger S = BigInteger.ZERO; BigInteger x = BigInteger.ZERO; BigInteger prev1 = BigInteger.ZERO; BigInteger prev2 = BigInteger.ZERO; Boolean isInt = null; x = S.divide(BigInteger.valueOf(2)); while (true) { x = x.add(preA.divide(x)).divide(BigInteger.valueOf(2)); if (x.pow(2).equals(S)) { isInt = true; break; } if (prev1.equals(x) || prev2.equals(x)) { isInt = false; break; } prev2 = prev1; prev1 = x; } 

Hay una manera MUY fácil de hacer esto. Encuentra cuántos factores tiene el número (incluido uno y sí mismo). Si tiene una cantidad impar de factores, es un cuadrado.

 def getFactors(n): '''Code for counting factors of n.''' result = 1 # not forgetting to count the number itself for i in range(1, n // 2 + 1): if n % i == 0: result += 1 return result 

Si el resultado de la función es impar, es un cuadrado.

EDITAR:

Puede que este no sea el mejor método para un progtwig de computadora, pero es un buen método para los humanos.