Cosinus minimaliste et rapide ?

Bonjour.

Je cherche une implémentation du cosinus qui soit vraiment rapide à calculer (je devrais en appeler 10 toutes les milisecondes sur un 24 Mhz avec d'autres tâches qui tournent), mais seulement pour de petites variations autour d'un angle

Edit: la partie en italique n'est plus vallable.
J'ai trouvé [ame="http://www.devmaster.net/forums/showthread.php?t=5784"]cette implémentation[/ame] qui semble adéquate, mais je dois avouer que je ne suis pas sûr de savoir comment utiliser le code assembleur, le mettre dans un asm() étant insuffisant. (faudrais connaitre l'état de mes registres itout itout.)

Si vous pouviez m'aider sur ce point ou me fournir une autre implémentation.

Merci

Cordialement

Si ce sont des cosinus de valeurs discrètes (genre, un pas de X degrés), je recommanderais une table.

Idem, une table précalculée avec un nombre d'entrées suffisant pour ton besoin me semble largement préférable, et de loin la plus rapide des méthodes. Elle n'a comme seul inconvénient que la taille que ça prends en mémoire : pour un cercle divisé en 256 parties (donc, précision de 1.4°), ça bouffe quand même un kilo-octet minimum...

Pour ma part, j'utilise en général des tables de 4096 entrées (précision d'environ 0.08°, donc) sur des doubles, donc 32 ko au total... Sous DOS, je me limitais à des tables de 512 entrées de floats (donc, 2 ko, précision d'environ 0.7°).

j'y ai pensé, mais avec mes 2Ko de ram (et 32 de flash), je ne suis pas sûr de pourvoir me permettre ce genre de chose...(et d'autre part, je comptais utiliser ce petit cos en parallèle avec le standart..) en gros, mon angle a dans les 12 500 valeurs possible, mais je n'ai besoin du fast cos que pour des petites variation autour d'un angle (du genre +-8/12500).
en y réfléchissant, le solution que j'ai regardé ne convient pas non plus. L'idéal, serait de pouvoir relancer la suite du cosinus à partir d'un angle donné ... (je sais pas si c'est possible). Le but étant dobtenir l'équivalent x, y de ces petites variations.


Merci

Dans ce cas, il te faudrait plutôt une suite / série convergente vers cos(x), que tu initialiserais avec une valeur "proche" de façon à accélérer la convergence... Reste à trouver cette suite ! Peut-être demander dans le forum algos / maths ?

J'ai bien vu un truc dans le genre (DL du cosinus), mais la suite implique un calcul de factorielle (8O), donc laisse tomber sur ton µC : ça le mettrait à genoux... Sauf à précalculer quelques factorielles ? Ce serait toujours plus light que le précalcul des cosinus, après tout, et ça te permettrait de calculer un DL d'ordre 11... Faut juste regarder le niveau de précision que ça donne, et si cela apporte un gain par rapport à l'algo de cosinus que tu as déjà.


Autre possibilité : comment as-tu l'angle dont il faut calculer le cosinus ? Parce que tu pourrais peut-être utiliser les propriétés du triangle rectangle, si jamais tu as des coordonnées dans un plan/espace...

Il y a de bonnes approximations par des polynomes de degré assez faible (6 ou 8) dans Handbook of Mathematical Functions d'Abramowitz et Stegun, dis moi si tu n'as pas ce livre, je l'ai à la maison, je copierai les formules ce soir. De mémoire, l'approximation au degré 4 donne 3 ou 4 décimales, celle au degré 6 deux de plus (et comme le développement est pair, tu n'as pas beaucoup de multiplication).

Pour bien les utiliser, il faut se limiter à l'intervalle 0, PI/4 (après, les approximations polynomiales convergent affreusement lentement). Donc si x est entre -PI/4 et PI/4, tu prends une approximation de cosinus, si tu es entre PI/4 et PI/2 tu prends sin(PI/2-x), et ailleurs tu te ramènes a l'intervalle précédent par congruence et symétrie.

L'alternative aux polynomes, c'est CORDIC, utilisée par la plupart des calculettes.
[ame]http://en.wikipedia.org/wiki/CORDIC[/ame]


Enfin, le calcul autour d'un angle, oui c'est possible : tu écris le développement limité en une valeur, et tu tronques la série de Taylor correspondante (@MacLak, les factorielles, elles n'apparaissent que dans le calcul des coefficients, qui sont toujours les mêmes, dans l'implémentation pratique, on les précalcule)

Francois

Citation:

---

Envoyé par Mac LAK

Autre possibilité : comment as-tu l'angle dont il faut calculer le cosinus ? Parce que tu pourrais peut-être utiliser les propriétés du triangle rectangle, si jamais tu as des coordonnées dans un plan/espace...

---

L'angle principal est obtenu par triangulation sur des coordonées x,y converties en polaires.
Or après orientation selon cet angle, mon système se déplace théoriquement en ligne droite jusqu'au point d'arrivée en enregistrant en temps réel son angle et son "avancement" (paramètre rho).
En réalité, il subit de petites variations en angle au cours de sa trajectoire qui sont très vite corrigées mais qui entraînent irrémédiablement un décalage par rapport à la position finale théorique.
Je cherche à calculer les erreurs de trajectoire qui se cumuleraient lors de ce déplacement...
Or le faire à l'aide de calculs impliquant des cosinus normaux me fait perdre le coté "temps réel"...

Citation:

---

Envoyé par fcharton

Enfin, le calcul autour d'un angle, oui c'est possible : tu écris le développement limité en une valeur, et tu tronques la série de Taylor correspondante (@MacLak, les factorielles, elles n'apparaissent que dans le calcul des coefficients, qui sont toujours les mêmes, dans l'implémentation pratique, on les précalcule)

---

Je vais regarder de ce coté là (et ressortir mon formulaire de prépa :p), mais il me semblais que d'autres suites (qui convergent notamment plus rapidement) que la série de taylor permettaient de faire ce calcul...
Sinon, pour ce qui est des tables, j'ai toujours le problème de cette mémoire limitée... enfin je peux essayer de passer ça dans la flash (à grands coups de define (ou peut être de const, mais pas sûr) ) , mais même comme ça, c'est dur...

Pour ta première proposition, il ne faut pas tenir compte de ce que j'ai dis dans le premier post : il me faut en fait pas mal de décimales, mais variant autour d'une valeur connue (calculée avec le cosinus normal).

Sinon, je vais aussi poster un thread dans la partie algorithmie pour un aspect plus mathématique...


Merci :)

Citation:

---

L'idéal, serait de pouvoir relancer la suite du cosinus à partir d'un angle donné ... (je sais pas si c'est possible). Le but étant dobtenir l'équivalent x, y de ces petites variations.

---

1- Si on a aussi le sinus (sinon, on peut l'obtenir au prix du calcul d'une racine carrée), il suffit de partir de l'identité

Citation:

---

cos(A+a) = cos(A)cos(a) - sin(A)sin(a)

---

Si a est petit, on peut utiliser un développement limité pour le calcul de cos(a) et sin(a)

2- Autre approche possible, tabuler très partiellement cos et sin et interpoler en utilisant la formule ci-dessus :

Avec deux tables ayant chacune 9 éléments et contenant les valeurs de cos(theta) et sin(theta) pour theta multiple de PHI = PI/16 (donc allant des angles 0 à PI/2 inclus) et en interpolant à l'ordre 3, on obtient une erreur inférieure à 0.00001. En interpolant à l'ordre 4, l'erreur est inférieure à 0.000001.
Par exemple, à l'ordre 3 :

Code:

---

1 2 3 4 5 6 7

double my_cos(double angle) // angle en radians compris entre 0 et PI/2(+PI/32) { unsigned int n = angle/PHI + 0.5; double xangle = angle - n*PHI ; double xangle2 = xangle*xangle/2.0; return tcos[n]*(1-xangle2)-tsin[n]*xangle*(1-xangle2/3); }

---

Citation:

---

Envoyé par diogene

1- Si on a aussi le sinus (sinon, on peut l'obtenir au prix du calcul d'une racine carrée), il suffit de partir de l'identité

---

pas sûr que ce soit plus court que le calcul du cos...

Citation:

---

Envoyé par diogene

2- Autre approche possible, tabuler très partiellement cos et sin et interpoler en utilisant la formule ci-dessus :

Avec deux tables ayant chacune 9 éléments et contenant les valeurs de cos(theta) et sin(theta) pour theta multiple de PHI = PI/16 (donc allant des angles 0 à PI/2 inclus) et en interpolant à l'ordre 3, on obtient une erreur inférieure à 0.00001. En interpolant à l'ordre 4, l'erreur est inférieure à 0.000001.
Par exemple, à l'ordre 3 :

Code:

---

1 2 3 4 5 6 7

double my_cos(double angle) // angle en radians compris entre 0 et PI/2(+PI/32) { unsigned int n = angle/PHI + 0.5; double xangle = angle - n*PHI ; double xangle2 = xangle*xangle/2.0; return tcos[n]*(1-xangle2)-tsin[n]*xangle*(1-xangle2/3); }

---

---

hmm, je suis désolé , je dois partir ce soir, :?
... mais promi, je lirais tout en détail demain (avec l'esprit au clair).

sinon, j'ai aussi créé une discussion sur le forum algorithmie.

Merci beaucoup.

Citation:

---

Envoyé par méphistopheles

L'angle principal est obtenu par triangulation sur des coordonées x,y converties en polaires.

---

Heu... Tu te rappelles que dans le triangle rectangle en C (AB=hypothénuse), on a l'égalité suivante : cos(A) = AB / AC ? ;)
Si tu as des coordonnées cartésiennes, tu peux donc avoir directement le cosinus, et ne pas te fader la conversion en coordonnées polaires...

Citation:

---

Envoyé par Mac LAK

Heu... Tu te rappelles que dans le triangle rectangle en C (AB=hypothénuse), on a l'égalité suivante : cos(A) = AB / AC ? ;)
Si tu as des coordonnées cartésiennes, tu peux donc avoir directement le cosinus, et ne pas te fader la conversion en coordonnées polaires...

---

oui, mais en réalité, le système s'oriente selon cet angle (puisqu'il peut le mesurer) puis avance en "ligne droite". Le problème est que je ne sais pas déduire cos(a+epsilon)...

Sinon diogene, je vais finalement également avoir besoin du sinus.... sachant que je peux aussi calculer sa valeur à l'angle principal pour ensuite me charger des petites variations....

Par contre, la seconde méthode ne semble pas profiter de mes petites variations... et surtout, je ne suis pas sûr qu'elle soit suffisante pour la précision que j'ai.

Je vais éditer le premier post pour plus de clarté.

Merci ;)

Citation:

---

Envoyé par méphistopheles

oui, mais en réalité, le système s'oriente selon cet angle (puisqu'il peut le mesurer) puis avance en "ligne droite".

---

Arf... Effectivement, dommage, ça aurait été simple pourtant.

Citation:

---

Envoyé par méphistopheles

Je vais regarder de ce coté là (et ressortir mon formulaire de prépa :p), mais il me semblais que d'autres suites (qui convergent notamment plus rapidement) que la série de taylor permettaient de faire ce calcul...

---

Pour une légère amélioration de Taylor, sur les fonctions circulaires, tu peux regarder du côté des polynomes de Tchebicheff. (mais dis toi bien que l'amélioration est marginale si ton intervalle est réduit)

Sur des algos de calcul local, la bonne méthode sera probablement Newton (quadratique et facile à calculer), il faut écrire les équations, appliquer la formule et programmer tout cela, normalement c'est quadratique...

Dans tous les cas, il est indispensable de réduire ton intervalle avant tout calcul : tu dois toujours rester entre 0 et PI/4 (<1). Mais regarde quand même les polynomes dérivés de Taylor : comme on est sur des fonctions paires (ou impaires pour le sinus), ca se calcule très vite...

Francois