Python: Vérifier si un nombre est un carré parfait

utilisez la méthode de Newton pour rapidement mettre à zéro sur la racine carrée entière la plus proche, puis le carré et voir si c'est votre nombre. Voir isqrt .

comme vous ne pouvez jamais compter sur des comparaisons exactes lors de la gestion de calculs à virgule flottante (comme ces façons de calculer la racine carrée), une implémentation moins sujette aux erreurs serait

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

Imaginer integer est 9 . math.sqrt(9) pourrait être 3.0 , mais il pourrait aussi être quelque chose comme 2.99999 ou 3.00001 , donc la quadrature du résultat tout de suite n'est pas fiable. Sachant que int prend la valeur de plancher, en augmentant la valeur de flottement par 0.5 tout d'abord signifie que nous obtiendrons la valeur que nous recherchons si nous sommes dans une gamme où float a encore une résolution assez fine pour représenter des nombres près de celui pour lequel nous recherchons.

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

Un carré parfait est un nombre qui peut être exprimé comme le produit de deux nombres entiers. math.sqrt(number) retour float . int(math.sqrt(number)) renvoie le résultat à int .

si la racine carrée est un entier, comme 3, par exemple, alors math.sqrt(number) - int(math.sqrt(number)) sera 0, et l'instruction if sera False . Si la racine carrée était un nombre réel comme 3.2, alors il sera True et imprimer"ce n'est pas un carré parfait".

Je suis nouveau à Stack Overflow, et j'ai vite fait de trouver une solution. Je viens de poster une légère variation sur certains des exemples ci-dessus sur un autre fil ( trouver des carrés parfaits ) et j'ai pensé que je voudrais inclure une légère variation de ce que j'ai posté ici (en utilisant nsqrt comme une variable temporaire), au cas où il est d'intérêt / utilisation:

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)

si vous êtes intéressé, j'ai une réponse de mathématiques pures à une question similaire à stackexchange de mathématiques," la détection des carrés parfaits plus vite que par l'extraction de racine carrée " .

ma propre mise en œuvre d'isSquare(n) peut ne pas être la meilleure, mais je l'aime. Cela m'a pris plusieurs mois d'études en théorie mathématique, calcul numérique et programmation python, me comparant à d'autres contributeurs, etc., cliquer sur vraiment avec cette méthode. J'aime sa simplicité et de l'efficacité. Je n'ai pas vu mieux. Dites-moi ce que vous en pensez.

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

assez simple. D'abord, il vérifie que nous avons un nombre entier et positif. Sinon il n'y a pas de point. Il laisse passer 0 comme True (nécessaire ou sinon prochain bloc est boucle infinie).

le bloc de code suivant supprime systématiquement les puissances de 4 dans un sous-algorithme très rapide en utilisant des opérations de décalage de bits et de logique de bits. En définitive, nous ne sommes pas trouver l'isSquare de notre n original mais d'un k

le troisième bloc de code effectue un simple test de logique booléenne. Les trois chiffres les moins significatifs, en binaire, de n'importe quel carré parfait sont 001. Toujours. Sauf pour les zéros de tête résultant de puissances de 4, en tout cas, qui a déjà été pris en compte. S'il échoue le test, vous savez immédiatement qu'il n'est pas un carré. Si ça passe, tu ne peux pas en être sûr.

aussi, si nous nous retrouvons avec un 1 pour une valeur d'essai alors le nombre d'essai était à l'origine une puissance de 4, y compris peut-être 1 lui-même.

comme le troisième bloc, le quatrième teste la valeur à une place en décimale en utilisant l'opérateur de module simple, et tend à saisir les valeurs qui glissent à travers le test précédent. Aussi un mod 7, mod 8, mod 9, et mod 13 test.

le cinquième bloc de code vérifie pour certains des motifs carrés parfaits bien connus. Les nombres se terminant par 1 ou 9 sont précédés d'un multiple de quatre. Et les nombres se terminant par 5 doivent se terminer par 5625, 0625, 225, ou 025. J'en avais inclus d'autres, mais j'ai réalisé qu'ils étaient redondants ou qu'ils n'étaient jamais utilisés.

enfin, le sixième bloc de code ressemble beaucoup à ce que le meilleur répondeur - Alex Martelli - réponse est. Essentiellement trouve la racine carrée en utilisant l'ancien Algorithme babylonien, mais en le limitant à des valeurs entières tout en ignorant la virgule flottante. Fait à la fois pour la vitesse et l'extension de l'amplitude des valeurs qui sont testables. J'ai utilisé des ensembles au lieu de listes parce que cela prend beaucoup moins de temps, j'ai utilisé des changements de bits au lieu de division par deux, et j'ai choisi intelligemment une valeur initiale de départ beaucoup plus efficacement.

soit dit en passant, j'ai testé le numéro de test recommandé par Alex Martelli, ainsi que quelques numéros beaucoup d'ordres de grandeur plus grands, tels que:

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

a imprimé les résultats suivants:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

et il l'a fait en 0.33 secondes.

à mon avis, Mon algorithme fonctionne de la même façon que celui D'Alex Martelli, avec tous les avantages que cela comporte, mais il a l'avantage supplémentaire des rejets de tests simples très efficaces qui économisent beaucoup de temps, sans parler de la réduction de la taille des nombres de test par des puissances de 4, ce qui améliore la vitesse, l'efficacité, la précision et la taille des nombres qui sont testables. Probablement particulièrement vrai dans les implémentations non-Python.

environ 99% de tous les entiers sont rejetés comme non-carrés avant extraction de racine babylonienne est même mis en œuvre, et dans 2/3 le temps, il faudrait le babylonien pour rejeter l'entier. Et bien que ces tests n'accélèrent pas le processus que de manière significative, la réduction de tous les numéros de test à un Impair en divisant toutes les puissances de 4 vraiment accélère le test babylonien.

j'ai fait un test de comparaison de temps. J'ai testé tous les entiers de 1 à 10 millions en succession. En utilisant seulement la méthode babylonienne par elle-même (avec ma supposition initiale spécialement conçue) il a fallu à ma Surface 3 une moyenne de 165 secondes (avec une précision de 100%). En utilisant seulement les tests logiques dans mon algorithme (excluant le babylonien), il a pris 127 secondes, il a rejeté 99% de tous les entiers comme non-carré sans rejeter par erreur tous les carrés parfaits. De ces entiers qui passait, seulement 3% étaient des carrés parfaits (une densité beaucoup plus élevée). En utilisant l'algorithme complet ci-dessus qui utilise à la fois les tests logiques et l'extraction des racines babyloniennes, nous avons une précision de 100%, et l'achèvement des tests en seulement 14 secondes. Le premier 100 millions d'entiers prend environ 2 minutes 45 secondes pour tester.

EDIT: j'ai été en mesure de ramener le plus de temps. Je peux maintenant tester les entiers 0 à 100 millions en 1 minute 40 secondes. Beaucoup de temps est gaspillé vérifier le type de données et la positivité. Eliminez les deux premiers contrôles et je réduis l'expérience d'une minute. On doit supposer que l'utilisateur est assez intelligent pour savoir que les négatifs et les flotteurs ne sont pas des carrés parfaits.

cela peut être résolu en utilisant le decimal module pour obtenir des racines carrées de précision arbitraire et des vérifications faciles pour "exactitude":

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]

pour démonstration avec des valeurs vraiment énormes:

# 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 vous augmentez la taille de la valeur testée, cela finit par devenir plutôt lent( prend près d'une seconde pour un carré de 200.000 bits), mais pour des nombres plus modérés (disons, 20.000 bits), c'est encore plus rapide que un humain remarquerait pour des valeurs individuelles (~33 ms sur ma machine). Mais puisque la vitesse n'est pas votre principale préoccupation, c'est une bonne façon de le faire avec Python bibliothèques standard.

bien sûr, il serait beaucoup plus rapide d'utiliser gmpy2 et juste tester gmpy2.mpz(x).is_square() , mais si les paquets tiers ne sont pas votre truc, ce qui précède fonctionne très bien.

ma réponse serait:

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

Cela fait essentiellement une racine carrée, puis modulo par 1 pour rayer la partie entière et si le résultat est 0 retourner True sinon retourner False . Dans ce cas, x peut être n'importe quel grand nombre, mais pas aussi grand que le nombre de float max que python peut gérer: 1.7976931348623157 e+308

vous pourriez binaire-recherche de la racine carrée arrondie. Carré le résultat pour voir s'il correspond à la valeur originale.

Vous êtes probablement mieux avec FogleBirds réponse - mais attention, comme l'arithmétique à virgule flottante est approximative, ce qui peut lancer cette approche off. Vous pourriez en principe obtenir un faux positif d'un grand entier qui est un plus qu'un carré parfait, par exemple, en raison de la précision perdue.

C'est ma méthode

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

prendre racine carrée du nombre convertir en entier puis prendre le carré si les nombres sont égaux, alors c'est un carré parfait pas autrement.

1. Décider combien de temps le nombre sera.
2. prenez un delta 0.000000000000.......000001
3. voir si le(sqrt (x))^2 - x est plus grand / égal /plus petit que delta et décider sur la base de l'erreur delta.

cette réponse ne se rapporte pas à votre question énoncée, mais à une question implicite que je vois dans le code que vous avez posté, c'est-à-dire, "comment vérifier si quelque chose est un entier?"

la première réponse que vous obtiendrez généralement à cette question Est "ne le faites pas!"Et c'est vrai qu'en Python, le typage est généralement pas la bonne chose à faire.

pour ces rares exceptions, cependant, au lieu de chercher un point décimal dans la représentation string du nombre, le la chose à faire est d'utiliser le isinstance fonction:

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

cela s'applique évidemment à la variable plutôt qu'à une valeur. Si je voulais déterminer si la valeur était un entier, je le ferais:

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