Non c'est l'algorithme de Héron d'Alexandrie que vous avez esquissé très largement ici (et non la méthode de Newton )
Soit N un réel positif dont on recherche la racine carrée
on se donne r1 une approximation de la racine carrée de N qui peut être très éloignée (cela ne pose pas de problème on arrivera quand même à atteindre la limite(la démonstration fait trois lignes)
la suite (r_n) tend vers la racine carrée de N
$$r_{n+1}=\dfrac {r_n+\dfrac {N}{r_n}}{2}$$
par exemple on va choisir exprès r1 très éloigné de la racine carrée de N
N=9745821103
$$\sqrt {N}\approx 98720.9253553$$
$$r_1=21$$
$$r_2\approx 232043370$$
à partir de $$r_{15}$$ on atteint 98906 et à partir de là la convergence est quadratique
$$r_{16}\approx 98721.0995339$$
$$r_{17}\approx 98720.9253554$$
Mais Héron d'Alexandrie nous a aussi laissé sa méthode d'extraction d'une racine carrée à la main
que nos ancêtres (d'avant 1968 nous enseignaient avant le passage au certificat d'étude)
il s'agissait de la cinquième opération à la main (après celle de l'addition, la soustraction, la multiplication et la division)
il y a avec recherche Google "racine carrée à la main" des multitudes de liens
idem racine cubiques à la main
mais le lien que je préfère c'est celui de Therese Eveilleau
utiliser une bonne approximation du logarithme népérien (même sur des très très grand nombres)
et une bonne approximation de l'exponentielle exp() alors
pour tout x >0
$$\sqrt {x}=y$$
$$exp\left(\dfrac {1}{2}ln(x)\right)=y$$
_______________________
pour une bonne approximation du logarithme népérien sur des très grands nombres il y en a une très efficace utilisant une fonction trigonométrique (par exemple sinus de période 2pi)
- Edité par DominiqueSicilia 13 décembre 2019 à 5:24:01
je ne sais pas si j'ai bien compris votre question à cause du commentaire il faut regarder à séries entières la fonction ln est infiniment dérivable et on peut l'écrire de la façon suivante selon le théorème suivant : si f est une fonction régulière alors
eh bien ln(x) comme racine carrée comme toute fonction régulière peut se calculer avec une convergence de type
1 décimale
2 décimales supplémentaire (total = 3)
3 décimales supplémentaire (total = 6)
4 décimales supplémentaires (total 10)
5 décimales supplémentaires (total 15)
etc...
c'est " très très rapide"
et pour le sujet ici il est facile de se donner une bonne approximation
j'avais fait exprès de prendre 21 mais pour montrer qu'à partir d'un certain rang la convergence devient rapide
mais j'ai fait ça pour montrer "physiquement" qu'il y a un théorème (qui fait trois lignes -celui de Héron d'Alexandrie- pour la racine carrée- comme j'ai dit) qui de toute façon affirme qu'aussi loin le premier terme de la suite soit de la limite on arrivera quand même au terme à partir duquel la suite devient très rapide
et vous avez trouvé comment exprimer efficacement ce premier terme
- Edité par DominiqueSicilia 13 décembre 2019 à 19:34:23
Je ne pense pas que ce soit très profitable d'utiliser la bibliothèque math.h ni même d'utiliser les types standards int ou long ou long long ou double pour faire des calculs qui vont dépasser les limites que celles données par ces types
où j'avais donné une approximation de son logarithme népérien
mais ce que je n'ai pas dit c'est que ce t est ici une chaîne de caractères
Oui car en ce qui me concerne je préfère travailler sur des chaîne de caractères dont l'alphabet est [0123456789-.+i]
les entiers seront écrits dans l'alphabet [0123456789-]
les "rationnels non entiers ou irrationnels réels" dans l'alphabet [0123456789-.] entre guillemets car en fait les réels en informatique n'existent pas (ce sont des nombres décimaux ((quand ils sont écrits en base dix) qui s'expriment avec une quantité finie de chiffres significatifs)
les nombres complexes dans l'alphabet [0123456789-.+i]
Là vous voulez faire des calculs par exemple avec des nombres de l'ordre 2^63 donc de l'ordre de 2^18
avec un type standard ça me semble un peu limite (de mémoire un type long est un nombre à dix chiffres)
Ce que vous décrivez est soit de l'arithmétique simulée, soit des extensions de l'arithmétique standard, donc très lents.
Pour information, le type long long comporte au maximum 16 valeurs décimales.
Pour corriger la non convergeance apparente de mon calcul, je dois garder les deux dernières approximations au lieu de la dernière seulement et je les compare avec la nouvelle approximation.
En faisant le calcul pour des nombres jusqu'à un milliard, cela me prend moins de 40 secondes.
Je vais tenter d'améliorer la façon de trouver la première approximation en utilisant une recherche dichotomique sur les exposants de 2.
Le Tout est souvent plus grand que la somme de ses parties.
ça serait dommage de laisser mourir ce sujet car ça serait intéressant de comparer nos temps de calcul selon les deux méthodes (l'une en s'aidant de la bibliothèque math.h et l'autre en traitant tout uniquement avec des chaînes de caractères -et devoir coder le calcul-pour calculer la racine carrée entière d'un nombre de plusieurs centaines de chiffres (en base dix)
Ceci dit je n'en suis pas encore là et mon code sera lourd (et ça ne fait qu'un mois que j'ai commencé à apprendre le C -et mes journées sont courtes)
NB: C'est certain que si on prend pour $$u_0$$ un nombre de poids numérique "en base dix par exemple" de la moitié du poids numérique (dans la même base) du nombre dont on recherche la racine carrée on arrive plus vite au $$u_a$$ à partir duquel la suite converge quadratiquement
- Edité par DominiqueSicilia 21 décembre 2019 à 11:50:51
"Imagine devoir diviser un nombre de 1000 chiffres par..."
En fait c'est pas si monstrueux que cela
il faut exploiter certains trucs
On sait que pour tout entier positif x et tout entier strictement positif y alors $$\dfrac {x}{y}=E\left(\dfrac {x}{y}\right)+\dfrac {x-yE\left(\dfrac {x}{y}\right)}{y}$$
et ici $$0\leq x-yE\left(\dfrac {x}{y}\right)<y$$ est le reste de la division de x par y
en manipulant bien cela il devient très facile de déterminer le rapport de deux nombres même s'ils font des milliers de chiffres
tout se ramène en fait à se donner une table de multiplication de 1 à 11 par 1 à 11 et à l'utiliser
une fois la partie entière calculée avec cette minuscule petite table on peut ensuite s'attaquer à la partie décimale qui est donnée par
$$\dfrac {x-yE\left(\dfrac {x}{y}\right)}{y}$$
- Edité par DominiqueSicilia 22 décembre 2019 à 8:47:54
Ce que tu suggères avec ta table de multiplication ressemble à de l'arithmétique simulée.
Tu pourrais faire des calculs avec des milliards de chiffres, mais ce serait horriblement long.
Le Tout est souvent plus grand que la somme de ses parties.
Trouver racine carrée entière rapidement
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.