[Mini Tuto] Travailler en virgule fixe

Suite à discussions avec @skywodd du blog skyduino, qui parlait avec délectation des calculs en virgule fixe, j’ai décidé de faire un petit point sur le sujet pour montrer que c’est pas si difficile que ça.

Ce post va concerner le langage C.

A l’origine: la virgule flottante

En C, quand on veut traiter des nombres à virgule, on va utiliser des variables de type float ou double. Ces types de données gèrent les nombres à virgule avec une notation “signe-mantisse-exposant”, c’est à dire en format “scientifique. En maths on a plutot l’habitude des nombres en base 10, par exemple 1,27 x 10^3. En informatique, on utilise la base 2, c’est aussi le cas dans les float/double.

Quand le compilateur C rencontre des expressions flottantes, il y a 2 possibilités:

  • soit le CPU cible est équipé d’un FPU (floating point unit) matériel, et dans ce cas le compilateur peut générer des instructions assembleur qui font appel à ce fpu.
  • soit le CPU n’en est pas équipé, et les instructions correspondantes sont implémentées par de longues routines écrites en assembleur, pour gcc c’est libm qui s’en occupe. (thx Skywodd, pas libgcc)

Dans la plupart des micro-contrôleurs embarqués de type PIC ou AVR (ou même ARM non cortex M4) il n’y a pas de FPU, du coup les opérations en flottant, si elles sont supportées par le compilateur, sont à éviter pour des raisons de performances.

Problèmes en virgule flottante

Parfois on veut gérer directement des grandeurs physiques, comme quand on écrit le code pour un accéléromètre, un appareil de mesure de tension/courant, etc.

La méthode “triviale” est de passer en float.

Regardons le code suivant:

#define REF_VOLTAGE (float)5.0 //valeur de la tension de référence
#define CONV_MAX 2048 //valeur max de mesure pour un convertisseur 12 bits (exemple)

unsigned short conv = adc_read(); //lire le résultat de la conversion, c'est un entier

float voltage = conv / CONV_MAX * REF_VOLTAGE; //règle de trois!

//maintenant on a une tension

Ce code est mauvais : il commence par faire une division, puis une multiplication. Selon les compilateurs, ça peut être grave, car si CONV_MAX n’est pas converti en flottant, la division produira toujours un résultat zéro: Eh oui, le résultat de cette division sera toujours compris entre zéro et un! Nous pouvons apporter une correction pour éviter cela:

float voltage = conv / (float)CONV_MAX * REF_VOLTAGE;

C’est moins mauvais… Cette fois c’est la précision qui en prend un coup. L’erreur d’arrondi dûe à la précision limitée de la division va être multipliée par REF_VOLTAGE, le résultat sera peu précis. On peut faire mieux de cette manière:

float voltage = (float)(conv * REF_VOLTAGE) / (float)CONV_MAX;

Cette fois, on  va diviser un plus grand nombre, et les erreurs d’arrondis seront minimales.

Maintenant, étudions le problème des performances, en essayant de se passer des nombres flottants.

L’optimisation: la virgule fixe

Dans beaucoup de cas en informatique embarquée, on veut pouvoir gérer des nombres dont les variations sont limitées, c’est à dire qu’on n’a pas besoin de gérer des exposants très différents. C’est le cas par exemple lorsqu’on gère la tension issue d’un convertisseur analogique numérique.

Dans ce cas, le convertisseur va générer un nombre de quelques bits, par exemple 8 à 16 bits. Le résultat de la conversion est un entier, et la plupart du temps cette information suffit.

Remarquons que la plupart des nombres à virgules simples peuvent s’écrire comme une fraction. Évidemment ce n’est pas le cas de tous les nombres, mais dans le cadre de la précision limitée qui nous intéresse, c’est le cas. Exemple: 1,23 = 123/100

On peut décider de fixer ce dénominateur et de le rendre implicite: on ne l’écrit plus. Cela nous permet de travailler avec des entiers “plus grands”.

Si je choisis par exemple 100, tous les nombres ayant deux chiffres après la virgule peuvent s’écrire comme des entiers:

  • 1,23 => 123
  • 4,67 => 467
  • 1,5473 => 155

J’ai choisi une convention de virgule fixe à deux chiffres après la virgule, ce qui en réalité, signifie que je travaille avec des nombres 100 fois plus grands que la réalité.

Si on transpose ceci dans le domaine de l’informatique, il faut faire les choses intelligemment. On ne va plus utiliser des puissances de dix, mais des puissances de deux, car c’est le système naturel de comptage de l’ordinateur. L’avantage, c’est que les multiplications et les divisions se transforment en décalages. Exemples:

* pour multiplier par 16, je décale vers la gauche de 4 bits.
* pour diviser par 32, je décale vers la droite de 5 bits.

Avec cette idée, je ne vais plus utiliser des nombres ayant deux chiffres après la virgule, mais de nombres ayant N bits après la virgule. Pas de panique, ça veut dire qu’au lieu de multiplier mes valeurs par 10,100,1000, je vais les multiplier par 16,32,…1024, etc.

Cela ne change rien au résultat: cela veut juste dire que je travaille avec des valeurs N fois plus grandes que le résultat souhaité.

Dans la plupart des cas en embarqué, on va travailler avec des nombres à virgule fixe de 16 (short) ou 32 (long) bits.

On choisit ensuite le nombre de bits après la virgule. Cela permet de définir une grande quantité de formats:

  • le format 8.8 code les nombres sur 16 bits, avec un dénominateur de (1<<8) = 256, il reste 8 bits pour la partie entière, ce qui permet de coder les nombres de 0 à 255 avec une précision de 1/256, ou de -128 à 127 si on garde le signe
  • le format 12.4 permet de coder de 0 à 4095 (12 bits entiers) avec une précision de 1/16
  • etc… etc…

Donc 5,0 volts flottants, si je le traduis en entier ça fait 5 volts, en format 8.8 ça fait (5<<8)+0 = (5*256) = 1280, et en format 12.4, ça fait (5*16) = 80
Si vous lisez 80 en format 12.4, ça fait en réalité: (80/16) = 5

Calculs en virgule fixe

C’est le même principe que pour les fractions, et dans notre cas elles sont déja réduites au même dénominateur D, celui qu’on a choisi. Un nombre en virgule fixe s’écrit <quelque chose>/D.

L’addition et la soustraction sont triviales, c’est la même chose que pour les entiers:

a/D + b/D = (a+b)/D

Il suffit donc de faire la somme de deux nombres en virgule fixe pour retrouver un nombre en virgule fixe dans le même format, sans autre chose à faire.

Pour la multiplication:

a/D * b/D = (a*b)/(D*D)

mais j’ai besoin de fractions dans lequel le dénominateur est toujours D. Je peux réécrire ce résultat en divisant en haut et en bas par D, ce qui ne change pas le résultat:

(a*b)/(D*D) = (a*b/D)/(D*D/D) = (a*b/D)/D

Le résultat de la multiplication de a et b est donc (a*b/D). En pratique, cela veut dire que chaque fois que vous multipliez deux nombres en virgule fixe dans le même format, il faut diviser ensuite le résultat par D. Comme on a dit que D était une puissance de deux, ça revient à un décalage.

Division: (a/D) / (b/D) = (a/D) * (D/b) = a/b = (a*D/b) /D

Vous me suivez? Pour retrouver un nombre dans le bon format, il faut donc multiplier par D après la division. Normal, c’est le réciproque de la multiplication!

Pour la comparaison, rien à signaler, on peut le faire directement, ce format ne change pas l’ordre des nombres entiers: a/D < b/D si et seulement si a < b .

Pour transposer un nombre flottant (ou entier) en format à virgule fixe, il suffit de le multiplier par D.

Pour transformer un nombre à virgule fixe en format flottant (ou en entier), il suffit de le diviser par D.

Conclusion

J’espère que ce petit aperçu vous aura clarifié les idées. En résumé, il s’agit de :

  • Choisir un dénominateur D assez grand pour la précision que vous souhaitez, celle ci vaudra 1/D. Pour avoir un avantage, il faut que D soit une puissance de 2.
  • Multiplier tous les nombres à manipuler par D, cela se fait par décalage à gauche.
  • L’addition et la soustraction se font avec des opérations normales sur les entiers.
  • La multiplication se fait comme pour les entiers, on divise ensuite par D en décalant à droite.
  • La division a/b se fait en prémultipliant a par D, puis en faisant une simple division entière par b.
  • La comparaison se fait comme pour les entiers

Et c’est tout!