Square Root (Integer)

Q: Quelle est la complexité temporelle de la recherche dichotomique de la racine carrée ?

Un temps de O(log x) et un espace de O(1) . Chaque étape divise par deux l’intervalle des candidats, donc x = 2^31 - 1 nécessite 31 étapes. Compter à partir de 0 nécessite O(√x) étapes, soit 46340 pour le même x , ce qui convient ici, mais augmente rapidement avec des entrées sur 64 bits.

Q: Comment la méthode de Newton calcule-t-elle une racine carrée entière ?

Commencez avec r = x . Tant que r × r > x , remplacez r par (r + x / r) / 2 en utilisant la division entière. À chaque étape, r se rapproche de la racine par valeurs décroissantes sans la dépasser, et la boucle s’arrête à la partie entière de la racine carrée. Pour x = 2^31 - 1 , il faut 19 étapes, et le nombre de chiffres exacts double approximativement à chaque étape une fois qu’il s’en rapproche.

FacileRecherche binaire Maths et simulation

+10

Votre fonction reçoit un entier non négatif x et renvoie sa racine carrée entière : le plus grand entier r tel que r × r ≤ x. Il s’agit de la racine carrée arrondie à l’entier inférieur ; ainsi, pour un nombre qui n’est pas un carré parfait, on obtient la racine du carré parfait inférieur. Calculez-la vous-même, sans utiliser de fonction intégrée de racine carrée ni de puissance.

Fonction

mySqrt(x: integer) → integer

xinteger: l’entier non négatif dont il faut extraire la racine carrée
Renvoieinteger: la racine carrée de x arrondie à l’entier inférieur

Contraintes

0 ≤ x ≤ 2³¹ - 1
Ne faites pas appel à une fonction intégrée de racine carrée, de puissance ou d’exponentiation.

Exemples

Entrée: x = 17
Sortie: 4
Explication: 4 × 4 = 16 est inférieur ou égal à 17, mais 5 × 5 = 25 est supérieur, donc la racine de 17 est arrondie à l’entier inférieur, soit 4.

Entrée: x = 49
Sortie: 7
Explication: 49 est un carré parfait, 7 × 7 = 49, donc rien n’est arrondi et la réponse est exactement 7.

+17 tests cachés à la soumission

Pour aller plus loin

Comment trouver plutôt la racine cubique entière, le plus grand r tel que r × r × r ≤ x, si x pouvait aussi être négatif ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Compter à partir de 0 jusqu’à ce que le carré suivant dépasse x donne la bonne réponse, mais cela prend une étape par unité de la racine, soit environ 46 000 étapes près de la limite supérieure de la plage. Les carrés 0, 1, 4, 9, 16, etc. sont triés : on peut donc effectuer une recherche binaire pour trouver le dernier candidat dont le carré est inférieur ou égal à x et terminer en environ 31 étapes. Dans les deux cas, le piège est le dépassement de capacité : le carré d’un candidat ne tient pas toujours sur 32 bits.

Comptez à partir de zéro

Intuition

La racine est le plus grand r tel que r × r ≤ x. Commence à r = 0, dont le carré convient toujours, puis continue avec r + 1 tant que le carré du nombre suivant convient encore. La boucle s’arrête au premier r dont le successeur est trop grand, ce qui correspond exactement à la racine. Pour x = 17, les carrés 1, 4, 9 et 16 conviennent, mais pas 25 ; la boucle s’arrête donc à 4.

La boucle s’exécute une fois par unité de la réponse. La réponse maximale ici est 46340 : il faut donc au plus 46340 étapes, ce qui s’exécute rapidement. Cependant, le coût est de O(√x) et augmente avec l’entrée : une valeur x sur 64 bits pourrait nécessiter environ 3 × 10^9 étapes.

Attention à la dernière vérification. Pour x = 2^31 - 1, la boucle élève 46341 au carré pour constater que le résultat est trop grand, et 46341 × 46341 = 2147488281 ne tient pas dans un entier de 32 bits. Effectue le calcul du carré sur 64 bits.

Algorithme

Définissez root = 0.
Tant que (root + 1) × (root + 1) ≤ x, augmentez root de 1.
Renvoyez root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Recherche binaire sur la réponse

Intuition

Aligne les candidats 0, 1, 2, jusqu’à x, et pose à chacun la même question : son carré est-il inférieur ou égal à x ? Les réponses sont oui, oui, oui, puis non pour tous les candidats après la racine, car les carrés ne font qu’augmenter. La racine est le dernier oui. Une suite de oui suivis de non, c’est exactement ce pour quoi la recherche binaire est conçue.

Garde l’intervalle de candidats lo à hi dont le cas n’a pas encore été tranché, en commençant de 0 à x, et une variable best pour le plus grand oui trouvé jusque-là. Teste le milieu mid. Si mid × mid ≤ x, la racine est égale à mid ou supérieure : stocke cette valeur dans best et fais passer lo à mid + 1. Sinon, la racine est plus petite : fais passer hi à mid - 1. Quand l’intervalle est vide, best est la racine.

Suivons x = 17. L’intervalle de 0 à 17 teste 8 (64, trop grand), puis celui de 0 à 7 teste 3 (9, ça convient, best = 3), puis celui de 4 à 7 teste 5 (25, trop grand), puis celui de 4 à 4 teste 4 (16, ça convient, best = 4). L’intervalle est vide et la réponse est 4. À chaque étape, l’intervalle est divisé par deux, donc x = 2^31 - 1 nécessite 31 étapes. Effectue le calcul du carré sur 64 bits : le premier mid est alors 1073741823.

Algorithme

Définissez lo = 0, hi = x et best = 0.
Tant que lo ≤ hi, calculez mid, le milieu de l’intervalle.
Si mid × mid ≤ x (sur 64 bits), définissez best = mid et lo = mid + 1.
Sinon, définissez hi = mid - 1.
Retournez best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Pièges et cas limites

La recherche elle-même est courte ; les bogues se cachent dans l’arithmétique et les cas limites.

Élever au carré sur 32 bits. Pour x = 2147483647, le premier candidat médian est 1073741823, et son carré vaut environ 1.15 × 10^18. Dans un int de 32 bits, le résultat déborde et devient une valeur incorrecte, qui peut même sembler suffisamment petite. Effectuez la multiplication sur 64 bits, ou comparez plutôt m ≤ x / m.
Élever au carré le candidat suivant sur 32 bits dans la boucle de comptage. La racine de 2^31 - 1 est 46340, et la dernière vérification de la boucle élève 46341 au carré, ce qui donne 2147488281, une valeur supérieure à la limite de 32 bits.
Faire dépasser à la borne la limite de 32 bits. Une borne exclusive hi = x + 1 vaut 2147483648 pour le plus grand x, soit un de plus que la limite de 32 bits. Avec hi = x inclusif, lo + hi atteint exactement 2147483647 à la première étape ; cela tient, mais sans aucune marge. Utilisez des index sur 64 bits ou lo + (hi - lo) / 2.
Renvoyer le dernier mid examiné au lieu du dernier qui convenait. Pour x = 17, la recherche se termine après avoir testé 5, qui est trop grand ; la réponse est le 4 mémorisé.
Briser les petits cas. Une recherche qui commence à lo = 1 ne prend pas en compte x = 0, et la vérification par division m ≤ x / m entraîne une division par zéro lorsque m = 0. Traitez séparément 0 et 1.

Questions fréquentes4

Comment trouver une racine carrée sans fonction intégrée ?

Pour calculer la racine carrée entière, effectuez une recherche dichotomique. Les candidats de 0 à x se répartissent en une suite dont les carrés sont inférieurs ou égaux à x et une suite dont les carrés sont supérieurs ; la recherche dichotomique trouve le dernier candidat de la première suite. La méthode de Newton est l'autre solution courante : elle affine une estimation r avec (r + x / r) / 2 jusqu'à ce que son carré convienne.

Quelle est la complexité temporelle de la recherche dichotomique de la racine carrée ?

Un temps de O(log x) et un espace de O(1). Chaque étape divise par deux l’intervalle des candidats, donc x = 2^31 - 1 nécessite 31 étapes. Compter à partir de 0 nécessite O(√x) étapes, soit 46340 pour le même x, ce qui convient ici, mais augmente rapidement avec des entrées sur 64 bits.

Comment la méthode de Newton calcule-t-elle une racine carrée entière ?

Commencez avec r = x. Tant que r × r > x, remplacez r par (r + x / r) / 2 en utilisant la division entière. À chaque étape, r se rapproche de la racine par valeurs décroissantes sans la dépasser, et la boucle s’arrête à la partie entière de la racine carrée. Pour x = 2^31 - 1, il faut 19 étapes, et le nombre de chiffres exacts double approximativement à chaque étape une fois qu’il s’en rapproche.

Pourquoi la solution a-t-elle besoin d’entiers de 64 bits alors que la réponse tient sur 32 bits ?

La réponse est au plus égale à 46340, mais les valeurs candidates que tu testes ne le sont pas. Une recherche binaire entre 0 et x essaie d’abord une valeur candidate proche de 10^9, dont le carré est proche de 10^18, bien au-delà de la limite 32 bits d’environ 2.1 × 10^9. Calculer le carré sur 64 bits permet de garder une comparaison exacte. Comparer m ≤ x / m évite complètement le grand produit.

Python

def mySqrt(x):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

x = 17

Attendu