Actions
Aller à l'accueil
Chercher un article
Connexion
Créer mon blog
Vous avez reçu un nouveau message !
S'abonner par RSS
Calcul de la racine carrée
par Skreo, le 11 Mars 2006 à 00:44 (modifié le 15/09/2006 à 18:58)
Je 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 ^^
Laisser un commentaire
Tags : 671, nombre, racine, carre, minimum
Suivre le flux RSS des commentaires de cet article
Revenir à la liste des articlesCommentaires
#211 Mars 2006 à 15:05Skreo
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 ^^)#311 Mars 2006 à 15:06Divarvel
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...#413 Mars 2006 à 21:17Payda
Mouaif on connait tous sqrt ca reste avoir^^ Skreo ou comment choper un mal de tête carabiné^^#515 Mars 2006 à 21:46chazlin
peuh 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 ;)#618 Mars 2006 à 14:30titounesuper 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 ?#718 Mars 2006 à 16:53bricedenice2929mdr 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 ^_^#818 Mars 2006 à 17:04Skreotitoune>> 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;
}#918 Mars 2006 à 22:03chazlinon lui a collé une caltosse multimedia quand il etait pitit c'est pour ça que maintenant ça degenere un peu :p#1020 Mars 2006 à 12:53cousinSkreo, 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
#1220 Mars 2006 à 20:22Germs
et 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!!!looooool#131 Avril 2006 à 00:31chazlinl'ego masculin depasse mon entendement :p#1419 Avril 2006 à 15:10bricedenice2929comment 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 :-)#1525 Juillet 2006 à 21:32SnoopixCa 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 ...#1613 Septembre 2006 à 14:48bairqcomment calculer ln 2 ???
quel serait l'quivalent de f(x)=(x+a/x)/2 pour caluler ln 2 ??#1715 Septembre 2006 à 19:25SkreoHum 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 = a#1814 Octobre 2006 à 01:22SkreoAlors 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#1925 Octobre 2006 à 23:26Alphonsesalut 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?
#2026 Octobre 2006 à 16:00SkreoC'est normal, sqrt n'est pas une fonction globale ^^
Il faut inclure la classe java.lang.Math, et appeler la fonction avec Math.sqrt()#2120 Novembre 2006 à 22:04Angelina1Bah 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...
#226 Janvier 2007 à 12:11nico l pommé en mathok 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 machin#237 Janvier 2007 à 13:50SkreoLe "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...#247 Janvier 2007 à 13:57divarvelEn 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 f#257 Janvier 2007 à 14:12Skreofacile :p#267 Janvier 2007 à 14:42nico l pommé en mathmerci c vrément simpa ... et en + ... g compris LOL :-D ... c cool ... bon eh bien a + et bonne année#2711 Février 2007 à 15:44bricedenice2929arf c plus facile ac la calculette ^^#2821 Mars 2007 à 21:59gwegwebizard bizard j'arrive à comprendre quelque chose mais c'est très flou ^^
mais bon c'est déjà pas mal xD#294 Octobre 2007 à 18:05POC
La méthode de Newton serait plus rapide je pense
Fouille ça tu verra
go to msn si tu veux en parler#303 Janvier 2008 à 09:48hatemc facile le methode cholvesky est plus facile qel descution sur mon compte skype (je lui donne dans mon mail) et merci#311 Mai 2008 à 21:5412345sosomoi 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
Haut de page
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! ;-)