Posts Tagged ‘Qt’

Mandelbrot

Saturday, February 18th, 2012

L’ensemble de Mandelbrot est une fractale bien connue pour son aspect si particulier en forme de cardioïde :

Cet ensemble est défini selon une formule relativement simple que nous verrons plus loin. Mais comme cette formule fait intervenir les nombres complexes, un petit rappel ne fera pas de mal.

Les nombres complexes

Si l’on se limite à l’ensemble des nombres réels (R), il est impossible de calculer la racine carrée d’un nombre négatif, comme par exemple .

L’ensemble des nombres complexes () permet de résoudre ce genre de problème. L’idée est de nommer le résultat de par la lettre i. Cette lettre représente la partie imaginaire du nombre. Ainsi :

$$\sqrt{-16}=\sqrt(-1\cdot 16)=\sqrt(-1)\cdot\sqrt(16)=i4$$

On dit que i4 est la partie imaginaire d’un nombre. Rien n’empêche qu’un nombre complexe possède également une partie réelle. On note donc un nombre complexe sous la forme (a + ib), où a est la partie réelle et b la partie imaginaire.

Comme les nombres réels sont constitués de deux composantes (la partie réelle et la partie imaginaire), il est facile de les représenter graphiquement sur un plan. Par convention, la partie réelle du nombre est dessinée en abscisse et la partie imaginaire en ordonnée. Voici par exemple la représentation du nombre complexe (3 + i4) :

Plutôt que d’utiliser la forme (a + ib), il est également possible de représenter un nombre complexe par son module (la longueur du segment) et son argument (l’angle). On parle de notation polaire.

Le module, noté |z|, se calcule facilement au moyen du théorème de Pythagore :

$$|z|=\sqrt{a^{2}+b^{2}}$$

Opérations utiles

L’addition et la multiplication de nombres complexes est associative, commutative et distributive, au même titre qu’avec les nombres réels.

L’addition de deux nombres complexes (a+ib) et (a’+ib’) est une opération très simple :

$$(a + ib) + (a{}’ + ib{}’) = a+a{}’ + i(b+b{}’)$$

La multiplication de deux nombres complexes est une opération également relativement simple :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ + aib{}’ + iba{}’ + i^{2}bb{}’$$

Comme i2= -1, on peut donc écrire :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ – bb{}’ + i(ab{}’+a{}’b)$$

Pour représenter graphiquement l’ensemble de Mandelbrot, nous n’aurons pas besoin d’autres opérations.

L’ensemble de Mandelbrot

Un nombre complexe C fait partie de l’ensemble de Mandelbrot si la suite < ne tend pas vers l'infini (en module). . Il a été démontré en 1990 que cet ensemble a une dimension de Hausdorff de 2. Cela signifie que dès que le module de cette suite dépasse 2, c’est que le nombre en question ne fait pas partie de l’ensemble de Mandelbrot.

À savoir également que l’ensemble de Mandelbrot est compris entre les nombres complexes (-2.1 – i1.2) et (0.6 + i1.2).

Représentation de l’ensemble de Mandelbrot

Pour afficher à l’écran l’ensemble de Mandelbrot, l’idée est d’associer à la surface de la fenêtre un intervalle de nombres complexes. Ainsi, chaque pixel de la fenêtre représente un nombre complexe pour lequel on pourra déterminer s’il appartient ou non à l’ensemble.

Il faut donc, pour chaque pixel de l’écran déterminer à quel nombre complexe il correspond, puis vérifier si ce nombre fait partie de l’ensemble de Mandelbrot. Si c’est le cas, le pixel sera affiché en noir. Sinon, il restera en blanc.

La plupart des langages de programmation ne permettent pas de manipuler en standard les nombres complexes. Toutefois, le calcul de la suite étant assez simple, il est facile de la calculer au moyen de nombres réels uniquement.

Posons et .

Calculons :

$$Z_{n+1}=Z_{n}\cdot Z_{n} + C=(Za_{n}+iZb_{n})\cdot (Za_{n}+iZb_{n}) + (Ca+ib)$$

$$Z_{n+1}=Za{_{n}}^{2}-Zb{_{n}}^{2}+i(2\cdot Za_{n} \cdot Zb_{n}) + Ca+iCb$$

Nous obtenons donc les calculs réels suivants :

$$Za_{n+1}=Z{_{na}}^{2}-Z{_{nb}}^{2}+Ca$$

$$Zb_{n+1}=2\cdot Za_{n} \cdot Zb_{n} + Cb$$

Reste à calculer cette suite pour déterminer si elle converge vers l’infini ou pas.

Nous avons vu plus haut que dès que le module de Z dépasse 2, il est certain que le nombre complexe en question ne fait pas partie de l’ensemble de Mandelbrot.

Il faut tester si le module est inférieur à 2 :

$$|z| < 2$$

Donc :

$$\sqrt{a^{2}+b^{2}} < 2$$

Nous pouvons simplifier le calcul en élevant les deux termes au carré :

$$a^{2}+b^{2} < 4$$

Par contre, si le nombre fait partie de l’ensemble, il faudrait calculer la suite à l’infini, ce qui n’est bien sûr pas réaliste. L’idée est donc de calculer les éléments de la suite jusqu’à un nombre d’itérations maximal, par exemple 200. Si après 200 itérations, le module de Z ne dépasse pas 2, on considère que la suite ne tend pas vers l’infini et que le nombre complexe fait partie de l’ensemble de Mandelbrot.

Il est donc impossible de dessiner cet ensemble de façon exacte. Sa représentation est une approximation dont l’exactitude dépend du nombre maximal d’itérations.

Algorithme

Voici l’algorithme permettant de vérifier si un nombre complexe C fait partie de l’ensemble de Mandelbrot :

procédure déterminant si C fait partie de l'ensemble de Mandelbrot
données : C : complexe
          Ca, Cb, Za, Zb, ZaTemp : réels
          Iteration, MaxIteration : entiers

début
   MaxIteration ← 200
   Ca ← partie réelle de C
   Cb ← partie imaginaire de C

   Za ← 0
   Zb ← 0

   Iteration ← 0

   tant que Za*Za + Zb*Zb < 4 et Iteration < MaxIteration faire
      ZaTemp ← Za*Za-Zb*Zb+Ca
      Zb ← 2*Za*Zb+Cb
      Za ← ZaTemp
      Iteration ← Iteration+1
   fin tant que

   si Iteration = MaxIteration alors
      le point fait partie de l'ensemble de Mandelbrot
   sinon
      le point ne fait pas partie de l'ensemble de Mandelbrot
   fin si
fin

Reste à utiliser cet algorithme pour dessiner quelque chose à l’écran. Il faut donc passer en revue chaque pixel de l’écran, déterminer à quels nombres complexes ils correspondent et les afficher s’ils appartiennent à l’ensemble de Mandelbrot.

Pour simplifier les choses, et comme l’ensemble de Mandelbrot est symétrique par l’abscisse, nous pouvons inverser l’orientation mathématique de l’axe imaginaire (l’ordonnée, axe vertical) afin qu’il soit dans la même direction que l’axe vertical d’affichage de l’écran.

procédure dessin de l'ensemble de Mandelbrot
données : LargeurEcran, HauteurEcran, Ligne, Colonne : entiers
          IntervalleComplexeGauche, IntervalleComplexeHaut,
          IntervalleComplexeDroite, IntervalleComplexeBas : réels
début
   IntervalleComplexeGauche ← -2.1
   IntervalleComplexeHaut ← 1.2
   IntervalleComplexeDroite ← 0.6
   IntervalleComplexeBas ← -1.2

   pour Ligne allant de 0 à HauteurEcran faire
      pour Colonne allant de 0 à LargeurEcran faire
         Ca ← Colonne * (IntervalleComplexeDroite - IntervalleComplexeGauche) / LargeurEcran + IntervalleComplexeGauche
         Cb ← Ligne * (IntervalleComplexeBas - IntervalleComplexeHaut) / HauteurEcran + IntervalleComplexeHaut

         si (Ca,Cb) fait partie de l'ensemble de Mandelbrot faire
            dessiner en Colonne, Ligne un point noir
         sinon
            dessiner en Colonne, Ligne un point blanc
         fin si
      fin pour
   fin pour
fin

 Implémentation en C++ avec Qt

Voici une implémentation simple en C++ et Qt des algorithmes présentés ci-dessus.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 200;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb);

// Programme principal
int main(int ArgC, char *ArgV[]) {
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            if (isInMandelbrotSet(Ca, Cb))
                Image.setPixel(Col, Line, BLACK);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    return Iteration == MAX_ITERATION;
}

Et voilà le résultat :

Représentation colorée

Si vous avez déjà vu des représentations de l’ensemble de Mandelbrot, vous serez sans doute déçus par le résultat austère, noir et blanc, obtenu.

Toutefois, la représentation ci-dessus est conforme à la donnée mathématique : les points noirs sont ceux qui font partie de l’ensemble de Mandelbrot.

Par contre, ce qui est intéressant, ce sont les points qui ne font pas partie de l’ensemble. Au bout d’un certain nombre d’itérations, ces points sont exclus. L’idée est alors de leur donner un couleur, différente selon le nombre d’itérations qu’il a fallu pour les exclure.

Solution simple

Un ordinateur est capable de recréer des millions de couleurs en mélangeant (synthèse additive) les trois couleurs primaires rouge, vert et bleu.

Pour chaque couleur primaire, il est possible de donner une intensité comprise en zéro (noir) et 255 (couleur vive).

Nous pourrions donc fixer à 256 le nombre maximal d’itérations dans notre algorithme. Dès lors, il suffit d’utiliser directement le nombre d’itérations obtenu comme intensité d’une des couleurs de base, par exemple le rouge.

Si le nombre maximal (256) est atteint le point sera dessiné en noir.

Le programme doit être modifié de telle sorte que la méthode isInMandelbrotSet() retourne un paramètre supplémentaire contenant le nombre d’itérations.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 256;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount = 0);

// Programme principal
int main(int ArgC, char *ArgV[])
{
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            int Iteration = 0;
            if (isInMandelbrotSet(Ca, Cb, &Iteration))
                Image.setPixel(Col, Line, BLACK);
            else
               Image.setPixel(Col, Line, Iteration*256*256);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    if (pIterationCount)
       *pIterationCount = Iteration;
    return Iteration == MAX_ITERATION;
}

Voilà le résultat obtenu :

Il y a sans doute moyen de faire mieux !

Le problème vient du fait que la surface éloignée de l’ensemble de Mandelbrot est très sombre, car il faut peu d’itérations pour déterminer que ces points ne font pas partie de l’ensemble.

Par contre, pour les points proches de la frontière de l’ensemble, les variations du nombre d’itérations sont plus marquées, mais le choix des couleurs ne rend pas compte de cette diversité.

Solution avancée

La meilleure solution est donc de mettre au point un dégradé de couleurs. Toute la difficulté sera de choisir judicieusement les couleurs constituant ce dégradé.

Voici un dégradé possible :

Les couleurs clés sont les suivantes :

Position Couleur R V B Hexadécimal
0 % rouge foncé 128 0 0 800000h
20 % jaune 255 255 0 FFFF00h
40 % orange 255 165 0 FFA500h
60 % pourpre 160 32 240 A020F0h
80 % bleu nuit 25 25 112 191970h
100 % rouge foncé 128 0 0 800000h

Et voilà le résultat correspondant :

Le rendu est bien plus satisfaisant !

La principale difficulté consiste donc à programmer le dégradé de couleur, en particulier en ce qui concerne les couleurs intermédiaires.

Pour ce faire, le plus simple est de coder une classe capable de gérer un dégradé entre certaines couleurs clé.

Le code étant trop long pour être affiché sur cette page, il peut être téléchargé : Projet Qt : MandelBrotGUI

À la découverte de la fractale

La partie amusante peut maintenant commencer : changer l’intervalle affiché afin d’admirer de magnifiques figures fractales.

C’est la ligne suivante qui détermine l’intervalle qui sera affiché :

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

Le premier nombre indique la limite gauche de l’intervalle (-2.2). Le deuxième nombre, sa limite haute (-1.5). Les deux derniers nombres indiquent la largeur et la hauteur de l’intervalle (3). Pour un affichage dans une fenêtre carrée, il faudrait que la largeur et la hauteur soient identiques.

Observons ce que l’on obtient avec les valeurs suivantes : -0.83, -0.21, 0.05, 0.05. La ligne de code devient QRectF ComplexArea(-0.83, -0.21, 0.05, 0.05);

Lissage des couleurs

Cette vue spectaculaire souffre toutefois encore d’un petit défaut : le dégradé de couleurs présente un effet d’escaliers. C’est la conséquence d’utiliser directement le nombre d’itérations pour obtenir une couleur, qui est un nombre entier. Le résultat est donc discret (à l’opposé de continu), ce qui provoque  dans certaines situations ces escaliers disgracieux.

Pour y remédier il existe différents algorithmes dont le normalized iteration count*. Il permet de calculer une variation décimale du nombre d’itérations pour obtenir un dégradé plus fin.

La formule est la suivante :

$$n+\frac{\log (\log b)-\log(\log \left | Z_{n} \right |)}{\log 2}$$

n est le nombre d’itérations et b le rayon de sortie (qui correspond à la dimension de Hausdorff et qui vaut donc 2 dans notre cas).

L’amélioration est nette :

Essayons d’autres valeurs : -0.749, -0.177488, 0.02, 0.02. La ligne de code devient QRectF ComplexArea(-0.749, -0.177488, 0.02, 0.02);

Nombre d’itérations

Nous avons vu plus haut que pour déterminer si un nombre fait partie de l’ensemble ou pas, il faudrait théoriquement calculer la suite à l’infini. Une approximation est donc réalisée en limitant le nombre d’itérations effectué lors du calcul de la suite.

Le problème d’une telle approximation, c’est que lorsqu’on veut afficher des détails, elle a un impact direct sur la précision obtenue.

Voici, pour les valeurs -0.726277, -0.257609, 0.000332257, 0.000332257 le résultat avec une limite de 256 itérations :

La cardioïde est passablement déformée. Voici une meilleure approximation avec une limite de 512 itérations :

Avec une limite de 1024 itérations :

Et enfin avec une limite de 2048 itérations :

Toute la difficulté revient à trouver une limite qui donne de bons résultats, en un temps acceptable !


Sources :

Wikipédia : Ensemble de Mandelbrot

Wikipedia : Mandelbrot set

Coloring dynamical systems in the complex plane, Garcia, Fernandez, Barrallo, Martin

L’arrondi

Friday, October 22nd, 2010

Introduction

Un arrondi est nécessaire lorsqu’un nombre d’une certaine précision, doit être converti en un nombre d’une moindre précision.

Typiquement, un arrondi doit être effectué lorsqu’un nombre à virgule est converti en un nombre entier.

Cette notion peut sembler toute simple. Nous avons tous appris en cours de math qu’un nombre à virgule s’arrondi de la façon suivante :

  1. si la partie décimale est inférieure à 0.5, le nombre est arrondi vers le bas (par exemple 1.3 ≈ 1)
  2. si la partie décimale est supérieure ou égale à 0.5, le nombre est arrondi vers le haut (par exemple 1.6 ≈ 2 ou encore 1.5 ≈ 2)

Un premier doute s’installe lorsqu’il s’agit d’un nombre négatif. Un arrondi vers le bas correspond-il a un arrondi vers un nombre plus positif ou plus négatif ?

D’autre part, est-ce réellement la seule façon d’arrondir un nombre à virgule ? Y a-t-il une façon plus juste qu’une autre ?

Lors de l’écriture d’un programme qui manipule des nombres ayant à être arrondis, il est nécessaire de connaître comment une fonction d’arrondi réalise l’opération et quel sera le résultat obtenu.

Pour commencer, voyons les différentes façons d’arrondir un nombre à virgule (appelé également nombre réel).

Arrondi vers le bas (arrondi vers -∞)

Le nombre réel est arrondi vers l’entier inférieur.

3.4 ≈ 3

-3.4 ≈ -4

Arrondi vers le haut (arrondi vers +∞)

Le nombre réel est arrondi vers l’entier supérieur.

3.4 ≈ 4

-3.4 ≈ -3

Arrondi par troncature (vers zéro)

Le nombre réel est arrondi vers l’entier suivant le plus proche de zéro. Concrètement, la partie décimale du nombre réel est simplement retirée.

3.4 ≈ 3

-3.4 ≈ -3

Arrondi vers les infinis (par éloignement de zéro)

Le nombre réel est arrondi vers l’entier suivant s’éloignant le plus de zéro.

3.4 ≈ 4

-3.4 ≈ -4

Arrondi au plus proche

Le nombre réel est arrondi vers l’entier le plus proche du nombre réel.

3.4 ≈ 3

3.6 ≈ 4

-3.4 ≈ -3

– 3.6 ≈ -4

Cette dernière forme d’arrondi pose problème lorsque la partie décimale est exactement à mi-chemin entre deux nombre entiers (par exemple 3.5 ou -3.5).

Dans ce cas, il existe plusieurs façons d’arrondir :

Arrondi vers le bas (vers -∞)

3.5 ≈ 3

-3.5 ≈ -4

Arrondi vers le haut (vers +∞)

Cette méthode d’arrondi est également appelée arrondi arithmétique asymétrique.

3.5 ≈ 4

-3.5 ≈ -3

Arrondi vers zéro

3.5 ≈ 3

-3.5 ≈ 3

Arrondi vers les infinis

Cette méthode d’arrondi est celle qui est certainement la plus communément utilisée en arithmétique. On parle également d’arrondi arithmétique symétrique.

3.5 ≈ 4

-3.5 ≈ -4

Arrondi au pair le plus proche (arrondi bancaire)

Si la partie entière est impaire, le nombre arrondi sera le nombre pair le plus proche.

Si la partie entière est paire, elle correspond au nombre arrondi.

3.5 ≈ 4

2.5 ≈ 2

-3.5 ≈ -4

-2.5 ≈ -2

Cette méthode élimine le biais qui survient en cas d’arrondi systématique vers les infinis (ou vers zéro).

Arrondi à l’impair le plus proche

Si la partie entière est paire, le nombre arrondi sera le nombre impair le plus proche.

Si la partie entière est impaire, elle correspond au nombre arrondi.

3.5 ≈ 3

2.5 ≈ 3

-3.5 ≈ -3

-2.5 ≈ -3

Cette méthode d’arrondi est très rarement utilisée, sauf lorsqu’il est important que -0.5 et 0.5 ne soient pas arrondis à zéro.

Arrondi stochastique

C’est le hasard (uniformément réparti) qui détermine si le nombre sera arrondi vers l’entier supérieur ou inférieur.

Comme pour l’arrondi au pair le plus proche, cette méthode élimine le biais d’arrondi, mais introduit une notion de hasard qui rend la reproduction de calculs impossible.

Arrondi alterné

L’arrondi est alternativement fait vers l’entier supérieur puis vers l’entier inférieur.

Résumé

nombre -2.6 -2.5 -2.4 -1.6 -1.5 -1.4 -0.6 -0.5 -0.4 0.4 0.5 0.6 1.4 1.5 1.6 2.4 2.5 2.6
vers +∞ -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3 3 3
vers -∞ -3 -3 -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2
troncature -2 -2 -2 -1 -1 -1 0 0 0 0 0 0 1 1 1 2 2 2
vers les ∞ -3 -3 -3 -2 -2 -2 -1 -1 -1 1 1 1 2 2 2 3 3 3
au plus proche vers +∞ -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3 3
vers -∞ -3 -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3
vers zéro -3 -2 -2 -2 -1 -1 -1 0 0 0 0 1 1 1 2 2 2 3
vers les ∞ -3 -3 -2 -2 -2 -1 -1 -1 0 0 1 1 1 2 2 2 3 3
pair -3 -2 -2 -2 -2 -1 -1 0 0 0 0 1 1 2 2 2 2 3
impair -3 -3 -2 -2 -1 -1 -1 -1 0 0 1 1 1 1 2 2 3 3
stochastique -3 -3 ou -2 -2 -2 -2 ou -1 -1 -1 -1 ou 0 0 0 0 ou 1 1 1 1 ou 2 2 2 2 ou 3 3
alterné -3 -3 (-∞) -2 -2 -1 (+∞) -1 -1 -1 (-∞) 0 0 1 (+∞) 1 1 1 (-∞) 2 2 3 (+∞) 3

Note : lorsque un nombre négatif est arrondi à zéro, certaines implémentations préservent le signe devant le zéro : -0.5 ≈ -0, afin de distinguer un arrondi à zéro provenant d’une nombre négatif, d’un arrondi provenant d’un nombre positif.

Fonctions courantes d’arrondi

Chaque langage (et chaque bibliothèque de fonctions) met à disposition un certain nombre de fonctions d’arrondi.

J’ai tenté de réunir dans un tableau les différentes façons d’arrondir un nombre réel ainsi que les différentes fonctions proposées par un langage ou une bibliothèque particulière.

Je m’en suis tenu aux langages que j’utilise couramment : C++ (avec les bibliothèques standards), C++ avec la bibliothèque Qt, VBS et Java. J’y ai ajouté Excel (et donc Keynote, qui implémente les mêmes fonctions), que j’utilise également régulièrement.

méthode\langage VBScript C++ C++ et cmath C++ Qt Java et java.lang.math Excel
vers +∞ ceil() ceil()
vers -∞ Int floor() floor() INT() ENT()
vers zéro
(troncature)
Fix static_cast<int>() trunc() int() ROUNDDOWN() ARRONDI.INF()FLOOR() TRONQUE()
vers les ∞ ROUNDUP() ARRONDI.SUP()CEILING() PLAFOND()
au plus proche vers +∞ qRound round()
vers -∞
vers zéro
vers les ∞ FormatNumber1 round() ROUND() ARRONDI()
pair Round CByte CInt CLng rint() rint()
impair
stochastique
alterné

1Contrairement aux autres fonctions qui retournent un nombre, FormatNumber retourne une chaîne de caractères formatée selon certains paramètres donnés. Il reste néanmoins intéressant d’observer la méthode d’arrondi utilisé par cette fonction.

Ce tableau montre bien la confusion qui peut s’intaller : une fonction nommée Round va par exemple faire un arrondi au pair le plus proche en VBS, mais un arrondi arithmétique symétrique en C++ et avec Excel. La fonction équivalente en Java fera un arrondi arithmétique asymétrique, de même que la fonction qRound de Qt !


Sources :

Wikipedia : Rounding to integer

Wikipédia : Arrondi

Aide et support Microsoft : How To Implement Custom Rounding Procedures

Les dates

Monday, March 22nd, 2010

Lors de la pratique de son métier, un développeur sera assurément amené à manipuler des dates.

À moins d’une raison très particulière, il ne faudrait pas réinventer la roue et plutôt faire usage des classes prenant déjà en charge la problématique des dates (et de l’heure).

Qt, par exemple, met à disposition les classe QDate et QDateTime.

Mais lorsqu’on apprend la programmation, les exercices sur les dates sont des classiques. Voici ce qui est souvent demandé :

  • déterminer si une année donnée est bissextile ;
  • déterminer le jour de la semaine d’une date donnée ;
  • convertir l’année d’une date en chiffres romains (et vice-versa).

Je reviendrai certainement sur la conversion d’un chiffre arabe en chiffre romain (et vice-versa) dans un autre billet.

Déterminer si une année est bissextile

Pour le calendrier grégorien (celui que l’on utilise de nos jours), une année (le temps que met la Terre pour faire un tour complet autour du Soleil) dure 365.2425 jours.

Avec ce calendrier la méthode pour déterminer si une année donnée est bissextile est la suivante :

  • Une année est bissextile si elle se divise par 4.
  • Une année n’est pas bissextile si elle se divise par 100.
  • Toutefois, si elle se divise par 400, elle est bissextile.
bool isLeapYear(int Year) {
   return (Year % 400 == 0 || (Year % 4 == 0 && Year % 100 != 0) );
}

Mais ce calcul n’est valable qu’avec le calendrier grégorien. Or, celui-ci a été introduit le 15 octobre 1582 par le pape Grégoire XIII.

Pour toutes les années qui précèdent 1582, c’est le calendrier julien qui fait foi. Ce calendrier est basé sur une année de 365.25 jours, ce qui signifie qu’il y a une année bissextile tous les 4 ans.

Notre méthode de calcul peut donc être améliorée :

bool isLeapYear(int Year) {
   if (Year < 1582)
      return abs(Year) % 4 == 0;
   else
      return (Year % 400 == 0 || (Year % 4 == 0 && Year % 100 != 0) );
}

Déterminer le jour de la semaine

La méthode permettant de déterminer quel jour de la semaine est une date donnée est différente selon que la date fait partie du calendrier grégorien ou julien.

Le calendrier julien se termine le 4 octobre 1582. Le calendrier grégorien commence le 15 octobre 1582. Cela signifie que le jour qui suit la date du 4 octobre 1582 est le 15 octobre 1582. Les dates comprises entre le 5 et le 14 octobre 1582 n’existent pas.

prérequis : Jour (1 - 31), Mois (1-12), Année
variables : DécaleAn, MoisDécalé, An, NuméroJour : entiers
début
   DécaleAn <- (14 - Mois) / 12
   An <- Année - DécaleAn
   MoisDécalé <- Mois + 12 * DécaleAn - 2

   si (Année > 1582) ou (Année = 1582 et (Mois > 10) ou (Mois = 10 et Jour >= 15))) alors
      NuméroJour = (Jour + Année + An/4 - An/100 + An/400 + 31 * Mois / 12) modulo 7
   sinon
      si (Année < 1582) ou (Année = 1582 et (Mois < 10 ou (Mois = 10 et Jour <= 4))) alors
         NuméroJour = (5 + Jour + An + An / 4 + ( 31* Mois / 12) modulo 7
      sinon
         NuméroJour = erreur
      fin si
   fin si
fin

NuméroJour vaut 0 pour dimanche, 1 pour lundi, etc.

En C++, la fonction pourrait être la suivante :

int dayOfWeek(int Jour, int Mois, int Annee) {
   int DecaleAn = 14 - Mois / 12;
   int An = Annee - DecaleAn;
   int MoisDecale = Mois + 12 * DecaleAn - 2;
   int NumeroJour = 0;

   if ( (Annee > 1582) ||
        (Annee == 1582 && (Mois > 10) || (Mois == 10 && Jour >= 15))) )
      NumeroJour = (Jour + Annee + An/4 - An/100 + An/400 + 31 * Mois / 12) % 7;
   else if ( (Annee < 1582) ||
                (Année == 1582 && (Mois < 10 || (Mois == 10 && Jour <= 4))) )
      NumeroJour = (5 + Jour + An + An / 4 + ( 31* Mois / 12) % 7;
   else
      NumeroJour = -1; 

   return NumeroJour; // 0 : dimanche, 1 : lundi, etc. -1 : erreur
}

Pourquoi QList::count() retourne un int ?

Thursday, March 18th, 2010

Les utilisateurs de Qt4 ont peut-être remarqué que la méthode count() ou size() de QList (mais également d’autres classes comme QVector, QMap, etc) retourne un int (donc un entier signé pouvant représenter des valeurs négatives), alors qu’à première vue, un entier non-signé semblerait plus logique.

D’ailleurs, les classes équivalentes de Qt3 retournaient bien un entier non-signé (unsigned int ou uint). Pourquoi ce changement ?

Au premier abord, un entier non-signé semble plus correct qu’un entier signé pour représenter une quantité : une liste ne peut pas contenir un nombre d’éléments négatif. Toutefois à l’usage, il est fréquent de comparer un entier avec le nombre d’élément d’une liste, ce qui provoque à chaque fois un avertissement du compilateur (qui peut être supprimé en faisant un transtypage).

Mais au delà de la stricte application disant qu’une quantité ne peut pas être négative, la raison principale d’utiliser un entier signé est d’éviter des erreurs sournoises.

Par exemple, si count() retourne un entier non-signé, le code suivant fonctionne :

for (uint i = 0; i < count(); ++i)

Mais à l’opposé, le code ci-dessous ne fonctionne pas :

for (uint i = count() - 1; i >= 0; --i)

car si la liste est vide, count() retournera zéro, et au moment d’être décrémenté, il vaudra une valeur positive. C’est un problème sournoi qui ne saute pas aux yeux et qui provoque souvent des boucles quasi-infinies.

Par contre, si count() retourne un entier signé, les deux façons de faire ci-dessous fonctionnent, sans subtilité cachée :

for (int i = 0; i < count(); ++i)
for (int i = count() - 1; i >= 0; --i)

Programme en mode console avec Qt Creator

Thursday, February 4th, 2010

Lorsqu’on souhaite développer une application en mode console avec Qt Creator (1.3.1) qui soit multi-plateforme Mac et Windows, il y a quelques problèmes à régler.

Comme exemple, nous allons essayer de faire fonctionner correctement le petit programme suivant :

#include <iostream>

int main() {
   std::cout << "Quel est ton nom : ";
   std::string Nom;
   std::cin >> Nom;
   std::cout << "Salut " << Nom << " !\n";
   return 0;
}

Mac OS X

ur Mac OS X, avec la configuration par défaut, la sortie standard est dirigée sur l’onglet Sortie de l'application de Qt Creator. Cela pose néanmoins un problème de taille : cet onglet ne gère pas l’entrée standard. Notre programme simple ne fonctionnera donc pas.

Pour résoudre ce problème, il faut forcer l’exécution de notre programme dans un terminal.

Pour ce faire, il faut modifier les paramètres d’exécution du projet. Afficher les détails et cocher la case Exécuter dans un terminal.

Malheureusement, cette façon de faire amène encore un petit problème à résoudre.
Sur Mac OS X, c’est un terminal XTerm qui sera utilisé, mais dans la configuration standard de Qt Creator, l’application XTerm n’est pas trouvable. Il faut en fait préciser le chemin complet de l’application.

Ouvrir les préférences de Qt Creator et aller dans la configuration Environnement : Général.

Dans la zone Terminal, indiquer le chemin complet :

/usr/x11/bin/xterm -e

Windows

Sur Windows, la configuration par défaut démarre une fenêtre de commande, dans laquelle s’affiche la sortie standard. L’entrée standard est correctement gérée.

Par contre, il subsiste deux problèmes :

  • Lorsque le programme est terminé, la fenêtre de commande disparaît immédiatement, ce qui empêche de voir la sortie finale du programme.
  • Si l’on souhaite déboguer notre programme, la fenêtre de commande n’est plus ouverte et la sortie standard s’affiche dans l’onglet Sortie de l'application de Qt Creator. L’entrée standard n’est pas gérée.

Pour résoudre ces problèmes, il faut forcer l’exécution de notre programme dans un terminal.

Pour ce faire, il faut modifier les paramètres d’exécution du projet. Afficher les détails et cocher la case Exécuter dans un terminal.

Les deux

Notre programme fonctionne maintenant correctement, aussi bien en ce qui concerne la sortie standard que l’entrée standard. Le déboguage se fait également au travers du terminal.

Reste le problème des accents concernant la phrase automatique Appuyez sur ENTRÉE pour fermer cette fenêtre.

Pour se débarrasser de ces caractères cabalistiques, la solution la plus simple est de démarrer Qt Creator en anglais.

Qt Creator en anglais

Wednesday, February 3rd, 2010

Mise à jour avril 2010 :

La technology preview de Qt Creator 2.0 montre qu’il est maintenant possible de changer la langue de l’interface depuis les préférences de l’application, en allant dans la section Environnement : Général des options.

Fin de la mise à jour.

Depuis la version 1.3.0, Qt Creator a été localisé dans plusieurs langues, en particulier le français. Dès lors, Qt Creator utilise automatiquement la langue du système d’exploitation.

Malheureusement, il n’y a aucun réglages au sein de l’application permettant de choisir une autre langue. Il peut en effet être très pratique dans certaines situations de démarrer Qt Creator 1.3.1 en anglais.

La solution diffère selon le système d’exploitation.

Mac OS X

La seule solution que j’ai trouvé avec Mac OS X pour forcer Qt Creator d’utiliser l’anglais est de l’empêcher de trouver le fichier de traductions du français. Pour ce faire, il faut sélectionner l’application Qt Creator, afficher le menu contextuel et choisir Afficher le contenu du paquet.

Lorsque le contenu est affiché, aller dans le répertoire Contents/Resources/translations/. Localiser le fichier qtcreator_fr.qm et le renommer (par exemple en _qtcreator_fr.qm).

Lors du prochain démarrage de Qt Creator, celui-ci ne trouvera pas le fichier de traductions pour le français (la langue du système d’exploitation) et se rabattra sur l’anglais.

Windows

Sous Windows, le plus simple est de définir la variable d’environnement LANG, que Qt Creator utilise en priorité (avant la langue du système d’exploitation) pour déterminer la langue de démarrage.

Pour ajouter une variable d’environnement, afficher les propriétés du Poste de travail.

Dans l’onglet Avancé, cliquer sur Variables d'environnement.

La liste des variables d’environnement apparaît. Ajouter une nouvelle variable pour l’utilisateur en cours en cliquant sur Nouveau.

Le nom de la variable d’environnement doit être LANG. Comme valeur pour cette variable, mettre en, ce qui signifie que que dorénavant, Qt Creator démarrera en anglais.

Augmenter le niveau de warning avec Qt Creator

Friday, December 11th, 2009

Voici un petit programme C++ développé avec l’IDE Qt Creator :

#include <iostream>

int main() {
   short A = 60000;
   std::cout << "A vaut " << A << "\n";
   return 0;
}

À priori, très simple mais qui ne fonctionne pas comme désiré. Le problème ? L’affectation du nombre 60000 dans un short signé.

Malheureusement, lors de la compilation de ce programme, aucun warning n’est émis !

Pour augmenter le niveau de warning, il suffit de modifier le fichier projet (.pro) et d’y ajouter la ligne suivante :

QMAKE_CXXFLAGS_WARN_ON += -Wconversion

Pour être informé d’un maximum de warnings, il serait même judicieux d’y ajouter le flag -Wextra, ce qui aboutirait à la ligne suivante :

QMAKE_CXXFLAGS_WARN_ON += -Wconversion -Wextra

En plus des problèmes de conversion, il peut également y avoir des problèmes lors du passage d’un type signé vers non-signée et vice-versa. Pour détecter ces problèmes, il faut utiliser le flag –Wsign-conversion.

D’une façon générale, il peut même être pratique de considérer les warnings comme des erreurs, afin de ne rien laisser passer. Pour ce faire, il faut ajouter le flag -Werror, ce qui abouti à la ligne suivante :

QMAKE_CXXFLAGS_WARN_ON += -Wconversion -Wextra -Wsign-conversion -Werror