IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

Savoir si la racine carrée d'un nombre est un nombre entier.


Sujet :

C

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 172
    Points : 68
    Points
    68
    Par défaut Savoir si la racine carrée d'un nombre est un nombre entier.
    Bonjour,

    La question est dans le titre, je voudrai écrire une fonction optimisée me renvoyant si la racine carrée d'un nombre est un nombre entier ou non, mais je ne sais pas comment m'y prendre ?

    Merci.

  2. #2
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Bonjour,

    Est-ce un exercice scolaire ou est-ce juste pour le défi ?

    Je ne pense pas qu'il y ait plus efficace, pour répondre à cette question, que calculer directement la racine dudit nombre. C'est une opération arithmétique qui ressemble à la division euclidienne sur papier et dont la complexité est proportionnelle au nombre de chiffres. En revanche, si tu sais que la racine est déjà contenue dans un intervalle limité de nombres entiers (par exemple entre 1 et 100), alors tu peux procéder par dichotomies successives, comme quand tu recherches une valeur dans une liste, à ceci près que tu compareras à x² au lieu de x seul (calculer le produit de x à chaque itération est trivial).

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 172
    Points : 68
    Points
    68
    Par défaut
    Non ce n'est pas un exercice scolaire, il y a longtemps que j'ai quitté l'école, je fais juste des recherches personnelles (à temps perdu) sur les nombres premiers , et mes recherches m'ont amené à savoir si une racine carré d'un nombre et entier ou non.
    J'utilise la fonction sqrt() de math.h mais ça ne me permet pas de savoir si le nombre est entier ou non, il doit surement y avoir une astuce simple pour savoir ça.

  4. #4
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Si. sqrt() te renvoie un double, c'est-à-dire un nombre réel, qui lui peut être entier ou pas.

    Si tu veux savoir si un réel, float ou double, est entier en lui-même, indépendamment des différentes fonctions, tu peux par exemple utiliser rint() qui arrondit un réel à l'entier le plus proche. Il te suffit alors d'écrire if (x == rint(x))

  5. #5
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Hello,

    Si tes nombres en entrée sont des flottants, alors tu peux éliminer tous ceux qui ne sont pas entiers.

    Il est aussi certainement possible d'éliminer rapidement certains nombres avec une lookup table : en décimal on sait qu'un carré se termine par 0, 1, 4, 5, 6 ou 9, c'est surement (j'ai pas la démonstration, mais ça me semble logique ) pareil en binaire.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    inline unsigned int fastSqrt(unsigned int n) {
    	// http://blog.quenta.org/2012/09/0x5f3759df.html
    	float nhalf = 0.5f * n;
    	int i = int(n);
    	i = 0x1fbd1df5 - (i >> 1);
    	float x = *(float*)&i;
    	x = x*(1.5f-(nhalf * x * x));
    	return unsigned int(x);
    }
     
    inline bool isSqrtInt(unsigned int n) {
    	// exemple avec une table vérifiant les 3 derniers bits (8 entrées)
    	// ça peut bien sur s'agrandir, en gardant une taille raisonnable pour que
    	// la table tienne entièrement en cache L1.
    	// 8 bits -> 256 entrées -> 1ko, 2ko en 64 bits (? sizeof(bool)  == 1, mais ça sera aligné sur 4/8 octets)
    	// est probablement une taille correcte.
     
    	// seuls les 3 bits de poids faible du résultat sont importants
    	// 000 x 000 = 000
    	// 001 x 001 = 001
    	// 010 x 010 = 100
    	// 011 x 011 = 001
    	// 100 x 100 = 000
    	// 101 x 101 = 001
    	// 110 x 110 = 100
    	// 111 x 111 = 001
    	static const bool lut[] = {
    		true,  // 000
    		true,  // 001
    		false, // 010
    		false, // 011
    		true,  // 100
    		false, // 101
    		false, // 110
    		false  // 111
    	};
    	if(lut[n & 7]) {
    		unsigned int sq = fastSqrt(n);
    		return sq*sq == n;
    	}
    	return false;
    }
    Il est aussi possible de stocker tous les carrés (si les nombres que tu testes sont dans un petit intervalle bien sur).

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Iradrille Voir le message
    en décimal on sait qu'un carré se termine par 0, 1, 4, 5, 6 ou 9, c'est surement (j'ai pas la démonstration, mais ça me semble logique )
    Bonjour

    La démonstration est facile: un chiffre entier se terminant par 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9, son carré se terminera par 0, 1, 4, 9, 6, 5, 6, 9, 4 ou 1 soit 0, 1, 4, 5, 6 ou 9.

    Une démonstration ne se fait pas obligatoirement qu'avec des x et des y. Si l'ensemble de départ est un ensemble fini et dénombrable, alors t'as tout à fait le droit d'examiner chaque élément de l'ensemble de départ pour regarder s'il vérifie la propriété à démontrer. Et si tous la vérifient alors QED.
    Généralement les propriétés à démontrer se font sur des ensembles infinis donc là, forcément, on est obligé de symboliser les éléments par des lettres. Mais quand on a la chance de tomber sur un cas fini, alors faut pas laisser passer l'occasion de briller facilement

    Sinon pour la question initiale ben puisqu'on ne travaille qu'avec des entiers, moi j'éliminerais l'utilisation des flottants (toujours très longue) et je calculerais la racine carrée entière du nombre initial. Ca, ça peut se faire avec la formule de Heron (limite de la suite Un+1=1/2(Un+N/Un))

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    unsigned short racine2(unsigned long n)
    {
    	unsigned long U[3]={0, 0, 1};		// Les 3 derniers calculs Un
     
    	if (n == 0 || n == 1) return n;		// Elimine les cas triviaux
     
    	while (1)
    	{
    		U[0]=U[1];						// Décalage 3 derniers calculs
    		U[1]=U[2];
     
    		U[2]=(U[1] + n/U[1]) >> 1;		// Calcule le résultat actuel (Un). Un décalage de bits donne le même résultat qu'une divison par 2.
     
    		// Si le dernier calcul est égal à un des deux précédents, on a atteint la limite de la suite
    		if (U[2] == U[1] || U[2] == U[0]) return U[2];
    	}
    }

    Bon, j'ai quand-même dû adapter aux nombres entiers. Parce qu'avec des flottants suffit de ne comparer que l'avant dernier élément de la suite avec le dernier mais avec des entiers, faut regarder les deux avant-derniers (sinon on tombe dans une boucle infinie x-1/x+1).
    Et en plus le calcul n'est pas parfait. Par exemple, pour 35, il renvoie 6. La logique et les règles de calcul voudraient qu'il renvoie 5 mais les aléas de la suite (qui alterne avec pluspetit/plus grand) font qu'à ce moment c'était sur un "plus grand".
    Toutefois pour les carrés parfait le calcul semble bon (testé sur les 65536 premiers carrés).
    Et en ce qui concerne le nombre d'itérations dans la recherche de la racine, la plus grande concerne la racine de 666465852 qui fait faire 21 itérations.

    Ensuite suffit de regarder si le carré du nombre renvoyé est égal au nombre initial...

    Sinon il y a une autre solution qui part de la plage de valeur des nombres traités. Si tu travailles avec des unsigned short (65536 valeurs), tu n'auras que 256 carrés parfaits. Donc facile à mettre dans un tableau puis ensuite regarder si un de tes nombres s'y trouve.
    Si maintenant tu travailles avec des unsigned long (4294967296 valeurs) ça te fait 65536 carrés parfaits. Toujours possible mais plus long...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  7. #7
    Expert confirmé
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Points : 4 442
    Points
    4 442
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    La démonstration est facile: un chiffre entier se terminant par 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9, son carré se terminera par 0, 1, 4, 9, 6, 5, 6, 9, 4 ou 1 soit 0, 1, 4, 5, 6 ou 9.

    Une démonstration ne se fait pas obligatoirement qu'avec des x et des y. Si l'ensemble de départ est un ensemble fini et dénombrable, alors t'as tout à fait le droit d'examiner chaque élément de l'ensemble de départ pour regarder s'il vérifie la propriété à démontrer. Et si tous la vérifient alors QED.
    Généralement les propriétés à démontrer se font sur des ensembles infinis donc là, forcément, on est obligé de symboliser les éléments par des lettres. Mais quand on a la chance de tomber sur un cas fini, alors faut pas laisser passer l'occasion de briller facilement
    Ho bah je l'avais en fait la démonstration, je savais juste pas que ça suffisait (cf. mon code).

    Pour le fait de travailler avec des entiers, à tester mais je pense que d'utiliser des float et le trick assez connu pour avoir une bonne valeur de départ pour l'algo de Heron sera plus rapide vu qu'une ou deux itérations seulement donnent une approximation correcte.

  8. #8
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 172
    Points : 68
    Points
    68
    Par défaut
    Merci pour vos réponses, j'ai trouvé une solution de mon coté qui fonctionne bien.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int main (void)
    {
       long int nombre;
       float rc, arrondi;
     
       nombre=361;
       rc=sqrt(nombre);
       arrondi=floor(rc);
     
       if(rc-arrondi==0) { printf("entier\n");}
       else {printf("Pas entier\n") ;}
     
     
       return 0 ;
    }
    C'est une solution simple mais ça fonctionne.

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 172
    Points : 68
    Points
    68
    Par défaut
    Vous savez quelle méthode utilise la fonction sqrt() de math.h pour calculer la racine carré ?

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Iradrille Voir le message
    ...avoir une bonne valeur de départ pour l'algo de Heron sera plus rapide vu qu'une ou deux itérations seulement donnent une approximation correcte.
    Le mieux (Tyrtamos me l'a appris) c'est de partir d'un nombre déjà proche de la racine cherchée.
    Lui, il part de 10^(nb_chiffres/2). Et à partir de là, calculer la racine d'un nombre contenant 10000 chiffres ne prend que 13 itérations (contre 16634 si on part de 1 ou si on part du nombre initial)...

    Citation Envoyé par fred61 Voir le message
    C'est une solution simple mais ça fonctionne.
    Attention toutefois à l'imprecision des nombres flottants. C'est un problème qui est lié non pas au langage mais à la façon dont l'ordi converti un nombre flottant en base 2. Il peut arriver que la conversion ne soit pas possible avec exactitude (dans le cas où le nombre ne peut pas s'exprimer sous la forme d'une fraction de 1 par une puissance de 2). Ainsi 0.24 sera vu par l'ordinateur comme 0.239999999.

    Et donc dans cette imprécision, une soustraction de deux nombres théoriquement égaux peut ne pas donner 0. Donc quand on veut vérifier l'égalité de deux flottants, vaut mieux regarder si leur différence est plus petite qu'epsilon (à définir)...

    Citation Envoyé par fred61 Voir le message
    Vous savez quelle méthode utilise la fonction sqrt() de math.h pour calculer la racine carré ?
    A vue de pieds je pencherais pour les log. ln(sqrt(x))=1/2ln(x). Avec une table des logarithmes et des exponentielles et le tour est joué...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  11. #11
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 172
    Points : 68
    Points
    68
    Par défaut
    Citation Envoyé par Sve@r Voir le message

    Attention toutefois à l'imprecision des nombres flottants. C'est un problème qui est lié non pas au langage mais à la façon dont l'ordi converti un nombre flottant en base 2. Il peut arriver que la conversion ne soit pas possible avec exactitude (dans le cas où le nombre ne peut pas s'exprimer sous la forme d'une fraction de 1 par une puissance de 2). Ainsi 0.24 sera vu par l'ordinateur comme 0.239999999.

    Et donc dans cette imprécision, une soustraction de deux nombres théoriquement égaux peut ne pas donner 0. Donc quand on veut vérifier l'égalité de deux flottants, vaut mieux regarder si leur différence est plus petite qu'epsilon (à définir)...

    .
    Et si je fais :

    if (floor(y)==y)

    Il ne devrait pas y avoir le problème d’imprécision des nombres flottant non ?

  12. #12
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    En fait, il faut garder à l'esprit qu'un nombre flottant est limité en taille et vaut « 1,mantisse × 2exposant ». Donc sa racine carrée vaut forcément « sqrt(1,mantisse) × 2exposant ÷ 2 ». Si l'exposant est impair, il suffit de décaler la mantisse d'un bit et de corriger l'exposant en conséquence. À ce stade, calculer la mantisse du flottant revient à calculer celle de sa mantisse seule.

    Et pour ce faire, on peut utiliser l'algorithme que l'on utilisait jadis directement sur papier (et dont je ne connais pas le nom), consistant à grouper les chiffres du nombre par paires de part et d'autre de la virgule. Il est tout-à-fait possible de faire cela en binaire avec la mantisse. Les opérations sont alors extrêmement simples en elles-mêmes et le nombre d'itérations ne dépend que de la largeur de la mantisse, ce qui signifie au passage que la durée de l'opération est invariable pour un type donné, quelque soit la valeur extraite.

  13. #13
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par fred61 Voir le message
    Et si je fais :

    if (floor(y)==y)

    Il ne devrait pas y avoir le problème d’imprécision des nombres flottant non ?
    Oui, là c'est bon puisque les nombres entiers même mis en flottant n'ont aucun problème d'imprécision.

    Citation Envoyé par Obsidian Voir le message
    Et pour ce faire, on peut utiliser l'algorithme que l'on utilisait jadis directement sur papier (et dont je ne connais pas le nom), consistant à grouper les chiffres du nombre par paires de part et d'autre de la virgule.
    Il s'agit de la méthode de la potence.
    Elle est tirée du fait que (a+b)2=a2+2ab+b2. Toutefois c'est déjà un petit travail que de programmer ça en C. Surtout que le calcul, même fait à la main, devient de plus en plus complexe. En effet, le résultat, qui grossit d'un chiffre à chaque itération, est intégralement réutilisé à chaque itération pour trouver le chiffre suivant...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  14. #14
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Il s'agit de la méthode de la potence.
    Merci pour le nom.

    Toutefois c'est déjà un petit travail que de programmer ça en C. Surtout que le calcul, même fait à la main, devient de plus en plus complexe. En effet, le résultat, qui grossit d'un chiffre à chaque itération, est intégralement réutilisé à chaque itération pour trouver le chiffre suivant...
    Oui mais ce résultat, dans tous les cas, ne dépasse jamais la taille de la mantisse initiale. Donc, on travaille quand même sur les mêmes formats de registre. cette méthode de la potence consiste, à la première étape, à estimer soi-même le chiffre dont le carré est le plus proche, mais le binaire simplifie encore la chose puisque ce chiffre est forcément 0 ou 1, et que le carré de 1 est 1. Donc, si les deux premiers bits ne sont pas nuls, le premier bit à insérer est un 1.

    Ensuite, le reste de l'algorithme consiste à ajouter un chiffre et à multiplier par ce même chiffre. L'ajout d'un chiffre se fait par insertion par la droite, ce qui est aisé en C et devient même trivial en assembleur (avec la possibilité de faire un SHL ou un ROL impliquant la retenue C). Puis on multiplie soit par 0, ce qui revient simplement à sauter l'étape d'addition et passer au tour suivant, soit par 1 ce qui permet quand même de se passer de la multiplication. C'est d'ailleurs cette méthode qu'utilisait le BASIC de mon vieux TO8D.

    Enfin, c'est plus efficace que l'approche par le logarithme et l'exponentielle si c'est également à toi de coder ces fonctions. Mon Thomson, toujours lui, utilisait des approximants de Padé pour y parvenir. Ça fonctionnait très bien, mais ça restait coûteux. Par contre, c'est naturellement la voie suivie pour calculer tout « xy » avec x,y ∈ ℝ. Calculer une racine carrée ne consiste alors plus qu'à élever à la puissance 1÷2.

  15. #15
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Obsidian Voir le message
    Enfin, c'est plus efficace que l'approche par le logarithme et l'exponentielle...
    Ici j'ai trouvé un paquet d'algo(rithmes pour éviter à notre ami LittleWhite de corriger mes posts ) de racine carrée implémentés en C.

    Il y en a un paquet dont je n'arrive même pas à entrevoir la théorie qui les sous-tend...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  16. #16
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Il y a celle de J. Carmack

    Mais d'après Wiki, la fonction inverse est illégale en C++03

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    float SquareRootFloat(float number) {
        long i;
        float x, y;
        const float f = 1.5F;
     
        x = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;
        i  = 0x5f3759df - ( i >> 1 );
        y  = * ( float * ) &i;
        y  = y * ( f - ( x * y * y ) );
        y  = y * ( f - ( x * y * y ) );
        return number * y;
    }
     
     
    // Inverse
    float Q_rsqrt( float number ) {
        long i;
        float x2, y;
        const float threehalfs = 1.5F;
     
        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y; // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
        // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
     
        #ifndef Q3_VM
        #ifdef __linux__
          assert( !isnan(y) ); // bk010122 - FPE?
        #endif
        #endif
        return y;
    }
     
    // Inverse plus performante de Chris Lomont
    float InvSqrt(float x) {
      float xhalf = 0.5f*x;
      int i = *(int*)&x; // get bits for floating value
      i = 0x5f375a86- (i>>1); // gives initial guess y0
      x = *(float*)&i; // convert bits back to float
      x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
      return x;
    }

Discussions similaires

  1. Calcul de la racine carrée d'un nombre
    Par Anomaly dans le forum Télécharger
    Réponses: 3
    Dernier message: 05/11/2013, 00h16
  2. Calculer la racine carrée d'un nombre d'une façon particulière
    Par Roud9 dans le forum Débuter avec Java
    Réponses: 8
    Dernier message: 29/09/2010, 04h11
  3. Nombre premiers et calculer la racine carrée d'un nombre
    Par Roud9 dans le forum Débuter avec Java
    Réponses: 19
    Dernier message: 21/09/2010, 18h55
  4. Racine carrée de très grands nombres
    Par paskal64 dans le forum Général Python
    Réponses: 5
    Dernier message: 19/08/2008, 09h35
  5. la racine carré d'un nombre
    Par aziz jim dans le forum C++
    Réponses: 4
    Dernier message: 07/08/2006, 15h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo