penser base 2

Dans la vie de tous les jours on utilise la base décimale et lorsqu'on fait de la programmation de haut niveau en général on continue à travailler avec la base décimale et parfois avec la base hexadécimale. Mais lorsqu'on travaille avec de petits micro-controlleurs il vaut mieux penser base 2. Dans cette chronique je vais expliquer le pourquoi et le comment de cette affirmation.

So tiny!

Les MCU atTiny ne s'appelle pas ainsi parce qu'ils sont physiquement petit, même s'ils peuvent l'être, mais parce que les ressources dont on dispose sur ces MCU sont vraiment limitées. l'atTiny13A par exemple avec son 1KB de mémoire flash ne permet vraiment pas d'utiliser les librairies 'C' complexes. Vous programmez en 'C' pour un atTiny13a et vous voulez faire une multiplication ou une division.

Faisons le test. Voici un petit programme qui fait des lectures analogiques et fait la moyenne de 20 échantillons pour éliminer les interférences, scénario classique.
/* * PenserBase2.c * * Created: 2013-02-25 19:03:24 * Author: Jacques * OBJET: démontrer comment réduire la taille du code en évitant l'utilisation des opérateurs arithmétique '*' et '/' */ #define F_CPU 9600000L // 9,6Mhz #define SAMPLES 20 #include <avr/io.h> uint16_t somme=0; uint8_t compte=0, moyenne; int main(void) { CLKPR= (1<<CLKPCE); // permet la modification du pre-scale CLKPR = 0 ; // pre-scale mise à zéro. Le MCU fonctionne à la fréquence maximale. ADMUX=3; // convertion analogue/numérique sur canal 3 Vref=Vcc ADCSRA = (1<<ADEN) | 7 ; // activation du convertisseur, CLKadc=CLKcpu/128 while(1) { ADCSRA |= 1<<ADSC; // débute une conversion; while (ADCSRA & (1<<ADSC)); // attend la find de la conversion. somme+= ADCL + (ADCH*256); compte++; if (compte==SAMPLES){ moyenne=somme/SAMPLES; somme -= moyenne; compte--; } } }
On compile et ont constate que ça prend 224 octets de mémoire flash. Voici une autre version de ce même programme sauf qu'au lieu de faire la moyenne de 20 échantillons on va la faire sur 16 échantillons et on va remplacer la division par un opérateur >>. /* * PenserBase2.c * * Created: 2013-02-25 19:03:24 * Author: Jacques * OBJET: démontrer comment réduire la taille du code en évitant l'utilisation des opérateurs arithmétique '*' et '/' */ #define F_CPU 9600000L // 9,6Mhz #define SAMPLES 16 #include <avr/io.h> uint16_t somme=0,moyenne; uint8_t compte=0; int main(void) { CLKPR= (1<<CLKPCE); // permet la modification du pre-scale CLKPR = 0 ; // pre-scale mise à zéro. Le MCU fonctionne à la fréquence maximale. ADMUX=3; // convertion analogue/numérique sur canal 3 Vref=Vcc ADCSRA = (1<<ADEN) | 7 ; // activation du convertisseur, CLKadc=CLKcpu/128 while(1) { ADCSRA |= 1<<ADSC; // débute une conversion; while (ADCSRA & (1<<ADSC)); // attend la find de la conversion. somme +=(ADCL + (ADCH<<8)); compte++; if (compte==SAMPLES){ moyenne=somme>>4; somme -= moyenne; compte--; } } }
Cette version prend 188 octets flash, un gain d'espace de 36 octets. En utilisant une puissance de 2 pour le nombre d'échantillons on peut remplacer la division par un décalage vers la droite de 4 positions ce qui équivaut à une division par 16. Toute multiplication par une puissance de 2 peut-être remplacée par un opérateur << avec le log2 du multiplicateur comme argument. Toute division par une puissance de 2 peut-être remplacée par un opérateur >> avec le log2 du diviseur. Non seulement le code prends moins d'espace mais l'exécution est plus rapide.

Il y a de nombreuses situations où il est judicieux de choisir des paramètres qui sont des puissances de 2 pour éviter une multiplication ou une division. C'est ce que j'appelle penser base 2. Un autre exemple est celui d'une interpolation linéaire entre 2 nombres. Au lieu de choisir un fraction décimale, on divise l'intervale en une puissance de 2. Par exemple supposons qu'on a calculer une table de sinus avec 90 valeurs stockées en mémoire flash. Soit une valeur à tous les 4 degrés. si on veut connaître la valeur au degré près on peut faire une interpolation linéaire entre les 2 valeurs.
Soit à connaître la valeur du sinus de 15 degrés:
// sinus15d=sinus[12]+ (sinus[16]-sinus[12])/4 *(15-12) int8_t i, fraction, diff,sinud15d; fraction= 15 & 0x3; //même chose que (15-12) diff=(sinus[16]-sinus[12])>>2; // (sinus[16]-sinus[12])/4 sinus15d=sinus[12]; for (i=0;i<fraction;i++) sinus15d+= diff; // même chose que multiplication. Voilà, sans utiliser de multiplication ni de division ce code fait une interpolation linéaire pour trouver la valeur d'un sinus pour un angle qui tombe entre 2 valeurs de la table. Ça prends moins de code et c'est plus rapide. si on avait choisi de créer la table des sinus avec un interval de 3 ou 5 degrés il aurait fallu utiliser une multiplication et division.

Conclusion il faut penser en terme de base 2 lorsqu'on travaille avec de petits micro-processeurs.