Extraction d'une racine carrée

Soyez le premier à donner votre avis sur cette source.

Vue 19 632 fois - Téléchargée 601 fois

Description

Ce programme calcule la racine carrée d'un nombre entier avec une précision déterminée.

Exemple :
Racine de 2 avec une précision de 1 donnera : 1,4
Racine de 3 avec une précision de 0 donnera : 1
Racine de 3 avec une précision de 3 donnera : 1,732
...

Le mode de calcul est tiré du livre : Le Grand Larousse (article recopié dans un .doc disponible dans le .zip)

Source / Exemple :


cf ZIP

Conclusion :


Aucun bug connu, toutefois les calculs sont faits avec des "long long", donc il peut y avoir des dépassements de capacité (je n'ai pas développé de classe BigInt permettant de gérer des chiffres de tailles infinies).

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
1
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 octobre 2006

En réponse à notre ami COSMOBOB, je me permet d'émettre 2 critiques sur l'algo :
- D'une part, le résultat d'une racine carré d'un 32 bits sera codé sur 16 bits (si ton "int" est bien un 32 bits, cale cela dépend des compilos)
- D'autre part, le test "milieucarre < milieu" , bien que corrigeant le résultat de calcul pour certaines valeurs ne corrige pas tout ! (quand on tend vers 2^32 ça tend aussi vers des résultats systématique faux !)
Il suffit de borner la variable "droite" avec la racine de la valeur max du type d'entée, qui se trouve être aussi la valeur max de sortie (on calcul une racine carré je rappel) donc avec 2^16 = 65536.
Qu'est-ce que vous en pensez-vous ?
Il y a peut-être encore plus optimum, mais au moins, je pense que cet algo fonctionne parfaitement cette fois-ci
Enfin, pour un sujet noté "Niveau de la source : Débutant", je trouve qu'il y a beaucoup de commentaires. C'est pas si "Débutant" que cela de faire un algo de racine carré, vu le nombre d'algos qui existent, qui soit rapide et fiable...


typedef unsigned int u16;
typedef unsigned long u32;

u16 mysqrt(u32 a)
{
u16 gauche 0, milieu 0;
u16 droite;
u32 milieucarre = 0;

if (a < 65536)
{
droite = (u16)value;
}
else
{
droite = 65535;
}

if (a <= 1)
return ((u16)a);
while ((droite - gauche) > 1)
{
milieu = (u16)(((u32)droite + gauche) / 2);
milieucarre = ((u32)milieu * milieu);
if (milieucarre > a)
{
droite = milieu;
}
else
{
gauche = milieu;
}
}
return (gauche);
}
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Bon, ça me chagrinait cosmobob que tu dises que mon algo était lent, parce que je voyais pas trop pq, alors j'ai benchmarké avec le high frequency timer de windows, et le benchmark donne ton algo gagnant (4% plus rapide que le mien) sur 10 000 000 de naturels compris entre 0 et MAX_RAND (=2^16-1 chez moi). Je pense pas que tu aies pu voir une telle différence à l'oeil nu, mais en attendant t'as qd même gagné, bravo ^^.
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

arnaud, je l'ai trouvée en griffonant sur un bout de papier.
quant à "c'est une trouvaille ça", ben je trouve que oui, dans la mesure où je ne risque vraiment pas d'overflow, que je ne bosse qu'avec des entiers, que c'est élégant, que c'est du sûr, que c'est indirect... la recherche dichotomique je l'ai faite aussi, t'en fais pas, et c'est très bien si tu veux une approximation avec virgule flottante, mais c'était pas la question, comme j'ai précisé: fallait le naturel égal ou inférieur.
au passage, ma recherche dichotomique était environ 25 fois plus lente que la version de la librairie standard, qui, je suppose, fait appel au FPU d'Intel, donc bon ^^.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
29
Pour FSQRT tu vas demander à Intel, c'est en dur dans les transistors de la fpu, je ne suis pas chimiste.
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2
oh et pour Kirua : t'es pas bete toi ^^ tu la tires d'ou cette méthode?
Afficher les 38 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.