S'abonner par RSS-
Calcul de la racine carrée
par Skreo, le 11 Mars 2006 à 00:44Je me posais depuis un certain temps la question toute bête mais interessante : comment calculer efficacement la racine carrée d'un nombre ?
Je parts de x² = a
Il y a quelques mois j'avais fait un petit programme un peu brutal et très lent sur ma TI-89 qui essayait plein de possibilités pour trouver x en vérifiant à chaque fois en comparant x² et a, jusqu'à obtenir un écart maximal prédéfini. Mais c'était pas du tout satisfaisant...
J'ai alors cherché un peu sur internet, et j'ai trouvé plusieurs méthodes, mais la plupart étaient faites pour être utilisées à l'écrit, et elles étaient donc inexploitable dans un programme. Et j'ai trouvé la méthode d'Héron d'Alexandrie (1er siècle après J-C) qui consiste en fait à créer une fonction dont le minimum sur R+ est en x = √a et y = √a. On cherche donc à atteindre le minimum de cette fonction pour avoir la valeur la plus approchée possible de √a
A partir de l'équation x² = a, on obtient :
2x² = x² + a
2x = x + a/x
x = (x + a/x)/2
Ce qui donne une fonction f(x) = (x + a/x)/2
A gauche, on voit la fonction f(x) = (x + 9/x)/2 pour trouver la racine carré de 9
On voit bien que le minimum de f(x) sur R+ est en 3, qui est bien ce que l'on cherche ^^
Mais comment trouver ce minimum ? En calculant la dérivée f '(x) de f(x) et en cherchant la solution de f '(x) = 0 (la dérivée étant égale au coefficient directeur de la tangente en un point, elle est égale à 0 lorsque la tangente est horizontale, et donc lorsque f(x) atteint son minimum)
Mais non ! car si on fait ça, le résultat est.... √a ! On ne va tout de même pas tourner en rond ^^
Non en fait cette fonction permet à partir de n'importe quel nombre de départ d'obtenir un nombre plus proche de √a que ce nombre de départ. Donc en répétant le calcul 3 ou 4 fois on obtient déjà une très bonne approximation.Prenons par exemple a = 671, et la racine carré de la puissance de 10 de ce nombre comme nombre de départ (facile à mettre en oeuvre dans un programme).
On a dans ce cas comme nombre de départ : x = √100 = 10
f(10) = (10 + 671 / 10) / 2 = 39,05
f(39,05) = (39,05 + 671 / 39,05) / 2 = 28,1025641025
f(28,1025641025) = (28,1025641025 + 671 / 28,1025641025) / 2 = 25,9896944600
f(25,9896944600) = (25,9896944600 + 671 / 25,9896944600) / 2 = 25,9038100697
f(25,9038100697) = (25,9038100697 + 671 / 25,9038100697) / 2 = 25,9036676943
f(25,9036676943) = (25,9036676943 + 671 / 25,9036676943) / 2 = 25,9036676940
La valeur réelle de la racine carré de 671 donnée par un ordinateur est 25,9036676940
Au bout de 3 calculs, on obtient déjà un résultat convenable : 25,98
Et au bout de 6 calculs, on trouve la racine carré de 671 avec une précision de 10 chiffres après la virgule !
Evidemment, plus le nombre de départ est proche de la racine carré, et le nombre dont on veut trouver la racine carré est petit, moins il y a de calculs à faire ^^
Partager cet article :
Tags : 671, nombre, racine, carre, minimum
Suivre le flux RSS des commentaires de cet article
Revenir à la liste des articles
-
Commentaires
cousin>> merci mais je connais la fonction sqrt quand même ^^
L'intêret est justement de savoir comment calculer une racine carré avec un programme entièrement fabriqué par soit, sans aucune fonction existante.
Là on a besoin uniquement de pouvoir multiplier et diviser ^^
Après c'est sûr que je n'utiliserai jamais ça dans un programme, parce que les fonctions native des langages sont toujours plus rapides (normal puisqu'elles sont natives ^^)Cousin=> tu n'as pas compris la portée du script ^^
Si c'était juste pour calculer une racine carré, on connait tous sqrt()..
l''intérêt c'est de la trouver à partir de fonctions simples...4Payda
13 Mars 2006 à 21:17Mouaif on connait tous sqrt ca reste avoir^^ Skreo ou comment choper un mal de tête carabiné^^
5chazlin
15 Mars 2006 à 21:46peuh c'est trop facil, moi j'utilise la fonction carrée inverse par le bicentre symetrique au cube du cercle inscrit au parrallelogramme, le tout multiplié par le sqrt et jfous 2 patates dans la caltosse et ça me donne 2² = 4 ... ça pose un prob ? :p
Sinon , jdis qu il y a un moyen plus rapide, on appuis sur la tite touche shift, puis racine carré, et le nombre demandé, et ça vous ldonne !!! Si si jvous jure faut esayer ;)6titoune18 Mars 2006 à 14:30super on enleve mon commentare, et bien moi je dis chacun dis ce qu il veu si je trouve ca nutile c est mon choix! non ?mdr j'ai rien comprit ^^ mais bon ça me servira surment un jour donc si à un moment j'ai un truc comme ça ben je viendrai voir comment on fait ici ça à l'air bien axpliquer ^_^titoune>> j'ai enlevé ton commentaire car il n'avait vraiment aucun interêt. Si encore tu demandais des précision pour comprendre, je te les donnerais, mais là....
Et au fait cousin, même pour ta fonction puissance il y a beaucoup plus simple ^^
Il suffit de faire (en java) :
int puissance(int a, int b){
int p=a;
for(int i=1;i<b;i++) p*=a;
return p;
}9chazlin
18 Mars 2006 à 22:03on lui a collé une caltosse multimedia quand il etait pitit c'est pour ça que maintenant ça degenere un peu :p
10cousin20 Mars 2006 à 12:53Skreo, oui elle est plus simple mais beaucoups lente à calculer la racine carrée (ta proposition).
si tu essayes de calculer puissance(2,5000) tu verras que ma proposition est plus rapide.
Pour a^n (n>0, n entier)
Ta proposition: complexité linéaire (n multiplication)
Ma proposition: complexité logarithmique (log n multiplication)
Ce qui donne dans l'exemple 2^5000
Ta proposition: 5000 multiplications
Ma proposition: 3,7 multiplications (oui je t'entends déjà! c'est environ 4!!!)
Ce n'est pas très négligeable surtout si tu l'appelle plusieurs fois! :-o
Mon premier poste était a but informatif... Je n'avais pas compris si c'était un programme pour "t'amuser" ou si tu ne connaissait pas la fonction sqrt ...(on est pas obligé de tout connaitre)
En tout cas, fin de la polémique :p
ah oué pas bête ^^
12Germs
20 Mars 2006 à 20:22et au passage, tu as aussi enlevé le mien...^^
C'est vrai que ca peut etre utile, mais faut s'y connaitre...
et je ne suis pas d'accord quand tu ecris :
int puissance(int a, int b){
int p=a;
for(int i=1;i<b;i++) p*=a;
return p;
}
parce que là, c'est que du pif!!!looooool13chazlin
1 Avril 2006 à 00:31l'ego masculin depasse mon entendement :p
14bricedenice292919 Avril 2006 à 15:10comment comprendre un truc quand c'est une discusion de génie de l'informatique et des maths sans avoir apprit un poil de ca ? mdr c'est pas possible lool :-)15Snoopix25 Juillet 2006 à 21:32Ca vous amuse de nous ridiculiser avec vos truc de math ?Nous , pauvre inculte que nous somme !
Moi le seul truc en math que jconait c'est :
50g de Pain + 2 cuillere de Nutella = 1kg de + sur la ballance
Tu n'es pas de mon avis Chazlin ?
Et oui comme vous le comprendrez ,je suis moi aussi tomber dans cette spirale infernale ...16bairq13 Septembre 2006 à 14:48comment calculer ln 2 ???
quel serait l'quivalent de f(x)=(x+a/x)/2 pour caluler ln 2 ??Hum pour le logarithme népérien je pense pas qu'on puisse utiliser un algo comme ça. C'est plus compliqué car il faut trouver dans ce cas la puissance de l'exponentiel :
pour x = ln(a), on cherche x, et e^x = aAlors en fait pour le logarithe népérien, c'est une autre démarche qu'il faut adopter. Il faut chercher de la même manière que pour trouver un exponentiel, en faisant une approche avec un pas le plus petit possible. Si j'ai un peu temps j'essairai de faire ça
19Alphonse25 Octobre 2006 à 23:26salut a vous tous,
vous dites en java on utlise la fonction sqrt pour calculer la racine carre d un nombre,mais quand je l applique pourquoi me dit t on que cette fonction n est pas definie.
y a t il encore quelques choses a faire?
C'est normal, sqrt n'est pas une fonction globale ^^
Il faut inclure la classe java.lang.Math, et appeler la fonction avec Math.sqrt()21Angelina120 Novembre 2006 à 22:04Bah dis donc on devra faire ces trucs la à l'école ??? 8-O
Ca me donne déjà la migraine rien qu'à les voir !!
Dire que dans deux ans je veux faire math science...
22nico l pommé en math6 Janvier 2007 à 12:11ok bon je suis pa si loin ke vs ds c calcule mé g un blém ac le loga...chose :-/ je doit trouvé une valeur approché de 1.1 en partant de f'(x)=1/x et de f(1)=0 dc je suppose ke f(x) est une fonction loga machin mé si c le cas sa veut dire ke f(0)= l infini .... et la je suis perdu alors je sait pa comment faire et i fo impérativement ke j utilise le loga machinLe "loga...chose" dont tu parles est le logarithme népérien ^^
Ta fonction f est bien la fonction ln (logarithme népérien), qui associe 0 à 1 et dont la dérivée est 1/x.
Mais attention ! f(0) n'est pas égal à l'infini, car ln n'est pas définie en 0 ! Par contre sa limite en 0 est -∞
Pour trouver une valeur approchée pour 1.1, tu peux utiliser la méthode d'Euler.
Si tu ne connais pas, je l'explique rapidement, sans la démontrer :
Pour un h très petit, on peu dire que f(x+h) = f(x) + h*f'(x)
Donc si on prend h=0.02 (mais tu peux prendre 0.01 pour plus de précision), on a :
f(1.02) = f(1) + 0.02 * 1/1 = 0 + 0.02 = 0.02
f(1.04) = 0.02 + 0.02 * 1/1.02 = 0.0396
f(1.06) = 0.0396 + 0.02 * 1/1.04 = 0.0588
f(1.08) = 0.0588 + 0.02 * 1/1.06 = 0.0777
f(1.1) = 0.0777 + 0.02 * 1/1.08 = 0.0962
Et voilà, on a une valeur approchée de ln(1.1), la valeur exacte étant 0.095310179804...24divarvel
7 Janvier 2007 à 13:57En fait la valeur exacte c'est ln(1,1) :p
Mais waip la méthode d'Euler est pas mal pour des valeurs approchés.
Surtout si on te donne la dérivée.
Enfin voilà.
Allez un petit problème très facile
Soit f(x) tel que quel que soit x, f(x) = (f(x))²
Avec f continue sur R
jveux tout savoir sur f25Skreo
7 Janvier 2007 à 14:12facile :p
26nico l pommé en math7 Janvier 2007 à 14:42merci c vrément simpa ... et en + ... g compris LOL :-D ... c cool ... bon eh bien a + et bonne année27bricedenice292911 Février 2007 à 15:44arf c plus facile ac la calculette ^^28gwegwe21 Mars 2007 à 21:59bizard bizard j'arrive à comprendre quelque chose mais c'est très flou ^^
mais bon c'est déjà pas mal xD29POC
4 Octobre 2007 à 18:05La méthode de Newton serait plus rapide je pense
Fouille ça tu verra
go to msn si tu veux en parler
30hatem3 Janvier 2008 à 09:48c facile le methode cholvesky est plus facile qel descution sur mon compte skype (je lui donne dans mon mail) et merci
3112345soso1 Mai 2008 à 21:54moi ji pige rien a vos truc de matématicien =) mais jé u 1 15/20 en math sétter sur la somme algébrique je sais que sa a rien avoir mais bon
Ajouter un commentaire
Godefroy de Compreignac
Blog de Skreo :: Webdev && Hi-Tech
-
Godefroy de Compreignac, aka Skreo. Je suis actuellement étudiant en prépa PSI à l'ISEP. Passionné d'informatique et plus particulièrement de programmation web depuis 2001, mes principaux sites web sont Murties et EklaBlog. Ce blog est un support pour partager mes astuces, idées, coups de coeurs...
Vous pouvez me retrouver sur Twitter, et Facebook. -
Haut de page
Actions
Aller à l'accueil
Contact
Chercher un article
Connexion
Créer mon blog
Vous avez reçu un nouveau message !
moi j'aurais utilisé directement la fonction racine carré présente dans les bibliothèques: sqrt
sinon à défaut d'avoir trouvé la fonction, j'aurais utilisé la fonction puissance (en vérifiant que le nombre est positif avant^^)
en général les fonctions qui sont déja implémentées sont en log(n) (la complexité).
par exemple une fonction puissance en log(n) en java:
int puissance(int a,int b) { //a puissance b,b>0
if(b==1) {return a;}
else {
int p=puissance(a,b/2)*puissance(a,b/2);
if(p%2 !=0) {p+=a;}
return p;
}
}
après chacun ses gôûts! ;-)