IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Cosinus minimaliste et rapide ?


Sujet :

C

  1. #1
    Membre éprouvé
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Points : 1 220
    Points
    1 220
    Par défaut 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
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  2. #2
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    Si ce sont des cosinus de valeurs discrètes (genre, un pas de X degrés), je recommanderais une table.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  3. #3
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    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°).
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  4. #4
    Membre éprouvé
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Points : 1 220
    Points
    1 220
    Par défaut
    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
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  5. #5
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    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 (), 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...
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  6. #6
    Invité
    Invité(e)
    Par défaut
    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

  7. #7
    Membre éprouvé
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Points : 1 220
    Points
    1 220
    Par défaut
    Citation Envoyé par Mac LAK Voir le message
    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 Voir le message
    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
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  8. #8
    Expert éminent sénior
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Points : 13 926
    Points
    13 926
    Par défaut
    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é

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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);
    }
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  9. #9
    Membre éprouvé
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Points : 1 220
    Points
    1 220
    Par défaut
    Citation Envoyé par diogene Voir le message
    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 Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  10. #10
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par méphistopheles Voir le message
    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...
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  11. #11
    Membre éprouvé
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Points : 1 220
    Points
    1 220
    Par défaut
    Citation Envoyé par Mac LAK Voir le message
    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
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  12. #12
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par méphistopheles Voir le message
    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.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  13. #13
    Invité
    Invité(e)
    Par défaut
    Citation Envoyé par méphistopheles Voir le message
    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

Discussions similaires

  1. Cosinus rapide pour petites variations autour d'un angle
    Par méphistopheles dans le forum Mathématiques
    Réponses: 3
    Dernier message: 17/02/2010, 15h10
  2. Calcul rapide de percentiles
    Par benj63 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 08/12/2006, 15h50
  3. LES TECHNIQUES DES SGBDR / MySQL rapide ???
    Par SQLpro dans le forum Langage SQL
    Réponses: 1
    Dernier message: 12/09/2003, 12h16
  4. Accés rapide aux propriétés d'un Objet
    Par Alacazam dans le forum C++Builder
    Réponses: 4
    Dernier message: 28/11/2002, 22h56
  5. [VBA Excel] Effacer rapidement une feuille
    Par Invité dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 24/10/2002, 14h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo