> Théorie
PrograZine issue #9 - http://www.citeweb.net/discase/9/FIXE.htm Edito Sommaire Contribution Contacts


Le Calcul en Virgule fixe
par discase - discse@mail.dotcom.fr 		Initié Intel





    Nous allons voir au cours de cet article un principe de clcul nommé le calcul en virgule fixe. Cette méthode permet dans de nombreux cas d'accélerer grandement les calculs plutôt que de passer par des calculs à virgule flottante classiques.
>Les calculs en virgule flottante

    En informatique (et en particulier dans les langages de progrmmation), on distingue en général deux grands types de données: les entiers et les nombres à virgules (cependant, quelques langges ne font pas cette distinction).

    Comme tout le monde le sait, le processeur ne reconnait qu'un seul type de donnée: le binaire ! (0 ou 1). Pour stocker un nombre entier, on va donc stocker sa représentation en base 2 (i.e en binaire). Pour 32 par exemple, on stockera 100000, pour 33 100001, etc ...

    Maintenant pour stocker un nombre à virgule, c'est plus compliqué. Prenons le nombre 3.14159265. Comment pourrait-on stocker ce nombre ? Nous devons stocker plusieurs renseignements: la partie entière et la partie décimale. On peut aussi stocker le nombre entier et la position de la virgule dans ce nombre. En général, on stocke également l'exposant scientifique (noté sous la forme E+2 par exemple). Ca fait pas mal de chose à stocker. Ce type de donnée est souvent stocké sur 4 octets au minimum. De plus, une simple addition de deux nombres à virgule demande beaucoup de travail au processeur. Il doit en effet les découper et les tailler en rondelle avant chaque opération.

    Tout ça pour vous dire que les calculs en virgule flottante sont à éviter le plus souvent possible !! Le seul cas où ils sont vraiment nécessaires est quand le calcul en virgule flottante n'est pas très important où qund on a besoin d'une énorme précision. Pour programmer un moteur 3D par exemple, c'est quasi-indispensable !
>Principe du calcul en virgule fixe

    Le principe de calcul en virgule fixe est assez simple. Supposons que notre programme n'est besoin que d'une précision de deux chiffres après la virgule. Nous voulons multiplier 1.50 par 3.00, ce qui donne 4.50. On effectuera plutôt (150*300) / 100, ce qui donne 450. Le principe est toujours de travailler sur des nombres entiers. Plutôt que de travailler sur 1.50, on travaillera avec 150 qui est beaucoup plus simple et rapide à manipuler. On a juste multiplier par 100.

    Quand on multiplie deux de ces nombres entre eux, on ne doit pas oublier de diviser par 100

    Le principe de base est donc de stocker toutes les parties décimales dans la partie entière par simple multiplication. Au lieu de la seule opération 1.50*3.00, on a deux opérations (150*300)/100 et on traite le résultat sous forme entière.
>Récupérer la partie entière et décimale

    On ne travaille plus qu'avec des nombres entiers. Mais on a toujours besoin de connaitre la partie entière et a partie décimale d'un nombre, pour ionformer l'utilisateur par exemple. On ne va surtout pas dire que Pi est eviron égal à 314 ! mais plutôt à 3.14.

    Pour cel, il suffit de deux opérations: la division entière et le reste de cette division

    La division entière travaille sur des entiers et renvoie le quotient de la division.

    Si, par exemple, on a un nombre sous "forme fixe" A, on pourra extraire en Pascal:
VAR
  A : Integer;

BEGIN
  A := 314;

  Writeln('Pi = ',A DIV 100,'.',A MOD 100);
END.
l

    Les deux instructions DIV et MOD sont très rapide, et sûrement plus rapide qu'une division flottante.
>Accélerons encore un peu

    Reprenons l'exemple de la multiplication: 1.5 par 3.0. On pourra afficher le résultat de cette multiplication par:
E = Quotient((1.5*100 * 3.0*100) / 100)
D = Reste((1.5*100 * 3.0*100) / 100)
l

    Le résultat sera donc E.D

    Pour généraliser un peu, on va appeller 100 le "facteur de précision" et on va la noter F
E = Quotient((1.5*F * 3.0*F) / F)
D = Reste((1.5*F * 3.0*F) / F)
l

    Je suis sûr que vou vou demander comment le Quotient de deux nombres entiers, le premier ayant été calculé par multiplication de deux nombres entiers, ayant été eux-mêmes obtenus par multiplication entre un entier et un flottant (ouf !) peuvent être plus rapide qu'une simple multiplication de deux flottant ?! En fait, j'en sais rien, mais c'était pour mieux comprendre la suite ...

    Vous remarquerez qu'on utilise la multiplication et la division par F (ici 100). Pour nous, humains qui utilisons le système en base 10, il n'y a rien de plus simple de multiplier ou diviser par un multiple de 10, il suffit, de "translater" le nombre de plusieurs chiffres. 01.5 devient 15.0, rien de plus simple.

    Eh bah pour le processeur, c'est pareil, sauf qu'il raisonne en base 2. Donc, pour lui rien de plus simple que de multiplier/diviser par une puissance de 2.

    Je reprend: Prenons un humain très con, si on lui de multiplier 2 par 10, il va poser son opération (il est très con j'ai dit !). Pour un humin un peu plus subtil, il va prendre 2 et rajouter un 0 ce qui donnera 20.

    Eh bah même chose pour le processeur, à la base il est très con, donc il va multiplier betement, mais si on lui dit, il utilisera une instruction magique qui permet de "décaler" (mis cette fois en binaire)

    Prenons le nombre 33 en binaire 10001. 33*2 = 66 Pour multiplier par deux, il suffit de déclaer à gauche chaque bit, ce qui donne 100010 qui est bien égal à 66.

    Les deux instructions de décalge (gauche et droite) dont SHL (SHift Left) et SHR (SHift Right) sur les processeurs Intel. Certains langages autres que l'assembleur permettent d'y accéder. Ainsi, en pascal c'est pareil (SHL et SHR) et en C c'est << et >>
En pascal:
33 SHL 2
En C:
33 << 2
l

    Après tout ça, nos formules deviennent: (J'ai appelé S le facteur de décalage en prenant F = 512 et S = 9)
E = Quotient((1.5*F * 3.0*F) SHR S)
D = Reste((1.5*F * 3.0*F) SHR S)
l

    De même, il y a possibilité d'accélerer les opérations "Quotient" et "Reste".

    En reprennant notre exemple en décimal, pour trouver le quotient et le reste de 450 par 100, ce n'est pas très dur: il y a deux zéros dans 100, on va donc décaler 450 vers la droite de deux, mais en effaçant à chaque le dernier chiffre: 450 puis 45 puis 4. 4 est le quotient.

    Pour le reste il suffit de prendre les deux premiers chiffres de 450.

    C'est donc très facile pour nous quand ce sont des puissances de 10. Vous vous doutez donc que ce sera facile pour l'ordinateur en cs de puissances de 2.

    Pour un facteur de précision de 512 par exemple, on décale de 9 vers la droite (SHR) pour la partie entière. Pour le reste, il faut "cacher" le reste du nombre (ne garder que les 9 premier bits de droite). Pour cela, on fait un AND 511 (512-1).
E = (1.5*F * 3.0*F) SHR S) SHR S
D = (1.5*F * 3.0*F) SHR S) AND (F-1)
l
>Application

    Prenons un exemple concret: un moteur 3D. Pour effectuer des rotations de points autour des trois axes, on utilise des formules faisant intervenir Sinus et Cosinus.

    Pour accélerer les calculs, on stockera dans des tableaux la valeur des cosinus et des sinus. On rarement besoin, même dans un moteur 3D d'utiliser des valeurs de sin et cos à 0.000000001 près . On se contente de 3 chiffres à peu près après la virgule. On multipliera donc par 1024 qui est une puissance de deux, qui revient à décaler de 10.

    Au début du programme, on déclare deux tableaux d'entiers: TSin et TCos
Pour i allant de 0 à 359,
  TSin[i] = (sin(i)+1) * 1024
  TCos[i] = (cos(i)+1) * 1024
l

    Vous allez voir plus loin pourquoi on ajoute un.

    Si on a besoin après d'un calcul faisant intervenir un sinus ou un cosinus:
H = Hypothénuse
O = ((TSin[Angle]-1) * H) SHR 10
l

    C'est surtout dans ces cas là que sert énormément le calcul à virgule fixe: on stocke dans un tableau des données à virgule mis que l'on connit à l'avance. Les multiplications classiques se font au début du programme et pendant les boucles ayant besoin de vitesse, on utilise les décalages ...
>Les nombres relatifs

    Vous savez tous plus ou moins qu'un sinus ou un cosinus est compris entre -1 et 1

    Le décalage binaire et la façon dont sont notés les nombres relatifs sur les processeur Intel font que ce système de multiplication / décalge fausse le résultat dans le cas d'un nombre négatif. Pour éviter cela, on remet le nombre en question en positif. Dans l'exemple précedent, on ajoutait 1 pour que les sin/cos soient compris entre 0 et 2.
Cet article est la propriété de discase. La copie et la diffusion sont libres sauf dans un but lucratif sans accord explicite de l'auteur.