Comment écrire votre propre fonction pour trouver la racine carrée la plus exacte d'un entier ?
Après avoir cherché sur Google, j'ai trouvé cette (archivé de son lien original ), mais premièrement, je n'ai pas tout compris, et deuxièmement, c'est aussi approximatif.
Supposez que la racine carrée est un entier le plus proche (de la racine réelle) ou un flottant.
La procédure suivante calcule floor(sqrt(N)) pour N > 0 :
x = 2^ceil(numbits(N)/2)
loop:
y = floor((x + floor(N/x))/2)
if y >= x
return x
x = yIl s'agit d'une version de la méthode de Newton présentée dans Crandall & Pomerance, "Prime Numbers : A Computational Perspective". La raison pour laquelle vous devriez utiliser cette version est que les personnes qui savent ce qu'elles font ont prouvé qu'elle converge exactement vers le plancher de la racine carrée, et qu'elle est simple, de sorte que la probabilité de commettre une erreur d'implémentation est faible. Il est également rapide (bien qu'il soit possible de construire un algorithme encore plus rapide - mais le faire correctement est beaucoup plus complexe). Une recherche binaire correctement mise en œuvre peut être plus rapide pour un très petit N, mais dans ce cas, vous pouvez tout aussi bien utiliser une table de recherche.
Pour arrondir à la le plus proche il suffit de calculer t = floor(sqrt(4N)) en utilisant l'algorithme ci-dessus. Si le bit de poids faible de t est défini, choisissez x = (t+1)/2 ; sinon, choisissez t/2. Notez que cette méthode arrondit à l'entier supérieur en cas d'égalité ; vous pourriez également arrondir à l'entier inférieur (ou à l'entier pair) en vérifiant si le reste n'est pas nul (c'est-à-dire si t^2 == 4N).
Notez qu'il n'est pas nécessaire d'utiliser l'arithmétique à virgule flottante. En fait, vous ne devriez pas. Cet algorithme doit être implémenté entièrement en utilisant des entiers (en particulier, les fonctions floor() indiquent simplement que la division normale des entiers doit être utilisée).
La méthode de Newtwon est celle que j'utiliserais. Elle converge en un nombre quadratique d'itérations et se comporte très bien pour la plupart des estimations initiales.
@fredrikj : votre réponse siempre permet d'obtenir un entier . Suggérez-vous que "la racine carrée la plus précise d'un nombre entier" est siempre entier ?
En fonction de vos besoins, une simple stratégie de division et de conquête peut être utilisée. Elle ne convergera pas comme rapide que d'autres méthodes, mais elle peut être beaucoup plus facile à comprendre pour un novice. En outre, comme il s'agit d'un algorithme O(log n) (divisant par deux l'espace de recherche à chaque itération), le pire cas pour un flotteur de 32 bits sera de 32 itérations.
Supposons que vous souhaitiez obtenir la racine carrée de 62,104. Vous choisissez une valeur à mi-chemin entre 0 et cette valeur, et vous l'élevez au carré. Si le carré est supérieur à votre nombre, vous devez vous concentrer sur les nombres inférieurs au point médian. S'il est trop bas, concentrez-vous sur les nombres supérieurs.
Avec de vraies mathématiques, vous pourriez continuer à diviser l'espace de recherche en deux à l'infini (s'il n'y a pas de racine carrée rationnelle). En réalité, les ordinateurs finiront par manquer de précision et vous aurez votre approximation. Le programme C suivant illustre ce point :
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
float val, low, high, mid, oldmid, midsqr;
int step = 0;
// Get argument, force to non-negative.
if (argc < 2) {
printf ("Usage: sqrt <number>\n");
return 1;
}
val = fabs (atof (argv[1]));
// Set initial bounds and print heading.
low = 0;
high = mid = val;
oldmid = -1;
printf ("%4s %10s %10s %10s %10s %10s %s\n",
"Step", "Number", "Low", "High", "Mid", "Square", "Result");
// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) {
oldmid = mid;
// Get midpoint and see if we need lower or higher.
mid = (high + low) / 2;
midsqr = mid * mid;
printf ("%4d %10.4f %10.4f %10.4f %10.4f %10.4f ",
++step, val, low, high, mid, midsqr);
if (mid * mid > val) {
high = mid;
printf ("- too high\n");
} else {
low = mid;
printf ("- too low\n");
}
}
// Desired accuracy reached, print it.
printf ("sqrt(%.4f) = %.4f\n", val, mid);
return 0;
}Voici quelques essais pour que vous puissiez vous faire une idée de la manière dont cela fonctionne. Pour 77 :
pax> sqrt 77
Step Number Low High Mid Square Result
1 77.0000 0.0000 77.0000 38.5000 1482.2500 - too high
2 77.0000 0.0000 38.5000 19.2500 370.5625 - too high
3 77.0000 0.0000 19.2500 9.6250 92.6406 - too high
4 77.0000 0.0000 9.6250 4.8125 23.1602 - too low
5 77.0000 4.8125 9.6250 7.2188 52.1104 - too low
6 77.0000 7.2188 9.6250 8.4219 70.9280 - too low
7 77.0000 8.4219 9.6250 9.0234 81.4224 - too high
8 77.0000 8.4219 9.0234 8.7227 76.0847 - too low
9 77.0000 8.7227 9.0234 8.8730 78.7310 - too high
10 77.0000 8.7227 8.8730 8.7979 77.4022 - too high
11 77.0000 8.7227 8.7979 8.7603 76.7421 - too low
12 77.0000 8.7603 8.7979 8.7791 77.0718 - too high
13 77.0000 8.7603 8.7791 8.7697 76.9068 - too low
14 77.0000 8.7697 8.7791 8.7744 76.9893 - too low
15 77.0000 8.7744 8.7791 8.7767 77.0305 - too high
16 77.0000 8.7744 8.7767 8.7755 77.0099 - too high
17 77.0000 8.7744 8.7755 8.7749 76.9996 - too low
18 77.0000 8.7749 8.7755 8.7752 77.0047 - too high
19 77.0000 8.7749 8.7752 8.7751 77.0022 - too high
20 77.0000 8.7749 8.7751 8.7750 77.0009 - too high
21 77.0000 8.7749 8.7750 8.7750 77.0002 - too high
22 77.0000 8.7749 8.7750 8.7750 76.9999 - too low
23 77.0000 8.7750 8.7750 8.7750 77.0000 - too low
sqrt(77.0000) = 8.7750Pour 62.104 :
pax> sqrt 62.104
Step Number Low High Mid Square Result
1 62.1040 0.0000 62.1040 31.0520 964.2267 - too high
2 62.1040 0.0000 31.0520 15.5260 241.0567 - too high
3 62.1040 0.0000 15.5260 7.7630 60.2642 - too low
4 62.1040 7.7630 15.5260 11.6445 135.5944 - too high
5 62.1040 7.7630 11.6445 9.7037 94.1628 - too high
6 62.1040 7.7630 9.7037 8.7334 76.2718 - too high
7 62.1040 7.7630 8.7334 8.2482 68.0326 - too high
8 62.1040 7.7630 8.2482 8.0056 64.0895 - too high
9 62.1040 7.7630 8.0056 7.8843 62.1621 - too high
10 62.1040 7.7630 7.8843 7.8236 61.2095 - too low
11 62.1040 7.8236 7.8843 7.8540 61.6849 - too low
12 62.1040 7.8540 7.8843 7.8691 61.9233 - too low
13 62.1040 7.8691 7.8843 7.8767 62.0426 - too low
14 62.1040 7.8767 7.8843 7.8805 62.1024 - too low
15 62.1040 7.8805 7.8843 7.8824 62.1323 - too high
16 62.1040 7.8805 7.8824 7.8815 62.1173 - too high
17 62.1040 7.8805 7.8815 7.8810 62.1098 - too high
18 62.1040 7.8805 7.8810 7.8807 62.1061 - too high
19 62.1040 7.8805 7.8807 7.8806 62.1042 - too high
20 62.1040 7.8805 7.8806 7.8806 62.1033 - too low
21 62.1040 7.8806 7.8806 7.8806 62.1038 - too low
22 62.1040 7.8806 7.8806 7.8806 62.1040 - too high
23 62.1040 7.8806 7.8806 7.8806 62.1039 - too high
sqrt(62.1040) = 7.8806Pour 49 :
pax> sqrt 49
Step Number Low High Mid Square Result
1 49.0000 0.0000 49.0000 24.5000 600.2500 - too high
2 49.0000 0.0000 24.5000 12.2500 150.0625 - too high
3 49.0000 0.0000 12.2500 6.1250 37.5156 - too low
4 49.0000 6.1250 12.2500 9.1875 84.4102 - too high
5 49.0000 6.1250 9.1875 7.6562 58.6182 - too high
6 49.0000 6.1250 7.6562 6.8906 47.4807 - too low
7 49.0000 6.8906 7.6562 7.2734 52.9029 - too high
8 49.0000 6.8906 7.2734 7.0820 50.1552 - too high
9 49.0000 6.8906 7.0820 6.9863 48.8088 - too low
10 49.0000 6.9863 7.0820 7.0342 49.4797 - too high
11 49.0000 6.9863 7.0342 7.0103 49.1437 - too high
12 49.0000 6.9863 7.0103 6.9983 48.9761 - too low
13 49.0000 6.9983 7.0103 7.0043 49.0598 - too high
14 49.0000 6.9983 7.0043 7.0013 49.0179 - too high
15 49.0000 6.9983 7.0013 6.9998 48.9970 - too low
16 49.0000 6.9998 7.0013 7.0005 49.0075 - too high
17 49.0000 6.9998 7.0005 7.0002 49.0022 - too high
18 49.0000 6.9998 7.0002 7.0000 48.9996 - too low
19 49.0000 7.0000 7.0002 7.0001 49.0009 - too high
20 49.0000 7.0000 7.0001 7.0000 49.0003 - too high
21 49.0000 7.0000 7.0000 7.0000 49.0000 - too low
22 49.0000 7.0000 7.0000 7.0000 49.0001 - too high
23 49.0000 7.0000 7.0000 7.0000 49.0000 - too high
sqrt(49.0000) = 7.0000
D'où mon premier paragraphe - l'intention de cette réponse était de montrer une façon de procéder qui ne nécessite pas de connaissances en calcul. Bien sûr, si vous voulez utiliser la méthode de Newton à l'aveugle (sans comprendre), c'est très bien - ma méthode n'en sera que plus efficace. Mais je n'ai pas mis tous ces tableaux dans ma réponse pour prouver sa rapidité - ils sont là pour éduquer.
Comment la méthode de Newton peut-elle être plus rapide que O(log n) ? Quelle est la complexité en temps de la méthode de Newton ?
Une méthode simple (mais pas très rapide) pour calculer la racine carrée de X :
squareroot(x)
if x<0 then Error
a = 1
b = x
while (abs(a-b)>ErrorMargin)
a = (a+b)/2
b = x/a
endwhile
return a;Exemple : racine carrée(70000)
a b
1 70000
35001 2
17502 4
8753 8
4381 16
2199 32
1116 63
590 119
355 197
276 254
265 264Comme vous pouvez le voir, il définit une limite supérieure et une limite inférieure pour la racine carrée et réduit la limite jusqu'à ce que sa taille soit acceptable.
Il existe des méthodes plus efficaces, mais celle-ci illustre le processus et est facile à comprendre.
Veillez simplement à fixer la marge d'erreur à 1 si vous utilisez des nombres entiers, sinon vous aurez une boucle sans fin.
C'est le meilleur algorithme que je connaisse pour calculer une racine carrée entière, mais je ne suis pas sûr que le mode d'arrondi soit déterministe (il semble que ce soit l'arrondi à l'entier le plus proche, mais je ne suis pas sûr que ce soit toujours le cas). A la fin, je renvoie le plus petit de a et b, de sorte que la fonction renvoie toujours floor(sqrt(x)).
Il s'agit d'un très bon et célèbre algorithme. Il est également appelé méthode de Herons ou méthode de Babylone. Très facile à mettre en œuvre ! fr.wikipedia.org/wiki/Babylonian_method#Babylonian_method
Permettez-moi de vous signaler une méthode extrêmement intéressante de calcul de la racine carrée inverse 1/sqrt(x), qui est légendaire dans le monde de la conception de jeux, car elle est d'une rapidité époustouflante. Ou attendez, lisez le post suivant :
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-Root/
PS : Je sais que vous ne voulez que la racine carrée, mais l'élégance de quake a vaincu toute résistance de ma part :)
D'ailleurs, l'article susmentionné parle également de l'ennuyeuse approximation de Newton-Raphson.
Je me souviens avoir lu un article à ce sujet il y a quelque temps. Je ne suis pas digne d'être en présence de celui qui a trouvé cette solution ;p
La méthode est Newton-Raphson - il s'agit simplement d'utiliser une approximation à une seule itération avec un petit bidouillage. Newton-Raphson peut calculer de nombreuses fonctions inverses, et pas seulement la racine carrée.
Bien sûr, il s'agit d'une approximation ; c'est ainsi que fonctionnent les mathématiques avec des nombres à virgule flottante.
Quoi qu'il en soit, la méthode standard consiste à utiliser Méthode de Newton . C'est à peu près la même chose que d'utiliser la série de Taylor, l'autre méthode qui me vient immédiatement à l'esprit.
Il serait bon que vous suggériez quelque chose du point de vue de la mise en œuvre dans la réponse.
En ce qui concerne l'algorithme, il peut être approximatif, mais seulement dans certaines limites que vous êtes libre de définir. Vous pouvez répéter la boucle jusqu'à ce que ces limites soient aussi petites que vous le souhaitez - en principe (si vous faites très attention à la façon dont vous le codez), vous pouvez atteindre la même précision que votre représentation des nombres en virgule flottante. Donc oui, cela reste approximatif - mais seulement parce que la virgule flottante est toujours approximative. Même 0,1 ne peut être représenté qu'approximativement en virgule flottante binaire.
@Ravi : La méthode de Newton est implémentée par l'algorithme que vous avez mis en lien -- utilisez-le donc. Pour commencer, pensez à trouver le 2^n le plus proche du nombre dont vous voulez prendre la racine, puis utilisez 2^(n/2) comme point de départ. Cependant, comme la fonction f(x)=x^2 est convexe partout, la méthode de Newton fonctionne assez bien pour elle, indépendamment du point de départ.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
2 votes
Vous ne précisez pas si le résultat doit être un entier ou s'il peut être un flottant.
12 votes
Une racine carrée d'un nombre entier et une racine carrée d'un nombre entier sont deux choses totalement différentes.
0 votes
fr.wikipedia.org/wiki/Methods_of_computing_square_roots
0 votes
fr.wikipedia.org/wiki/Integer_square_root
2 votes
Plutôt que de blâmer le fait de ne pas pouvoir
find where [it](http://nlindblad.org/2007/04/04/write-your-own-square-root-function/) has been movedcomme une excuse bidon, permettez-moi de brancher l'archive web .