[DEV-C++] CALCUL DE LA RACINE CARRÉE D'UN RÉEL
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
21 janv. 2010 à 23:00
ctx_man Messages postés 285 Date d'inscription mardi 28 décembre 2004 Statut Membre Dernière intervention 20 janvier 2013 - 26 janv. 2010 à 14:19
ctx_man Messages postés 285 Date d'inscription mardi 28 décembre 2004 Statut Membre Dernière intervention 20 janvier 2013 - 26 janv. 2010 à 14:19
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
https://codes-sources.commentcamarche.net/source/51157-dev-c-calcul-de-la-racine-carree-d-un-reel
26 janv. 2010 à 14:19
26 janv. 2010 à 13:18
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.
26 janv. 2010 à 11:44
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.
25 janv. 2010 à 18:05
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...
25 janv. 2010 à 16:38
25 janv. 2010 à 16:32
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
25 janv. 2010 à 16:22
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
25 janv. 2010 à 16:13
autre chose, c'est dommage de pas pouvoir éditer ses commentaires...
25 janv. 2010 à 16:10
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++
25 janv. 2010 à 15:20
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.
25 janv. 2010 à 15:15
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 ^^
25 janv. 2010 à 13:56
j'ai cependant trouver une optimisation (MAJ)
en ce qui concerne les optimisations que suggérait ton premier commentaire?
25 janv. 2010 à 10:48
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.
25 janv. 2010 à 08:44
25 janv. 2010 à 08:26
Warny>c'est exactement ce que je cherche, optimiser les calculs. j'ai fait mon maximum mais dis moi vite comment faire mieux!
22 janv. 2010 à 09:46
21 janv. 2010 à 23:00
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.