[DEV-C++] CALCUL DE LA RACINE CARRÉE D'UN RÉEL

Signaler
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/51157-dev-c-calcul-de-la-racine-carree-d-un-reel

Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

En l'occurence sur ce genre d'opération, tous les compilos que j'ai testé détectent s'il va y avoir perte de donnée et te préviennent. Mais je suis d'accord sur le fait qu'il ne faut pas présumer de ce que va coder le compilo, je l'ai fais ainsi parce que j'ai vérifié ce que ca donnais avec le mien, mais comme je le disais également, pour en être véritablement certain, il faut caster, exactement comme tu le montres.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
28
ya.c[3] = (ya.c[3] + 127) / 2;
On ne doit surtout pas présupposer sur ce qui est codé par le compilo, quel qu'il soit.
Soit on vérifie le listing ASM et si calculs faits sur DWORD alors ok mais si faits sur AL que nenni.
Dans tous les cas je déconseille fort cette manière, aucune assurance que ira encore quand on change de compilo ou simplement de version de compilo.

DWORD v = (DWORD) ya.c[3];
ya.c[3] = (BYTE) ((v + 127) / 2);
C'est pas épuisant à taper et on est assuré du bon résultat.
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Personnellement je ne pense pas que gcc soit moins bon en optimisation que vc++.
Il y a des tonnes de flags qui peuvent jouer et tellement de choses peuvent influer sur le résultat du bench présent dans ta fonction "main".
Concernant le dépassement de l'opération, normalement ca passe correctement. ya.[3] + 127 fait plus que 255, oui, mais il n'est pas stocké, donc il se retrouve soit en registre, soit en pile, une fois divisé par 2, le nombre ne peux plus faire plus de 8 bits, et donc tiens sur un octet, et là il est stocké dans ya.c[3]. Pour en être absolument certain, tu peux caster.
Après, l'utilisation de ce tableau est surtout une facilité d'écriture du programme (plus simple qu'un masque), question perf ca doit jouer a peine, pas facile de vérifier. J'ai repris le code tel qu'il est actuellement et j'ai ajouté une seconde fonction en utilisant le tableau de char, chez moi, 6 fois sur 10, la fonction utilisant le char est plus rapide de quelques millisecondes, mais c'est pas non plus loins devant. Faudrait refaire le teste encore et encore pour savoir si en moyenne une fonction est plus rapide que l'autre. Le mieux étant de décompiler pour voir l'assembleur résultant et compter le nombre de cycles consommés. Une comparaison par appel de l'horloge ne fait que donner un ordre d'idée.
Si tu veux continuer a optimiser encore plus, il faut passer en assembleur surtout que chaque compilateur va donner un assembleur différent et donc des performances différentes (avec un compilateur une fonction sera plus rapide que l'autre, et ce sera l'inverse sur un autre compilateur). Mais bon, de toute façon tu n'atteindra pas le score de la fonction standard qui se contente d'utiliser l'instruction assembleur du coprocesseur mathématique ou de SSE2 et qui donc te sort le résultat en une seule instruction.
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

bon je viens de tester la vitesse et contrairement à mon attente l'utilisation des char augmente le temps d'exécution. mais bon gcc n'est pas forcement aussi bien que vc++ en terme d'optimisation.
mais en y repensant ca ne devrait même pas marcher car l'opération ya.c[3] = (ya.c[3] + 127) / 2 dépasse le plus grand nombre sur 1 octet : 255...
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Oui oui, on s'en tamponne du signe, je l'ai conservé uniquement pour la pédagogie. C'était un bit de perdu lors du déplacement binaire du coup je préférai montrer comment le conserver et le restaurer. Mais je suis d'accord, vu que c'est une racine carrée le signe est forcément positif, donc 0, or ce sont des 0 qui sont insérés dans les décalages. (Encore que, je crois me souvenir que quand tu décales, le dernier bit sorti est posé dans un flag de retenu et est ré-inséré si tu re-décale dans l'autre sens, mais je suis pas catégorique la dessus, ca demande teste)
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

okay. ya.i=*(int*)&x; est quelque chose auquel j'aurais du penser à la première version du code (évitant ainsi le memcpy) donc quand enfin ca m'est venu je l'ai mis sans réfléchir, effectivement autant faire simple ^^.
ton code parfait (j'étais en train de faire de même pour comparer la vitesse d'exécution)
à ceci près que le problème du signe est trivial, s'agissant d'une racine carrée ;)
mais bon du coup c'est plus très pédagogique pour les opérations binaire :)

en tous cas ça fait plaisir de pas coder tout seul :D... bon passons à autre chose
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Oui je trouve aussi pour l'édition des commentaires.
Sinon, je comprend pas pourquoi tu fais "ya.i=*(int*)&x;" au lieu de "ya.f = x;" comme je te l'avais indiqué ?
Parce que la tu tapes ca place un pointeur dans la pile qui pointe sur x, pour après faire un dé-référencement pour obtenir la valeur, alors que l'union te permet de placer la valeur directement.
De plus, comme je l'indiquais dans mon commentaire, mettre un tableau de 4 char ca te permet d'accèder aux paquets de 8bits et donc directement à l'exposant sans avoir besoin de faire mumuse avec les masques binaires.
u_int signe = ya.i & 0x80000000; // Sauvegarde le signe
ya.i = ya.i << 1; // Décale l'exposant de 1 vers la gauche plutot que 23 vers la droite
ya.c[3] = (ya.c[3] + 127) / 2; // opération sur char donc pas de masque ca sortira pas du char
ya.i = ya.i >> 1; // On replace le tout comme c'était
ya.i = ya.i | signe; // On remet le signe
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

merci pour l'info sur les champs de bit encore quelque chose que j'ignorais.

autre chose, c'est dommage de pas pouvoir éditer ses commentaires...
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

XD merci on est arrivé aux deux mêmes conclusions ^^
si quelqu'un a plus d'idée en restant en c (par exemple utilisant des astuces mathématiques)
je pense que cet article :
http://www.azillionmonkeys.com/qed/sqroot.html
permet de clore le sujet, tout y est (c'est Quake 3 Arena qui gagne ^^ IMPRESSIVE!).

a++
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Vu que tu utilises maintenant une union, autant vraiment l'utiliser :
memcpy(&ya.i, &x, 4);
a remplacer par
ya.f = x;
Ca te fait un appel de fonction en moins, et plus besoin de passer par les adresses des variables.
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Question optimisation tu peux faire plusieurs choses.
Déjà, je trouve plus simple de décaler de 1 vers la gauche, que de 23 vers la droite, tu n'as bit de signe a sauvegarder.
Ensuite, faire un union float/int te permet d'agir sur les deux sans avoir a utiliser memcpy (donc pas d'appel de fonction).
L'utilisation de pointeurs également (poser un int* sur ton float te permet de faire des décalages binaires sans avoir a dupliquer la mémoire).
En faisant une union float/int/char[4] ca te permet d'initialiser via la float, de décaler de 1 vers la gauche via le int, d'obtenir d'exposant via le char[3] (ou char[0] sur certaines plateforme). Ca t'évites toutes les allocations temporaires.
On pourrais également utiliser un champs de bit pour accéder directement aux parties qui nous intéressent.
struct sFloat
{
unsigned int _signe:1;
unsigned int _exposant:8;
unsigned int _mantisse:23;
};
L'utilisation du mot "register" permet d'utiliser directement un registre et donc d'éviter les déplacement mémoire<->registre, mais ca ne se verra pas en mode débug. Passer la fonction en fonction inline boostera aussi quelque peu les perfs, mais idem, ca ne se verra pas en mode débug.
La différence entre la fonction sqrt et la tienne c'est que la sqrt est compilée en utilisant les options d'optimisation du compilateur, si la tienne l'étais aussi il n'y aurait pas une telle différence (bien que je pense que la fonction standard reste bien plus rapide). Le problème est que si tu actives les optimisations, l'optimiseur verra que tes boucles ne font rien (puisque leurs résultat n'est pas utilisé) et donc supprimera la boucle (en tout cas celui de Visual Studio le fait, même si je fait une boucle for de 4 000 000 000, ca prend toujours 0ms quelle que soit la méthode).
Après, quand on veux vraiment faire de l'optimisation faut se tourner vers l'assembleur en étudiant bien la documentation.
Petits exemple :
Mettre 0 dans un registre se fait "mov eax,0" mais "xor eax,eax" donne le même résultat avec 1 cycle de moins. Diviser par deux un entier c'est un décalage de 1bit vers la droite (attention a la perte du reste de la division).
Du coup, en assembleur il existe plusieurs façon de faire les choses, et la méthode la plus rapide n'est pas la même sur toute les plateformes.

PS : le temps d'écrire ce message je vois que tu a trouvé la technique des unions tout seul ^^
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

oui je cherche toujours à optimiser ce code, je pensais utiliser le type de déclaration register int / register float, mais ca ne donne rien.
j'ai cependant trouver une optimisation (MAJ)
en ce qui concerne les optimisations que suggérait ton premier commentaire?
Messages postés
473
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015

Pour les registres processeurs, il servent d'arguments et de résultat d'instructions processeur.
Il faut donc récupérer la doc de ton processeur, retrouver l'instruction qui fait la racine carrée et lui passer les bons arguments. Tu bénéficieras dans ce contexte de l'algorithme du processeur.
Cependant, nous perdrions ici l'interêt de ton code qui est de présenter la façon de calculer une racine carrée et la structure des réels en mémoire. Même si ton algorithme est moins rapide que le processeur, il n'en reste pas moins interressant dans une optique de formation.
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

il doit être possible d'utiliser les registres processeur non ?
Messages postés
68
Date d'inscription
dimanche 31 mars 2002
Statut
Membre
Dernière intervention
18 janvier 2010

BruNews>merci ! j'avais lu que "certains" CPU avaient la fonction intégrée mais je ne pensais pas que c'était général cela explique la vitesse d'exécution. Tanpis j'aurais essayé ^^.
Warny>c'est exactement ce que je cherche, optimiser les calculs. j'ai fait mon maximum mais dis moi vite comment faire mieux!
Messages postés
473
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015

Si on excepte le fait que ton code n'optimise pas les calculs, il n'n reste pas moins un bon tutoriel sur la manipulation en mémoire des nombres réels. A défaut d'utiliser le code un jour, il m'a appris plein de trucs.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
28
Pour info:
Intel publiait cette version en optmisé (ASM) et la livrait incluse dans sa bibili AMATH.
Comme ça fait un bon moment que tous les PCs ont au moins un CPU équipé de SSE2, on fait 4 racines carrées en 1 seule instruction:
sqrtps xmm1, xmm2
Ce qui fait que toutes ces méthodes n'ont plus cours.