Comment pouvons-nous déterminer efficacement si un nombre est un carré parfait à l'aide de nombres entiers ?

Approche efficace basée sur les nombres entiers pour identifier les carrés parfaits

Pour déterminer si un nombre constitue un carré parfait, on peut se passer de l'utilisation de calculs à virgule flottante comme math.sqrt(x) ou x**0.5. Ces approches peuvent introduire des inexactitudes, en particulier pour les entiers de grande taille. Considérez plutôt la méthode basée sur les nombres entiers ci-dessous :

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

Cet algorithme exploite « l'algorithme babylonien » pour calculer les racines carrées. Il calcule de manière itérative la moyenne de x et apositiveint//x pour se rapprocher progressivement de la racine carrée de apositiveint. L'inclusion de l'ensemble vu évite d'éventuelles boucles infinies tout en assurant la convergence de la solution.

Pour illustrer l'efficacité de cette méthode, considérons l'exemple suivant :

for i in range(110, 130):
   print i, is_square(i)

Sortie :

110 True
111 False
112 True
113 False
114 True
115 False
116 True
117 False
118 True
119 False
120 True
121 False
122 True
123 False
124 True
125 False
126 True
127 False
128 True
129 False

À titre de démonstration supplémentaire, nous pouvons appliquer l'algorithme à des entiers :

x = 12345678987654321234567 ** 2

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

Sortie :

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

Bien que les calculs à virgule flottante soient pratiques, ils peuvent introduire des inexactitudes qui peuvent ne pas être immédiatement évidentes. Pour obtenir des résultats précis, les approches basées sur les nombres entiers comme l'algorithme babylonien fournissent une solution plus fiable et plus efficace pour vérifier si un nombre est qualifié de carré parfait.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!