Comprobar si un número es un cuadrado perfecto
https://stackoverflow.com/questions/2489435
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo puedo comprobar si un número es un cuadrado perfecto?
La velocidad no es su problema, por ahora, sólo de trabajo.
Solución
El problema de confiar en cualquier punto de cómputo flotante (math.sqrt(x) o x**0.5) es que realmente no se puede estar seguro de que es exacta (para lo suficientemente grandes números enteros x, no va a ser, y podría incluso desbordamiento). Afortunadamente (si uno no tiene prisa ;-) hay muchos enfoques enteros puros, tales como las 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" de raíz cuadrada, consulte Wikipedia . Es hace trabajo para cualquier número positivo para el que tenga suficiente memoria para el cálculo de proceder a su terminación; -).
Editar : vamos a ver un ejemplo ...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
este grabados, como se desee (y en una cantidad razonable de tiempo, también; -):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Por favor, antes de proponer soluciones basadas en flotante resultados intermedios de punto, asegurarse de que funcionan correctamente en este ejemplo simple - no es que disco (sólo tiene algunas verificaciones adicionales en caso de que la raíz cuadrada computarizada es un poco fuera), sólo se necesita un poco de cuidado.
Y a continuación, tratar con x**7 y encontrar forma inteligente para evitar el problema que obtendrá,
OverflowError: long int too large to convert to float
tendrá que conseguir más y más inteligente que los números siguen creciendo, por supuesto.
Si I era a toda prisa, por supuesto, que haría uso de gmpy - pero entonces, estoy claramente sesgada; -).
>>> 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 lo que siento hacia Python en general ;-) - ninguna inteligencia en absoluto, simplemente perfecta franqueza y simplicidad (y, en el caso de gmpy , velocidad pura; -) ...
Otros consejos
El método de Newton para uso rápidamente situarse en la raíz cuadrada entero más próximo, a continuación, la cuadratura y ver si es su número. Ver isqrt .
Python ≥ 3.8 tiene math.isqrt . Si se utiliza una versión anterior de Python, buscar la aplicación "def isqrt(n)" aquí .
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
Dado que nunca se puede confiar en las comparaciones exactas cuando se trata de cálculos de punto flotante (como estas formas de calcular la raíz cuadrada), una aplicación menos propenso a errores sería
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
Imagínese integer es 9. math.sqrt(9) podría 3.0, pero también podría ser algo así como 2.99999 o 3.00001, por lo que la cuadratura del resultado correcto fuera no es fiable. Sabiendo que int toma el valor piso, aumentando el valor de coma flotante por primera 0.5 significa que pondremos el valor que estamos buscando si estamos en un rango donde float todavía tiene una resolución lo suficientemente fina para representar números cerca de aquel para el cual estamos buscando.
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
Un cuadrado perfecto es un número que se puede expresar como el producto de dos números enteros iguales. math.sqrt(number) devolver un float. int(math.sqrt(number)) arroja el resultado de int.
Si la raíz cuadrada es un número entero, igual que 3, por ejemplo, entonces math.sqrt(number) - int(math.sqrt(number)) será 0, y se if la declaración False. Si la raíz cuadrada era un número real como 3.2, a continuación, se True e imprimir "no es un cuadrado perfecto".
falla por una gran no cuadrada como 152415789666209426002111556165263283035677490.
Si estás interesado, tengo un pura matemática de la respuesta a una pregunta similar en matemáticas stackexchange, "la Detección de los cuadrados perfectos más rápido que mediante la extracción de la raíz cuadrada".
Mi propia implementación de isSquare(n) puede no ser el mejor, pero me gusta.Me llevó varios meses de estudio en matemáticas, la teoría de la digital, la computación y la programación en python, compararme a los colaboradores, etc., realmente haga clic en con este método.Me gusta su simplicidad y eficiencia, aunque.No he visto mejor.Dime lo 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
Bastante recta hacia adelante.En primer lugar, comprueba que tenemos un número entero y positivo en el que.De lo contrario, no hay ningún punto.Se permite a 0 a través de deslizamiento como Verdadero (necesario o de lo contrario el siguiente bloque es el bucle infinito).
El siguiente bloque de código sistemáticamente elimina los poderes de los 4 en una muy rápida sub-algoritmo mediante desplazamiento de bits y bits operaciones lógicas.En última instancia no se encuentra la isSquare de nuestra original n, pero de un kEsto reduce el tamaño del número que estamos trabajando y realmente acelera el método Babilónico, pero también hace otras comprobaciones más rápido.
El tercer bloque de código que realiza una Booleana simple de los bits de la lógica de la prueba.El menos significativo de tres dígitos, en el binario, de cualquier cuadrado perfecto son 001.Siempre.Ahorrar para los ceros a la izquierda resultantes de los poderes de 4, de todos modos, la cual ya ha sido explicado.Si falla la prueba, inmediatamente sabe que no es un cuadrado.Si pasa, que no puedo estar seguro.
También, si terminamos con un 1 por un valor de prueba, a continuación, el número de la prueba fue originalmente una potencia de 4, incluyendo tal vez 1 en sí.
Como el tercer bloque, el cuarto pruebas de los-valor posicional en decimales mediante simple operador de módulo, y tiende a los valores de captura que se deslizan a través de la prueba anterior.También un mod 7, mod 8, mod 9, y mod 13 de prueba.
El quinto bloque de código comprueba algunos de los conocidos cuadrado perfecto patrones.Los números terminados en 1 o 9 son precedidos por un múltiplo de cuatro.Y los números que terminan en 5 debe terminar en 5625, 0625, 225, o 025.Yo había incluido a los demás, pero se dio cuenta de que eran redundantes, o en realidad nunca utilizado.
Por último, el sexto bloque de código se parece mucho a lo que el superior de la comunidad - Alex Martelli - respuesta.Básicamente busca la raíz cuadrada usando la antigua Babilonia algoritmo, pero se restringe a valores enteros, mientras hace caso omiso de punto flotante.Hecho tanto por la velocidad y la ampliación de las magnitudes de los valores que son comprobables.He utilizado se establece en lugar de la lista, porque se tarda mucho menos tiempo, he usado poco turnos en lugar de la división por dos, y yo elegantemente eligió un arranque inicial del valor de manera mucho más eficiente.
Por cierto, hice la prueba de Alex Martelli recomendado por el número de la prueba, así como un par de números de muchos órdenes de magnitud más grandes, tales como:
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
impreso los siguientes resultados:
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
Y esto lo hizo en el 0,33 segundos.
En mi opinión, mi algoritmo funciona de la misma como Alex Martelli, con todos los beneficios de la misma, pero tiene el beneficio añadido altamente eficiente, simple prueba de rechazos que ahorrar un montón de tiempo, por no hablar de la reducción del tamaño de los números de prueba por parte de potencias de 4, lo que mejora la velocidad, la eficiencia, la precisión y el tamaño de los números que son comprobables.Probablemente especialmente cierto en la no-implementaciones de Python.
Aproximadamente el 99% de todos los números enteros son rechazadas como no-Plaza antes de que Babilonia raíz de la extracción está aún implementado, y en 2/3 del tiempo que tardaría el Babilónico para rechazar el entero.Y a pesar de que estas pruebas no acelerar el proceso que de manera significativa, la reducción en todos los números de prueba a un extraño dividiendo a cabo todos los poderes de 4 realmente acelera el Babilónico de la prueba.
Hice una comparación de tiempo de prueba.He probado todos los números enteros de 1 a 10 Millones en la sucesión.Usando el método Babilónico por sí mismo (con mi especialmente a la medida de estimación inicial) se llevó a mi Superficie de 3 con un promedio de 165 segundos (con 100% de exactitud).Utilizando sólo la lógica de las pruebas en mi algoritmo (excepto el de Babilonia), se llevó a 127 segundos, se rechaza el 99% de todos los números enteros como no-Plaza sin erróneamente rechazo de los cuadrados perfectos.De los enteros que pasó, sólo el 3% eran Cuadrados perfectos (a una densidad mucho mayor).Usando todo el algoritmo anterior que emplea tanto la lógica de las pruebas y el Babilónico raíz de la extracción, tenemos un 100% de precisión, y la finalización de la prueba en sólo 14 segundos.Los primeros 100 Millones de números enteros tarda cerca de 2 minutos 45 segundos para la prueba.
EDITAR:He sido capaz de acabar con el tiempo de más.Ahora puedo probar los enteros de 0 a 100 Millones en 1 minuto 40 segundos.Una gran cantidad de tiempo que se desperdicia comprobar el tipo de datos y la positividad.Eliminar los primeros dos cheques y me corté el experimento por un minuto.Uno debe asumir que el usuario es lo suficientemente inteligente como para saber que los negativos y los flotadores no son cuadrados perfectos.
Esto se puede solucionar utilizando el módulo decimal para obtener precisión arbitraria raíces cuadradas y controles fáciles para "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 los 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, lo que finalmente consigue bastante lento (tarda cerca de un segundo para una plaza de 200.000 bits), pero para los números más moderados (por ejemplo, 20.000 bits), todavía es más rápido que un ser humano se daría cuenta de valores individuales (~ 33 ms en mi máquina). Pero dado que 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 de usar gmpy2 y la prueba simplemente gmpy2.mpz(x).is_square(), pero si paquetes de terceros no es lo suyo, lo anterior funciona bastante bien.
Me acaba de publicar una ligera variación en algunos de los ejemplos anteriores en otro hilo ( Encontrar cuadrados perfectos ) y pensé en incluir una ligera variación de lo que he publicado aquí existe (utilizando nsqrt como una variable temporal), en caso de que sea de interés / uso:
import math
def is_square(n):
if not (isinstance(n, int) and (n >= 0)):
return False
else:
nsqrt = math.sqrt(n)
return nsqrt == math.trunc(nsqrt)
Es incorrecto para un gran no cuadrada como 152415789666209426002111556165263283035677490.
Mi respuesta es:
def is_square(x):
return x**.5 % 1 == 0
Básicamente hace una raíz cuadrada, entonces modulo por 1 para despojar a la parte entera y si el resultado es 0 retorno True de otro modo volver 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 pitón puede manejar: 1.7976931348623157e + 308
Es incorrecto para un gran no cuadrada como 152415789666209426002111556165263283035677490.
Este es mi método:
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
Tome raíz cuadrada del número. Convertir a entero. Tomar la plaza. Si los números son iguales, entonces es un cuadrado perfecto de lo contrario no.
Es incorrecto para una gran plaza como 152415789666209426002111556165263283035677489.
Se podría binaria de búsqueda de la raíz cuadrada redondeada. Cuadrado el resultado para ver si coincide con el valor original.
Usted es probablemente mejor con FogleBirds responder - a pesar de tener cuidado, ya que la aritmética de punto flotante es aproximada, que puede lanzar este enfoque fuera. Se podría, en principio, obtener un falso positivo de un gran número entero que es uno más que un cuadrado perfecto, por ejemplo, gracias a la precisión perdido.
- Decidir cuánto tiempo el número de teléfono.
- tomar un delta 0.000000000000.......000001
- a ver si el (sqrt(x))^2 - x es mayor / igual /menor que delta y decidir, basándose en el delta del error.
Esta respuesta no se refiere a su pregunta indicada, sino a una pregunta implícita que veo en el código que envió, es decir, "cómo comprobar si algo es un entero?"
La primera respuesta que generalmente obtendrá a esa pregunta es "No!" Y es cierto que en Python, verificación de tipos por lo general no es lo que hay que hacer.
En las raras excepciones, sin embargo, en lugar de buscar un punto decimal en la representación de cadena del número, lo que hay que hacer es usar el isinstance función:
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Por supuesto, esto se aplica a la variable en lugar de un valor. Si quería determinar si el valor fue un entero, me gustaría hacer esto:
>>> x=5.0
>>> round(x) == x
True
Sin embargo, como todo el mundo ha cubierto en detalle, hay cuestiones de punto flotante a tener en cuenta en la mayoría de ejemplos no juguete de este tipo de cosas.
Si desea bucle sobre una gama y hacer algo para cada número que no es un cuadrado perfecto, se 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 usted quiere 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))
Creo que esto funciona y es muy simple:
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
Es incorrecto para un gran no cuadrada como 152415789666209426002111556165263283035677490.
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
falla por una gran no cuadrada como 152415789666209426002111556165263283035677490.
