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

Commentaire de BruNews le 21/01/2010 23:00:25 administrateur CS

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.

Commentaire de Jhep le 25/01/2010 08:26:23

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!

Commentaire de Warny le 25/01/2010 10:48:20

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.

Commentaire de ctx_man le 25/01/2010 15:15:45

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 ^^

Commentaire de Jhep le 25/01/2010 16:10:17

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++

Commentaire de ctx_man le 25/01/2010 16:22:35

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

Commentaire de ctx_man le 25/01/2010 16:38:23

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)

Commentaire de ctx_man le 26/01/2010 11:44:17

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.