ce serais cool

il suffit d'utiliser les méthodes d'approximation des racines carrées, bon ça te sert pas à grand chose, mais sans tu y arriveras pas  

autant faire une omelette sans oeufs ...
 
dans quake3, il y a une source de racine carrée _très très_ rapide, sans table, juste qq instructions. je l'ai pas sous les yeux par contre ...

qu'est ce qui peux bien t'empecher d'utiliser les recine carré ?

ben sinon, tu considère le pb comme non linéaire et aprés : algo génétiques, recuit simulé, méthode dde Vigne; etc...
 
 

s'ils sont sur une feuille de papier, emploie une latte  
 
 
désolé

 
L'optimisation !
Les racines carrées elles sont gentilles mais ça bouffe du temps CPU comme animal.
C'est pour un simulateur de gravitation... mon fichier d'exemple contient 260 corps, donc ça fait 260² racines à chaque fois (260^4 si j'active la gestion des collisions...).
Sans la gestion des collisions, ça tourne à ~72fps (affichage en OpenGL), avec : ~50fps... MAIS ça c'est sur MA machine, un Duron 1Ghz + gf2mx oc... Chez un pote, c'est plus près de 2-3fps (K6 300 + TNT)...
 
 
youdontcare > où ça dans q3 ?!

http://trucsmaths.free.fr/js_racine.htm
 
Voilà pour la méthode traditionnelle. L'auteur du site fournit un exemple en javascript (visualise le source de la page pour le voir) de cette méthode, script que tu pourras adapter dans ton langage préféré.
Je ne suis pas sur cependant que celà soit la méthode la plus rapide.  
A+

euh... réponse bête tu y as surement pensé mais okazou...
 
As-tu toujours besoin d'extraire les racines carrées... la plupart du temps on peut faire la meme chose avec les carrés des distances... notamment pour le calcul des forces de gravitation.
Les carrés conservent également la monotonie.

un p'tit coup d'AN,
 
Yn+1 = (Yn + X/Yn)/2 pour n=0,1,2,
 
basé sur la méthode d'apporximation asymptotique de Newton.  
 
Interet de la méthode : L'odre de complexité vaut 2, soit le nombre de décimale déterminant la précision douuble a chaque itération
 
Problème de cette méthode :  
 
- détermination de Y0, il faut qu'il soit le plus proche possible de la racine de X. sinon ça peut mouliner au début (rem : c'est d'ailleur le prob générale de la méthode de Newton, sacré farceur celui-la )
 
- Les divisions. il y en a 2 : /Yn et /2. Pour le /Yn on peut transformer la solution en X*(Racine(X)/X) ou (Racine(X)/X) peut s'exprimer sans la division /Yn. Pour le /2 ben faut voir.
 
Cette formule est particulièrement efficace avec des entiers, donc a tester pour les flottants.
 
En pratique on détermine YO en fonction des condition de dapert qu'impose le problème dans lequel on utilise cette formule, donc a doit de voir, sinon l'approximation en base est Y0 = 2^E(m/2) ou m représente la taille en bit repésentant le nombre X.
 
Exemple pour 5 vaut en base 2 : 101 soit m = 3 donc Y0 = 2
 
 
Ah je crois que quand j'ai chassé PI j'avais une fonction d'approximation du nombre de bit en décimale, je cherche ça et je reviens

Bonne réponse de tgrx !!!
la force de graviatation entre deux corps étant k*m*m'/d*d
Il n'y a pas besoin d'extraire la racine carrée

bon,
 
en fait 1 decimale vaut environ 30/9 bits. Donc pour une approximation de Y0 avec 5609 4*30/9 = 13,333... soit Y0 = 2^E(13,333/2) = 2^6 = 64. Mais bon avec 1000 ça ne parche pas très bien donc je te conseille plutot de faire (N-1)*30/9 ou N est le nombre de décimale. Charge a toi de toruver un moyen de détemriner rapidement le nombre de décimal pour un chiffres.
 
Mais au fait tu peux accéder a l'exposant de la mantisse, non ? bon ben t'as ton m.

bon,
 
ben je remballe

je ne sais plus. cherche. j'ai juste un copié collé :
 
__asm {
  mov eax, square
  sub eax, 0x3F800000
  sar eax, 1
  add eax, 0x3F800000
  mov [retval], eax
}
 
y'a moyen de rajouter des itérations supplémentaires pour améliorer la précision. => cherche dans la source.

Voilà la fonction de calcul des accélérations
 
void calcAccCorps3d(TypCorps* C1, const TypCorps* C2) {
 double dx;
 double dy;
 double dz;
 double a;
 double d;
 double d2;
 double c;
 dx = C2->X - C1->X;
 dy = C2->Y - C1->Y;
 dz = C2->Z - C1->Z;
 d2 = sq(dx) + sq(dy) + sq(dz);
 d = sqrt(d2);
 a = (double) G*(C2->M/d2);
 c = (double)a/(double)d;
 C1->AX += dx * c;
 C1->AY += dy * c;
 C1->AZ += dz * c;
}
 
void calcPositions3d(const int n, TypCorps* tb) {
 int i;
 for (i=n ; i-- {
  tb[i].VX += tb[i].AX;
  tb[i].VY += tb[i].AY;
  tb[i].VZ += tb[i].AZ;
  tb[i].X += tb[i].VX;
  tb[i].Y += tb[i].VY;
  tb[i].Z += tb[i].VZ;
  tb[i].AX = 0;
  tb[i].AY = 0;
  tb[i].AZ = 0;
 }
}
 
les sources complètes sont la si ça vous interrèsse: http://cycojesus.ctw.net/files/openglavity_v0.6.0.zip (~845 Ko)
 
tgrx > pas bète, a voir...
 
Barbarella > wow !!

ah,
 
le casting de float a double peut parfois couter cher. essaie juste ton prog en mettant tout en double, ça doit pas être long a faire. et puis els prog travaille avec les même registre en float et double c'st seulement le temps de calcul sur certain ope qui change comme la division ou la SQR

bon,
 
j'ai un peu cogité sur ton code, pour la premier fonc pas trop d'idée, pour la seconde j'écrirais le code comme ça
 
void calcPositions3d(const int n, TypCorps* tb) {  
int i;  
for (i=n ; i--   {  
 tb[i].VX += tb[i].AX;  
 tb[i].X  += tb[i].VX;  
 tb[i].AX  = 0;  
 
 tb[i].VY += tb[i].AY;  
 tb[i].Y  += tb[i].VY;  
 tb[i].AY  = 0;  
 
 tb[i].VZ += tb[i].AZ;  
 tb[i].Z  += tb[i].VZ;  
 tb[i].AZ  = 0;  
}  
}  
 
en fait c'est une histoire de registre. en faisant un
 tb[i].VZ += tb[i].AZ;  
 tb[i].Z  += tb[i].VZ;  
 
le proc a toute les chances (si ton compilo n'est pas trop con) de conserver tb[i].VZ dans un registre au lieu de recalculer l'adresse  
 
Pour la mise a zero de AZ,AY,AX j'hésite entre comme je t'ai montré ou faire
 
....
 tb[i].VX += tb[i].AX;  
 tb[i].X  += tb[i].VX;  
 
 tb[i].VY += tb[i].AY;  
 tb[i].Y  += tb[i].VY;  
 
 tb[i].VZ += tb[i].AZ;  
 tb[i].Z  += tb[i].VZ;  
 
 tb[i].AX  =  tb[i].AZ  =  tb[i].AY  = 0;  
....
 
ça depend de ton compilo et de l'organisation de ta structure.
 
@++

au fait tu utilse quoi comme compilo ? t'as pensé a mettre l'alignement sur 8 word ? pour voir le résultat ?
 
Remarque : Les compilo recent gère bcp mieux l'alignment des données et donc optimise bcp mieux.

pour la première fonction,
 
j'ai fait ça vite fait, mais on peut supprimer des var dans la partie
 
d2 = sq(dx) + sq(dy) + sq(dz);  
d = sqrt(d2);  
a = (double) G*(C2->M/d2);  
c = (double)a/(double)d;  
 
 
1 sol :  
 
//d2 = sq(dx) + sq(dy) + sq(dz);  
d = sqrt(sq(dx) + sq(dy) + sq(dz));  
// a = (double) G*(C2->M/d2);  
c = (double)G * (C2->M / (d * d * d));  
 
interet : Supprime 2 affectations et vars et une division, heu ... mais c'est a vérifier si ça marche
 
2 sol : (plus soft )
 
d2 = sq(dx) + sq(dy) + sq(dz);  
d = sqrt(d2);  
//a = (double) G*(C2->M/d2);  
c = (double)G*(C2->M/d2)/(double)d;  
 
 
La raison de la sol 1 : a = b/c, d = a/e => d = b/c/e soit b/(c*e)  
 
 
Mais bon faut vérifier et même si mathématiquement c'est bon faut voir s'il y a perte de précision car il faut toujours se méfier de la précision lors de la réorganisation des opérations dans une fonction.

[edtdd]--Message édité par Barbarella--[/edtdd]

 
le pb viendrait plutot de ton Algo de gestion de collision non? en algo en O(x^4) ça restera long quoique tu mette dedans comme instruction t sur de pas pouvoir faire mieux (test de colision sélectif...   )

sombresonge a écrit a écrit :     le pb viendrait plutot de ton Algo de gestion de collision non? en algo en O(x^4) ça restera long quoique tu mette dedans comme instruction t sur de pas pouvoir faire mieux (test de colision sélectif...   )

tout à fait. regarder du côté du sweep & prune qui est en temps linéaire.

aussi, le 3dnow (ptet le sse aussi, j'en sais rien) permet de faire des approximations de racine carre...
Si vous n'avez pas besoin d'un truc hyper precis ca peut ptet etre interessant

il existe un algorithme assez rapide pour calculer une racine carrée :
soit A le nombre dont on veut la racine
la série : X(n+1)=1/2 (Xn + A/Xn)
converge très rapidement vers racine de A, quelque soit Xo > 0
 
Celà peut s'écrire assez facilement en assembleur pour des entiers. On peut choisir Xo en décalant vers la droite A, de la moitié du nombre de bits significatifs, et on se rapproche encore plus vite de la racine carrée.
 
A+

"converge très rapidement vers racine de A, quelque soit Xo > 0 "
 
c'est le même algo que j'ai donné , mais par contre cette affirmatione est fausse. C'est justement le hic des méthodes asymptotique. j'ai donné plus une méthode de détermination de Y0 (X0 chez toi).

-> Barbarella : j'avais mal lu ton topic, mais je ne suis pas d'accord avec toi sur la vitesse de convergence :
si on prend un entier de 32 bits par exemple 3 221 224 721, et comme Xo 49151 (les 16 bits de poids forts), il faut trois itérations pour obtenir 56755 alors que la racine est 56755,8.
 
Pour accélérer le calcul une division par 2 s'effectue en faisant un décalage vers la droite du nombre -> très rapide.
 
Un bon départ pour trouver Xo est :
Si A comporte n bits significatifs, de prendre les n/2 bits de gauche. Celà limitera le nombre de divisions. pour trouver n, qq décalages vers la droite seront suffisants (rapide en assembleur).
 
Celà va de soi que le calcul le plus rapide sera effectué avec des entiers.
 
A+

Le seul désaccord que j'avais avec toi c'était ton affirmation que ça conbverge vite pour tout X0 > 0. Mais comme t'as changé d'idée "Un bon départ pour trouver Xo est : ...."
 
Pour la vitesse de convergence en général pour cette forumle ou est notre désaccord ?

-> Barbarella
Je crois qu'on s'était mal compris l'un et l'autre. Ah les topics que l'on lit trop vite (surtout moi !!!).
je crois que cycojesus a une solution. A lui de coder maintenant
A+

Merci, je vais voir ça ce soir...