Voici une bibliothèque
mathématique écrite en C spécialement adaptée aux microcontrôleurs de
la famille Microchip. Elle a été développée afin d'être compatible avec
le logiciel C18 mais peut tout aussi bien être reprise pour un autre
compilateur. La présente page a pour but d'en décrire les principes.
|
|
oContraintes
de développement |
|
Lorsque vous développez sur microcontrôleur, vous
avez des contraintes que vous devez prendre en compte par rapport à
un système informatique traditionnel. Vous devez optimiser vos bibliothèques
en fonction du microcontrôleur utilisé mais aussi du compilateur afin
de réduire le temps d'éxecution d'une fonction.
Ces contraintes sont alors
les suivantes:
- Le jeu d'instruction. La plupart des PICS effectue des opérations sur des entiers de 8 bits
mais pas en virgule flottante. Ce qui signifie que toute opération de base (+,-,x,/) sur des
nombres réels devra être effectuée logiciellement, à partir de ce jeu d'instruction. Cela a
un coût en temps, surtout vis à vis de la division dont on s'abstiendra d'utiliser le plus possible.
- Les ressources mémoires (notament en ROM). Un PIC n'est pas un PC... Lorsque vous voulez calculer
une fonction, vous avez un compromis à faire entre le temps de calcul, la précision du résultat
et l'espace mémoire. Par exemple, la manière la plus rapide serait de constituer en ROM
d'une table. Vous vous pointez dans votre tableau à l'aide du nombre dont vous désirez connaître
la fonction, et vous obtenez directement votre résultat. A supposer que vous fassiez des calculs en simple
précision, vous devez avoir un tableau de 232 cases, ce qui n'est actuellement pas possible.
Donc, soit vous réduisez cette table et vous perdez en précision, soit vous effectuez des calculs,
et vous perdez en temps.
- Le format flottant. Sur le logiciel C18, la version de base ne comprend que le format flottant
simple précision. Donc, il ne faut pas vous attendre à des précisions de folie. Ce n'est pas conçu
pour faire des calculs poussés...
|
|
oPrincipes adoptés
|
|
Les principes utilisés sont donc les suivants:
- Calcul de chaque fonction par une formule approchée. Une méthode qui se prête bien à ce genre
de calcul est l'interpolation pôlynômiale, à condition que la fonction n'admette pas de branche
asymptotique. On verra plus loin comment déterminer le pôlynôme optimal.
- Réduction de l'intervalle dans lequel la fonction sera interpolée. Plus cet intervalle sera
petit, plus vous gagnerez en précision.
- Evitez la division. Ainsi, si un nombre doit être divisé par une constante, multipliez le par
la constante inverse.
|
|
oUn peu de mathématique
|
|
Lorsque vous faîtes du calcul du numérique, vous avez deux types d'erreurs:
- Les erreurs d'arrondi et de troncature. Ces erreurs sont dûes à
la formalisation du nombre (1/3 » 0.333333...).
- Les erreurs de methodes. Par exemple la dérivée numérique d'une
fonction peut être calculée par
f¢(x)=limh® 0[(f(x+h)-f(x))/h] avec h petit. Ce calcul va engendrer une erreur vis à vis de
la véritable dérivée.
Lorsque vous allez calculer vos fonctions, il va falloir prendre en compte ces erreurs de manière
théorique ou ,ce qui est souvent le cas pour les erreurs d'arrondis, de manière pratique.
Dans les sections qui vont suivre, nous ne ferons aucune démonstration
des formules. De même, nous ne montrons pas comment sont calculés les
coefficients du pôlynôme interpolateur. Nous laissons les lecteurs se
référer aux manuels de mathématique (pôlynôme interpolateur de Lagrange,
methode aux différences divisées,etc...).
Les pôlynômes interpolateurs optimaux
Les pôlynômes interpolateurs sont utilisés pour calculer une fonction
de manière approchée. C'est une méthode simple à mettre en oeuvre car
elle n'utilise que des opérations d'additions, soustractions et multiplications
sur des nombres réels.
Ainsi, on montre que l'erreur de méthode engendrée par un pôlynôme interpolateur est majorée par:
| |
|
|
||f (n)||¥
n!
|
| Q(x) | ; Q(x)= |
n-1 Õ
i=0
|
(x-ai) |
| |
|
avec f la fonction à interpoler, P le pôlynôme interpolateur de degrés
n-1, et ai les points d'interpolation.
On va alors se retrouver avec un problème d'optimisation: comment minimiser
cette erreur? Vous vous rendez compte que cette dernière dépend de la
fonction à interpoler (mais bon, ça vous n'y pouvez rien). Elle va dépendre
aussi du degrés du pôlynôme interpolateur, mais le plus important, des
points d'interpolation ai de la fonction : ces points ne doivent
pas, comme on pourrait l'imaginer, être équidistant.
On montre alors que l'erreur est minimale sur l'intervalle [a,b] si Q
est le pôlynôme de Chebychev, c-a-d si les ai sont les racines
de ce pôlynôme. Soit:
| |
|
|
(b-a)n
22n-1
|
cos[n arccos( |
2
b-a
|
x- |
b+a
b-a
|
)] |
| |
| |
|
|
b-a
2
|
cos[ |
(2i+1)p
2n
|
]+ |
b+a
2
|
|
| |
|
L'analyse du graphique nous montre que:
- approximer la fonction par son développement limité nous envoi rapidement
dans les choux.
- par comparaison, l'erreur engendrée par le pôlynôme interpolateur à
points équidistants est beaucoup moins importante sur l'intervalle [-Log
2, 0.5] que celle engendrée par le pôlynôme à points de Chebychev. Par
contre, elle croît très fortement sur l'intervalle [0.5 , Log 2] (phénomène
de Runge).
La méthode d'Horner
C'est une méthode utilisée pour calculer un pôlynôme. Elle est basée sur la représentation suivante:
|
|
|
a0+
x ( a1 + x (...( an-2+ x ( an-1+ x an ))...)) |
|
|
|
L'avantage est qu'elle n'effectue que n additions et n multiplications.
|
|
oTest
|
|
La bibliothèque a été simulé par Julien des Fribottes (merci Julien) pour
un PIC 18F452 à 40MHz à l'aide du compilateur C18. Les résultats en temps
de calcul sont les suivants:
sin(1) : | 4057 instructions (406µs) |
cos(1) : | 4280 instructions (428µs) |
tan(0.1) : | 7760 instructions (776µs) |
atan(0.1) : | 3180 instructions (318µs) |
exp(4) : | 3667 instructions (367µs) |
log(110) : | 3510 instructions (351µs) |
log10(110): | 3685 instructions (368µs) |
pow(5,6.5): | 7585 instructions (758µs) |
sqrt(1000): | 3116 instructions (312µs) |
|
|
oParamètres configurables
|
|
Les nombres réels sont mis au format flottant (c-a-d de la forme ±m 2b). Parfois, il est utile de connaître la valeur de l'exposant
b de ce nombre flottant (par exemple pour réduire l'intervalle d'une racine
carrée). Vous devez donc opérer physiquement sur ce format. Le problème
est que chaque compilateur a son format flottant propre. Donc si vous
voulez adapter cette bibliothèque à un autre compilateur, vous devrez
configurer les paramètres suivants:
- exp_pos: |
Position de l'octet exposant dans le nombre flottant |
- exp_offset: |
Valeur de l'exposant nul |
- exp_lo_min: |
Valeur minimal de l'exposant négatif |
- exp_hi_max: |
Valeur maximal de l'exposant positif |
- returnINF_LO(void): |
Valeur -¥ |
- returnINF_HI(void): |
Valeur +¥ |
- returnINF_NAN(void): |
Valeur Not A Number |
|
|
oQuelques
liens |
|
La
Bibliothèque mathématique |
Fiche
technique : "Débutez avec les PICs" |
Banque
de donnée technique du site Fribotte |
Microchip |
|
oContact |
|
Pour toutes questions envoyer moi un
mail: Sylvain |
|