python - built - ¿Cómo podría verificar si un número es un cuadrado perfecto?
python math gdc (19)
¿Cómo podría verificar si un número es un cuadrado perfecto?
La velocidad no tiene importancia, por ahora, solo funciona.
- Decida cuánto tiempo será el número.
- tomar un delta 0.000000000000 ....... 000001
- vea si el (sqrt (x)) ^ 2 - x es mayor / igual / más pequeño que delta y decida en función del error delta.
Creo que esto funciona y es muy simple:
from math import sqrt
def is_perfect_square(num):
return int(sqrt(num)) == sqrt(num)
Dado que nunca se puede depender de comparaciones exactas cuando se trata de cálculos en coma 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 así como 2.99999 o 3.00001 , por lo que cuadrar el resultado de inmediato no es confiable. Sabiendo que int toma el valor mínimo, aumentar el valor flotante 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 cercanos a aquel para el cual nosotros estamos mirando.
Esta respuesta no pertenece a su pregunta planteada, 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á a esa pregunta es "¡No lo hagas!" Y es verdad que en Python, la verificación de tipo generalmente no es lo correcto.
Sin embargo, para esas raras excepciones, en lugar de buscar un punto decimal en la representación de cadena del número, lo que hay que hacer es usar la función de instancia is :
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Por supuesto, esto se aplica a la variable en lugar de a un valor. Si quisiera determinar si el valor era un número entero, haría esto:
>>> x=5.0
>>> round(x) == x
True
Pero como todos los demás han cubierto en detalle, hay cuestiones de punto flotante que deben considerarse en la mayoría de los ejemplos que no son juguetes de este tipo de cosas.
Este es mi método
int(n**0.5)**2 == int(n)
tomar la raíz cuadrada del número convertir a entero y luego tomar el cuadrado si los números son iguales, entonces es un cuadrado perfecto, de lo contrario no.
Esto es numéricamente una solución tan ingenua como sea posible. Funciona para números pequeños.
def is_perfect_square(n):
return (n ** .5).is_integer()
Evidentemente falla para un gran número como 152415789666209426002111556165263283035677490.
Esto se puede resolver usando 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 la demostración 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 "<stdin>", line 1, in <module>
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 prueba, con el tiempo se vuelve lento (tarda casi un segundo en un cuadrado de 200,000 bits), pero para números más moderados (digamos 20,000 bits), es aún más rápido de lo que un humano se daría cuenta valores individuales (~ 33 ms en mi máquina). Pero como la velocidad no era su principal preocupación, esta es una buena forma de hacerlo con las bibliotecas estándar de Python.
Por supuesto, sería mucho más rápido usar gmpy2 y simplemente probar gmpy2.mpz(x).is_square() , pero si los paquetes de terceros no son lo tuyo, lo anterior funciona bastante bien.
Hay una manera MUY fácil de hacer esto. Encuentre 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:
Este podría no ser el mejor método para un programa de computadora, pero es un buen método para los humanos.
Mi respuesta sería:
def checkSquare(x):return x**.5%1==0
Esto básicamente hace una raíz cuadrada, luego módulo en 1 para quitar la parte entera y si el resultado es 0, devuelve True contrario, devuelve False . En este caso, x puede ser cualquier número grande, pero no tan grande como el número máximo de flotador que puede manejar python: 1.7976931348623157e + 308
No estoy seguro de Python, pero podrías hacer algo como:
function isSquare(x) = x == floor(sqrt(x) + 0.5)^2
Es decir, tome un número, encuentre la raíz cuadrada, redondee al entero más cercano, cuadre y pruebe si es igual al número original. (el floor y la adición de 0.5 se realiza para evitar que casos como sqrt(4) devuelvan 1.9999999... debido a la matemática de punto flotante, como señaló Mike Graham).
En caso de que le interese, 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 número entero .
Editado para aclaración.
Podría buscar binariamente la raíz cuadrada redondeada. Cuadre el resultado para ver si coincide con el valor original.
Probablemente estés mejor con la respuesta de FogleBirds, aunque ten cuidado, ya que la aritmética de coma flotante es aproximada, lo que puede descartar 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.
Si desea recorrer un rango y hacer algo para cada número que NO sea un cuadrado perfecto, podría 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 para cada número que ES un cuadrado perfecto, el generador es aún más fácil:
(n * n for n in range(upper))
Si estás interesado, tengo una respuesta matemática pura a una pregunta similar en math stackexchange, "Detectando 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 tomó varios meses de estudio en teoría matemática, computación digital y programación python, comparándome con otros colaboradores, etc., para realmente hacer clic con este método. Aunque me gusta su simplicidad 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 comprueba que tenemos un número entero, y uno positivo en eso. De lo contrario, no tiene sentido. Permite que 0 se deslice a través de True (necesario o si el siguiente bloque es infinito).
El siguiente bloque de código elimina sistemáticamente las potencias de 4 en un subalgoritmo muy rápido utilizando operaciones de bit shift y bit logic. En última instancia, no estamos encontrando el isSquare de nuestro n original, sino de un k <n que ha sido reducido por 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 de Babilonia, pero también hace otras verificaciones más rápidas también.
El tercer bloque de código realiza una prueba de lógica de bits Booleana simple. Los tres dígitos menos significativos, en binario, de cualquier cuadrado perfecto son 001. Siempre. Ahorre para los ceros a la izquierda como resultado de las potencias de 4, de todos modos, que ya se han tenido en cuenta. Si no pasa la prueba, inmediatamente sabrá 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, incluyendo quizás 1 en sí mismo.
Al igual que el tercer bloque, el cuarto prueba el valor de una posición en decimal usando el operador de módulo simple, y tiende a capturar valores que se deslizan a través de la prueba anterior. También una prueba de mod 7, mod 8, mod 9 y mod 13.
El quinto bloque de código comprueba algunos de los patrones cuadrados perfectos conocidos. 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. Había incluido otros pero me di cuenta de que eran redundantes o que nunca se usaban realmente.
Por último, el sexto bloque de código se asemeja mucho a lo que responde el respondedor superior, Alex Martelli. Básicamente, encuentra la raíz cuadrada usando el antiguo algoritmo babilónico, pero restringiéndolo a valores enteros sin tener en cuenta el punto flotante. Hecho tanto para la velocidad como para extender las magnitudes de los valores que se pueden probar. Utilicé sets en lugar de listas porque lleva mucho menos tiempo, utilicé cambios de bits en lugar de división por dos, y escogí inteligentemente un valor de inicio 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 mayor, como:
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 agregado de rechazos de prueba simple altamente eficientes que ahorran mucho tiempo, sin mencionar la reducción en el tamaño de los números de prueba por poderes 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 son rechazados como no cuadrados antes de que la extracción de raíz babilónica se implemente, y en 2/3 el tiempo le tomaría a Babilonia rechazar el número entero. Y aunque estas pruebas no aceleran el proceso de manera significativa, la reducción en todos los números de prueba a impar al dividir 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 por sí mismo (con mi conjetura 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 babilonio), tardó 127 segundos, rechazó el 99% de todos los enteros como no cuadrados sin rechazar por error cuadrados perfectos. De esos enteros que pasaron, solo el 3% eran cuadrados perfectos (una densidad mucho más alta). Usando el algoritmo completo anterior que emplea tanto las pruebas lógicas como la extracción de raíz babilónica, tenemos una precisión del 100% y la finalización de la prueba en solo 14 segundos. Los primeros enteros de 100 millones demoran aproximadamente 2 minutos y 45 segundos en probarse.
EDITAR: He podido reducir el tiempo aún más. Ahora puedo probar los enteros de 0 a 100 millones en 1 minuto y 40 segundos. Se desperdicia mucho tiempo verificando el tipo de datos y la positividad. Elimine los primeros dos controles y reduzco el experimento por un minuto. Uno debe suponer que el usuario es lo suficientemente inteligente como para saber que los negativos y las carrozas no son cuadrados perfectos.
Soy nuevo en e hice una búsqueda rápida para encontrar una solución. Acabo de publicar una pequeña variación en algunos de los ejemplos anteriores sobre otro hilo ( Encontrar cuadrados perfectos ) y pensé incluir una pequeña variación de lo que publiqué aquí (usando nsqrt como 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)
Tengo una ligera mejora en la solución original con el enfoque babilónico. En lugar de usar un conjunto para almacenar cada aproximación generada previamente, solo las dos aproximaciones más recientes se almacenan y se comparan con la aproximación actual. Esto ahorra la gran cantidad de tiempo desperdiciado al verificar 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;
}
Use el método de Newton para centrarse rápidamente en la raíz cuadrada entera más cercana, cuadrarla y ver si se trata de su número. Ver isqrt .
El problema de depender de cualquier cálculo de punto flotante ( math.sqrt(x) , o x**0.5 ) es que no se 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 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 de Babilonia" para la raíz cuadrada, ver wikipedia . Funciona para cualquier número positivo para el que tenga suficiente memoria para que el cálculo finalice ;-).
Editar : veamos un ejemplo ...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
esto se imprime, como se desee (y en un tiempo razonable, también ;-):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Antes de proponer soluciones basadas en resultados intermedios de coma flotante, asegúrese de que funcionen correctamente en este sencillo ejemplo: no es tan difícil (solo necesita unos cheques adicionales en caso de que el sqrt calculado esté un poco apagado), solo toma una un poco de cuidado.
Y luego intente con x**7 y encuentre una forma inteligente de evitar el problema que obtendrá,
OverflowError: long int too large to convert to float
Tendrás que ser cada vez más inteligente a medida que los números sigan creciendo, por supuesto.
Si gmpy prisa, por supuesto, usaría gmpy , pero entonces, estoy claramente predispuesto ;-).
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
Sí, lo sé, es tan fácil que parece una trampa (un poco lo que siento hacia Python en general ;-) - no tiene inteligencia, solo franqueza perfecta y simplicidad (y, en el caso de gmpy, pura velocidad) ; -) ...
a = math.sqrt(n)
b = int(a)
a == b
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 expresar como el producto de dos enteros iguales. math.sqrt(number) devuelve un float . int(math.sqrt(number)) arroja el resultado a int .
Si la raíz cuadrada es un número entero, como 3, por ejemplo, math.sqrt(number) - int(math.sqrt(number)) será 0 y la instrucción if será False . Si la raíz cuadrada era un número real como 3.2, entonces será True e imprimirá "no es un cuadrado perfecto".