Verifique se um número é um quadrado perfeito
https://stackoverflow.com/questions/2489435
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como eu poderia verificar se um número é um quadrado perfeito?
A velocidade não é preocupante, por enquanto, apenas trabalhando.
Solução
O problema de confiar em qualquer computação de ponto flutuante (math.sqrt(x), ou x**0.5) é que você não pode realmente ter certeza de que é exato (para números inteiros suficientemente grandes x, não será e pode até transbordar). Felizmente (se não tiver pressa ;-) Existem muitas abordagens inteiras puras, como as seguintes ...:
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)
Dica: é baseado no "algoritmo babilônico" para raiz quadrada, veja Wikipedia. Isto faz Trabalhe para qualquer número positivo para o qual você tenha memória suficiente para que o cálculo prossiga para a conclusão ;-).
Editar: Vamos ver um exemplo ...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)
Isso imprime, conforme desejado (e em uma quantidade razoável de tempo também ;-):
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False
Antes de propor soluções com base em resultados intermediários de ponto flutuante, verifique se eles funcionam corretamente neste exemplo simples - não é este Hard (você só precisa de algumas verificações extras, caso o SQRT calculado seja um pouco desligado), apenas tome um pouco de cuidado.
E então tente com x**7 e encontre uma maneira inteligente de contornar o problema que você terá,
OverflowError: long int too large to convert to float
Você terá que ficar cada vez mais inteligente à medida que os números continuam crescendo, é claro.
Se eu foi com pressa, é claro, eu usaria GMPY -Mas então, estou claramente tendencioso ;-).
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0
Sim, eu sei, isso é tão fácil que parece trapacear (um pouco do jeito que eu sinto em relação ao python em geral ;-)-sem esperteza, apenas direção e simplicidade perfeitas (e, no caso de GMPY, velocidade pura ;-) ...
Outras dicas
Use o método de Newton para se concentrar rapidamente na raiz quadrada inteira mais próxima e depois enquadrá -la e ver se é o seu número. Ver isqrt.
Python ≥ 3,8 tem math.isqrt. Se estiver usando uma versão mais antiga do Python, procure o "def isqrt(n)"Implementação aqui.
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2
Como você nunca pode depender de comparações exatas ao lidar com cálculos de ponto flutuante (como essas maneiras de calcular a raiz quadrada), uma implementação menos propensa a erros seria
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2
Imagine integer é 9. math.sqrt(9) poderia ser 3.0, mas também pode ser algo como 2.99999 ou 3.00001, então quadrilha o resultado logo não é confiável. Sabendo que int leva o valor do piso, aumentando o valor da flutuação por 0.5 Primeiro significa que teremos o valor que estamos procurando se estamos em uma faixa onde float Ainda tem uma resolução fina o suficiente para representar números próximos daquele para o qual estamos procurando.
import math
def is_square(n):
sqrt = math.sqrt(n)
return (sqrt - int(sqrt)) == 0
Um quadrado perfeito é um número que pode ser expresso como o produto de dois números inteiros iguais. math.sqrt(number) retornar a float. int(math.sqrt(number)) lança o resultado para int.
Se a raiz quadrada é um número inteiro, como 3, por exemplo, então math.sqrt(number) - int(math.sqrt(number)) será 0, e o if declaração será False. Se a raiz quadrada era um número real como 3,2, então será True e imprimir "Não é um quadrado perfeito".
Falha para Um grande não quadrado como 152415789666209426002111556165263283035677490.
Se você estiver interessado, tenho uma resposta pura a uma pergunta semelhante em Math Stackexchange, "Detectando quadrados perfeitos mais rápido do que extraindo raiz quadrada".
Minha própria implementação do ISSQUARE (n) pode não ser a melhor, mas eu gosto. Levei vários meses de estudo sobre teoria matemática, computação digital e programação Python, comparando -me a outros colaboradores, etc., para realmente clicar com esse método. Eu gosto de sua simplicidade e eficiência. Eu não vi melhor. Me diga o que você acha.
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
Bem direto. Primeiro, verifica se temos um número inteiro e positivo nisso. Caso contrário, não há sentido. Permite que 0 deslize como verdadeiro (necessário ou o próximo bloco é infinito loop).
O próximo bloco de código remove sistematicamente os poderes de 4 em um sub-algoritmo muito rápido usando operações de mudança de bits e bits. Em última análise, não estamos encontrando o ISSQUARE do nosso N original, mas de AK
O terceiro bloco de código executa um teste bit-lógico booleano simples. Os três dígitos menos significativos, em binário, de qualquer quadrado perfeito, são 001. Sempre. Exceto para os zeros líderes resultantes de poderes de 4, de qualquer maneira, o que já foi contabilizado. Se falhar no teste, você sabe imediatamente que não é um quadrado. Se passar, você não pode ter certeza.
Além disso, se acabarmos com 1 para um valor de teste, o número do teste foi originalmente uma potência de 4, incluindo talvez 1.
Assim como o terceiro bloco, o quarto teste do local em decimal usando o operador simples do módulo e tende a capturar valores que deslizam pelo teste anterior. Também um teste MOD 7, MOD 8, MOD 9 e MOD 13.
O quinto bloco de código verifica alguns dos conhecidos padrões quadrados perfeitos. Os números que terminam em 1 ou 9 são precedidos por um múltiplo de quatro. E os números que terminam em 5 devem terminar em 5625, 0625, 225 ou 025. Eu incluí outros, mas percebi que eles eram redundantes ou nunca foram realmente usados.
Por fim, o sexto bloco de código se assemelha muito ao que é o principal resposta - Alex Martelli - a resposta é. Basicamente, encontra a raiz quadrada usando o antigo algoritmo babilônico, mas restringindo -o a valores inteiros enquanto ignora o ponto flutuante. Feito tanto para velocidade quanto estendendo as magnitudes dos valores testáveis. Usei conjuntos em vez de listas porque leva muito menos tempo, usei turnos de bits em vez de divisão por dois, e escolhi de maneira inteligente um valor inicial de início com muito mais eficiência.
A propósito, testei o número de teste recomendado por Alex Martelli, bem como alguns números de muitos pedidos de magnitude maior, como:
x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
print(i, isSquare(i))
Imprimiu os seguintes resultados:
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False
E fez isso em 0,33 segundos.
Na minha opinião, meu algoritmo funciona da mesma forma que o de Alex Martelli, com todos os seus benefícios, mas tem o benefício adicional de rejeições de teste simples altamente eficiente que economizam muito tempo, sem mencionar a redução no tamanho dos números de teste por poderes de poderes de 4, o que melhora a velocidade, a eficiência, a precisão e o tamanho dos números testáveis. Provavelmente especialmente verdadeiro em implementações não python.
Aproximadamente 99% de todos os números inteiros são rejeitados como não quadrados antes que a extração da raiz da Babilônia seja implementada e, em 2/3, o tempo que o Babilônico levaria para rejeitar o número inteiro. E embora esses testes não acelerem o processo tão significativamente, a redução em todos os números de teste para um ímpar dividindo todos os poderes de 4 verdade acelera o teste da Babilônia.
Eu fiz um teste de comparação de tempo. Testei todos os números inteiros de 1 a 10 milhões em sucessão. Usando apenas o método babilônico por si só (com meu palpite inicial especialmente adaptado), minha superfície levou 3 uma média de 165 segundos (com 100% de precisão). Usando apenas os testes lógicos no meu algoritmo (excluindo o Babilônico), levou 127 segundos, ele rejeitou 99% de todos os números inteiros como não quadrados sem rejeitar equivocados a quadrados perfeitos. Dos números inteiros que passaram, apenas 3% eram quadrados perfeitos (uma densidade muito maior). Usando o algoritmo completo acima que emprega os testes lógicos e a extração da raiz da Babilônia, temos 100% de precisão e a conclusão do teste em apenas 14 segundos. Os primeiros 100 milhões de números inteiros levam aproximadamente 2 minutos 45 segundos para testar.
EDIT: Consegui reduzir o tempo. Agora posso testar os números inteiros de 0 a 100 milhões em 1 minuto 40 segundos. Muito tempo é desperdiçado verificando o tipo de dados e a positividade. Elimine os dois primeiros cheques e eu reduzi o experimento em um minuto. É preciso assumir que o usuário é inteligente o suficiente para saber que negativos e carros alegóricos não são quadrados perfeitos.
Isso pode ser resolvido usando a decimal módulo Para obter raízes quadradas de precisão arbitrária e verificações fáceis de "exatidão":
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 demonstração com valores verdadeiramente 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
Se você aumentar o tamanho do valor que está sendo testado, isso acaba sendo bastante lento (leva quase um segundo para um quadrado de 200.000 bits), mas para números mais moderados (por exemplo, 20.000 bits), ainda é mais rápido que um humano notaria para valores individuais (~ 33 ms na minha máquina). Mas como a velocidade não foi sua principal preocupação, essa é uma boa maneira de fazê -lo com as bibliotecas padrão do Python.
Claro, seria muito mais rápido usar gmpy2 e apenas teste gmpy2.mpz(x).is_square(), mas se os pacotes de terceiros não são o que você gosta, o exposto funciona muito bem.
Acabei de publicar uma ligeira variação em alguns dos exemplos acima em outro tópico (Encontrando quadrados perfeitos) e pensei em incluir uma ligeira variação do que publiquei aqui (usando o NSQRT como uma variável temporária), caso seja de interesse / 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)
Está incorreto Para um grande não quadrado como 152415789666209426002111556165263283035677490.
Minha resposta é:
def is_square(x):
return x**.5 % 1 == 0
Basicamente True Caso contrário, retorne False. Nesse caso, x pode ser um número grande, apenas não tão grande quanto o número de flutuação máxima que o Python pode lidar: 1.7976931348623157e+308
Está incorreto Para um grande não quadrado como 152415789666209426002111556165263283035677490.
Este é o meu método:
def is_square(n) -> bool:
return int(n**0.5)**2 == int(n)
Pegue a raiz quadrada do número. Converter para inteiro. Pegue o quadrado. Se os números forem iguais, é um quadrado perfeito, caso contrário, não.
Está incorreto Para um quadrado grande como 1524157896662094260021115561652632830356777489.
Você pode pesquisar binários para a raiz quadrada arredondada. Quadrado o resultado para ver se ele corresponde ao valor original.
Você provavelmente está melhor com a resposta do Foglebirds - embora tenha cuidado, pois a aritmética do ponto flutuante é aproximado, o que pode desligar essa abordagem. Você pode, em princípio, obter um falso positivo de um número inteiro grande, que é um mais que um quadrado perfeito, por exemplo, devido à perda de precisão.
- Decida quanto tempo o número será.
- Pegue um Delta 0.000000000000 ....... 000001
- Veja se o (sqrt (x))^2 - x é maior / igual / menor que o delta e decida com base no erro delta.
Essa resposta não se refere à sua pergunta declarada, mas a uma pergunta implícita que vejo no código que você postou, ou seja, "Como verificar se algo é um número inteiro?"
A primeira resposta que você geralmente chega a essa pergunta é "Não!" E é verdade que, no Python, o TypeCecking geralmente não é a coisa certa a fazer.
Para essas raras exceções, porém, em vez de procurar um ponto decimal na representação da string do número, a coisa a fazer é usar o isinstance função:
>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False
Obviamente, isso se aplica à variável e não ao valor. Se eu queria determinar se o valor Era um número inteiro, eu faria isso:
>>> x=5.0
>>> round(x) == x
True
Mas, como todos os outros abordaram detalhadamente, há questões de ponto flutuante a serem consideradas na maioria dos exemplos não-tojas desse tipo de coisa.
Se você deseja fazer um loop em um intervalo e fazer algo para cada número que não é um quadrado perfeito, você pode fazer algo assim:
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
Se você quiser fazer algo para cada número que seja um quadrado perfeito, o gerador é ainda mais fácil:
(n * n for n in range(upper))
Eu acho que isso funciona e é muito simples:
import math
def is_square(num):
sqrt = math.sqrt(num)
return sqrt == int(sqrt)
Está incorreto Para um grande não quadrado como 152415789666209426002111556165263283035677490.
import math
def is_square(n):
sqrt = math.sqrt(n)
return sqrt == int(sqrt)
Falha para Um grande não quadrado como 152415789666209426002111556165263283035677490.
