Vérifiez si un nombre est un carré parfait

Question

Comment puis-je vérifier si un nombre est un carré parfait ?

La vitesse n'est pas un problème, pour l'instant, il suffit de travailler.

Answer 1

Le problème se fondant sur tout calcul en virgule flottante (math.sqrt(x) ou x**0.5) est que vous ne pouvez pas vraiment être sûr qu'il est exact (pour les entiers suffisamment grands x, il ne sera pas, et pourrait même déborder). Heureusement (si l'on est pas pressé ;-) il y a de nombreuses approches entières pures, telles que les suivantes ...:

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)

Astuce: il est basé sur le « algorithme de Babylone » pour la racine carrée, consultez wikipedia. Il fait travail pour un nombre positif pour lequel vous avez assez de mémoire pour le calcul de procéder à la réalisation, -.)

Modifier : nous allons voir un exemple ...

x = 12345678987654321234567 ** 2

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

imprime, comme vous le souhaitez (et dans un laps de temps raisonnable, aussi; -):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

S'il vous plaît, avant de proposer des solutions basées sur virgule flottante des résultats intermédiaires, assurez-vous qu'ils fonctionnent correctement sur cet exemple simple - ce n'est pas dur (vous avez juste besoin de quelques contrôles supplémentaires en cas sqrt calculée est un peu hors), prend juste un peu de soins.

Et puis essayez avec x**7 et trouver moyen intelligent de contourner le problème que vous aurez,

OverflowError: long int too large to convert to float

vous devrez obtenir de plus en plus intelligent que les chiffres ne cessent d'augmenter, bien sûr.

Si I n'a pressé, bien sûr, j'utiliser gmpy - mais alors, je suis clairement partial; -).

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

Ouais, je sais, c'est tellement facile qu'il se sent comme de la tricherie (un peu la façon dont je me sens vers Python en général ;-) - pas du tout intelligence, juste parfait et la simplicité immédiateté (et, dans le cas de gmpy , la vitesse pure; -) ...

Answer 2

La méthode de Newton Utilisez rapidement zéro sur la racine carrée le plus proche entier, carré alors et voir si elle est votre numéro. Voir isqrt .

Python ≥ 3.8 a math.isqrt . Si vous utilisez une ancienne version de Python, recherchez le « def isqrt(n) » la mise en œuvre ici .

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

Answer 3

Puisque vous ne pouvez jamais compter sur des comparaisons exactes lorsqu'ils traitent avec des calculs à virgule flottante (comme ces moyens de calcul de la racine carrée), une mise en œuvre moins sujette aux erreurs serait

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

Imaginez 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 bon résultat de n'est pas fiable. Sachant que int prend la valeur plancher, ce qui augmente la valeur du flotteur par 0.5 signifie d'abord nous allons obtenir la valeur que nous recherchons si nous sommes dans une plage où float a encore une résolution assez fine pour représenter des nombres près de celui pour lequel nous sommes à la recherche.

Answer 4

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return (sqrt - int(sqrt)) == 0

Un carré parfait est un nombre qui peut être exprimé en tant que produit de deux nombres entiers égaux. math.sqrt(number) retourner un float. int(math.sqrt(number)) jette 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 de 0, et la déclaration de if sera False. Si la racine carrée est un nombre réel comme 3.2, il sera True et imprimer « ce n'est pas un carré parfait ».

Il échoue pour un grand tel non carré comme 152415789666209426002111556165263283035677490.

Answer 5

Si vous êtes intéressé, j'ai une réponse mathématique pure à une question similaire à StackExchange math, « la détection des carrés parfaits plus rapidement que par l'extraction de racine carrée » .

Mon propre implémentation de isSquare (n) peut ne pas être le meilleur, mais je l'aime. Il m'a fallu plusieurs mois d'études en théorie des mathématiques, calcul numérique et la programmation de python, de me comparer à d'autres contributeurs, etc., cliquer vraiment avec cette méthode. J'aime sa simplicité et son efficacité bien. Je nai vu mieux. Dites-moi ce que vous 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 à ce sujet. Sinon, il n'y a pas de point. Il laisse 0 par glissement comme True (nécessaire ou autre bloc suivant est boucle infinie).

Le bloc de code suivant supprime systématiquement les pouvoirs de 4 dans un sous-algorithme très rapide en utilisant des opérations logiques de décalage et le bit de bits. Nous ne constatons pas en fin de compte la isSquare de notre origine, mais n d'un k

Le troisième bloc de code effectue un test simple logique binaire de Boole. Les moins trois chiffres significatifs, en binaire, d'un carré parfait sont 001. toujours. Sauf pour des zéros non significatifs résultant de pouvoirs de 4, de toute façon, qui a déjà été pris en compte. Si elle échoue le test, vous savez immédiatement nest pas un carré. Si elle passe, vous ne pouvez pas être sûr.

De plus, si nous nous retrouvons avec un 1 pour une valeur de test, puis le numéro de test était à l'origine une puissance de 4, y compris peut-être lui-même 1.

Comme le troisième bloc, la quatrième teste la valeur les place en décimal utilisant l'opérateur de module simple, et tend à attraper des valeurs qui se glissent dans l'essai précédent. Aussi un mod 7, 8 mod, mod 9 et mod test 13.

Le cinquième bloc de contrôle de code pour certains des modèles parfaits carrés bien connus. Les nombres se terminant par 1 ou 9 sont précédés d'un multiple de quatre. Et les numéros se terminant par 5 doivent se terminer par 5625, 0625, 225 ou 025. Je l'avais compris, mais d'autres ont réalisé qu'ils étaient licenciés ou jamais réellement utilisé.

Enfin, le sixième bloc de code ressemble beaucoup à ce que le haut answerer - Alex Martelli - réponse. Fondamentalement trouve la racine carrée en utilisant l'ancien algorithme de Babylone, mais en limitant à des valeurs entières tout en ignorant à virgule flottante. Fait à la fois pour la vitesse et l'extension des grandeurs des valeurs qui sont testables. J'ai utilisé à la place des ensembles de listes, car il faut beaucoup moins de temps, je décalages de bits au lieu de la division par deux, et je intelligemment choisi une valeur initiale de départ beaucoup plus efficacement.

Par ailleurs, je l'ai fait tester le numéro de test Alex Martelli recommandé, ainsi que quelques chiffres beaucoup d'importance commandes supérieures, telles que:

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

imprimer les résultats suivants:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

Et il l'a fait en 0,33 secondes.

A mon avis, mon algorithme fonctionne comme le Alex Martelli, avec tous les avantages de celui-ci, mais a l'avantage des rejets-tests simples très efficaces qui permettent d'économiser beaucoup de temps, sans parler de la réduction de la taille des numéros de test par des puissances de 4, ce qui améliore la vitesse, l'efficacité, la précision et la taille des chiffres qui sont testables. Probablement particulièrement vrai dans les implémentations non-Python.

sont rejetés Environ 99% de tous les entiers comme non-place avant l'extraction de la racine de Babylone est même mis en œuvre, et en 2/3 le temps qu'il prendrait la Babylone de rejeter l'entier. Et bien que ces tests DonT accélérer le processus 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 de Babylone.

Je l'ai fait un test de comparaison de temps. Je l'ai testé tous les entiers de 1 à 10 millions successivement. En utilisant simplement la méthode de Babylone par lui-même (avec mon estimation initiale spécialement sur mesure), il a pris ma surface 3 en moyenne de 165 secondes (avec une précision de 100%). En utilisant seulement les tests logiques dans mon algorithme (hors de Babylone), il a fallu 127 secondes, il a rejeté comme non-place 99% de tous les entiers sans rejeter par erreur des carrés parfaits. Parmi les entiers qui sont passés, 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 babylonien, nous avons une précision de 100%, et l'achèvement de test en seulement 14 secondes. Les 100 premiers millions entiers prend environ 2 minutes 45 secondes à tester.

EDIT: Je suis en mesure de faire baisser le plus de temps. Je peux maintenant tester les nombres entiers de 0 à 100 millions en 1 minute 40 secondes. Beaucoup de temps est gaspillé vérifier le type de données et la positivité. Éliminer les premiers deux contrôles et je coupe l'expérience par une minute. Il faut supposer que l'utilisateur est assez intelligent pour savoir que les négatifs et les flotteurs ne sont pas des carrés parfaits.

Answer 6

Ceci peut être résolu en utilisant le module decimal pour obtenir une précision arbitraire des racines carrées et des contrôles faciles pour « précision »:

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 la 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 devient finalement assez lent (prend près d'une seconde pour un carré de 200.000 bits), mais pour des chiffres plus modérés (disons, 20000 bits), il est encore plus rapide qu'un humain remarquerait des valeurs individuelles (33 ~ ms sur ma machine). Mais puisque la vitesse n'a pas été votre principale préoccupation, c'est une bonne façon de le faire avec les bibliothèques standard de Python.

Bien sûr, il serait beaucoup plus rapide à utiliser gmpy2 et juste gmpy2.mpz(x).is_square() test, mais si des logiciels tiers ne sont pas votre truc, les travaux ci-dessus tout à fait bien.

Answer 7

Je viens de publier une légère variation sur certains des exemples ci-dessus sur un autre thread ( Trouver des carrés parfaits ) et pensé que je serais inclus une légère variation de ce que j'y ai posté ici (en utilisant nsqrt comme une variable temporaire), au cas où il est d'intérêt / utilisation:

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)

Il est incorrect pour une grande non carrée tels que 152415789666209426002111556165263283035677490.

Answer 8

Ma réponse est:

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

Il ne fondamentalement une racine carrée, puis modulo par une bande de la partie entière et si le résultat est égal à 0 sinon retour True retour False. Dans ce cas, x peut être un grand nombre, mais pas aussi grand que le nombre de flotteur max que python peut gérer: 1.7976931348623157e + 308

Il est incorrect pour une grande non carrée tels que 152415789666209426002111556165263283035677490.

Answer 9

Ceci est ma méthode:

def is_square(n) -> bool:
    return int(n**0.5)**2 == int(n)

Prendre racine carrée du nombre. Convertir en entier. Prenez la place. Si les chiffres sont égaux, alors il est un carré parfait sinon pas.

Il est incorrect pour une grande place, comme 152415789666209426002111556165263283035677489.

Answer 10

Vous pouvez binaire recherche la racine carrée arrondie. Carré le résultat pour voir si elle correspond à la valeur d'origine.

Vous êtes probablement mieux avec FogleBirds répondre - mais méfiez-vous, comme arithmétique en virgule flottante est approximative, qui peut lancer cette approche hors. Vous pouvez en principe obtenir un faux positif d'un grand entier qui est un plus d'un carré parfait, par exemple, en raison de la précision perdue.

Answer 11

1. Décidez de la durée du numéro.
2. prendre un delta 0,000000000000.......000001
3. voyez si le (sqrt(x))^2 - x est supérieur/égal/plus petit que delta et décidez en fonction de l'erreur delta.

Answer 12

Cette réponse ne concerne pas votre question énoncée, mais à une question implicite que je vois dans le code affiché, à savoir « comment vérifier si quelque chose est un entier? »

La première réponse que vous obtiendrez généralement à cette question est « Ne pas! » Et il est vrai que dans Python, est généralement pas typage la bonne chose à faire.

Pour les rares exceptions près, cependant, au lieu de chercher un point décimal dans la représentation de chaîne du nombre, la chose à faire est d'utiliser isinstance fonction:

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

Bien sûr, cela s'applique à la variable plutôt qu'une valeur. Si je voulais déterminer si le valeur est un entier, je ferais ceci:

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

Mais comme tout le monde a couvert en détail, il y a des questions à virgule flottante à considérer dans la plupart des exemples non-jouets de ce genre de chose.

Answer 13

Si vous voulez faire une boucle sur une plage et faire quelque chose pour chaque numéro qui est pas un carré parfait, vous pourriez faire quelque chose comme ceci:

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 vous voulez faire quelque chose pour chaque numéro qui est un carré parfait, le générateur est encore plus facile:

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

Answer 14

Je pense que cela fonctionne et est très simple:

import math

def is_square(num):
    sqrt = math.sqrt(num)
    return sqrt == int(sqrt)

Il est incorrect pour une grande non carrée tels que 152415789666209426002111556165263283035677490.

Answer 15

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return sqrt == int(sqrt)

Il échoue pour un grand tel non carré comme 152415789666209426002111556165263283035677490.