Recherche des nombres narcissiques

Finalité du programme


Le but du programme est de calculer tous les nombres narcissiques (Smallbrain) compris entre une borne minimale et une borne maximale. Un nombre narcissique est un nombre qui est égal à la somme cumulée de ses chiffres à la puissance Nième (ou N représente le nombre de chiffres). Le programme doit pouvoir trouver tous ces nombres entre 1 et 2^⁶³-1.

Algoritmique du programme



Les grandes étapes de l'algorithme sont décrites sur le schéma ci-dessous :

etape2.png

1. Calcule et stockage de toutes les puissances des chiffres jusqu'à une puissance N calculée par la formule suivante, max < 2^N avec N < 20.

puissances.png



2. Recherche de l'ensemble des combinaisons sans répétition du type C(N+9,9) avec N le nombre de chiffre d'un nombre.
Une combinaison sans répétition est stockée sous la forme d'un tableau d'occurrence des chiffres qui le compose.
Pour chaque combinaison :
a. Calcule la somme des différents chiffres du nombre à la puissance Nième
b. La somme des chiffres est ensuite redécomposée en tableau d'occurrence de chiffres
c. Et si les deux tableaux d'occurrence de chiffres sont égaux alors il s'agit d'un nombre narcissique et celui-ci est inséré dans une liste triée.

etapes.png



3. La liste des nombres narcissiques est ensuite affichée dans l'ordre croissant.


Organisation du code



Le code source est composé de 4 classes. Le schéma ci-dessous représente le diagramme de classe associé au code.

diagramme_classe.png


Par ordre d'importance :

    • La classe SmallBrain se concentre sur la recherche des nombres narcissiques
    • La classe Chiffres permet de manipuler un tableau d'entiers qui représente les chiffres de 0 à 9.
      Cela permet entre autre de stocker un tableau d'occurrence des chiffres de nombres.

tableau_occurrences.png

  • La classe Calcul permet d'effectuer et de stocker les calculs des puissances.
  • La classe Bench permet de mesurer le temps d'exécution du programme.


Parallélisation du code

Le programme est parallélisé à l'endroit le plus en gourmand en ressources du programme.
C'est-à-dire pour la recherche de l'ensemble des combinaisons sans répétition.
Nous avons utilisé l''API OpenMP pour paralléliser notre algorithme.

Voici par exemple l'appel de la méthode qui génère la liste des combinaisons sans répétitions.

 #pragma omp parallel
    {
      #pragma omp single nowait
      this->genererListeNombres(p_max, p_max, 0, Chiffres());
    }

Dont voici le code.

void SmallBrain::genererListeNombres(u_int32_t nb_imbrication,
                                     const u_int32_t p_calcule,
                                     const u_int32_t indice_depart,
                                     const Chiffres& nombre){
	--nb_imbrication;
    /* Pour chaque entier de l'indice depart à 9. */
    for(u_int32_t c = indice_depart; c <= 9; ++c){
        Chiffres ch = nombre, ch1 = 0;
        ++ch.c[c];//Ajoute l'indice courant comme chiffre.

        //Tant que l'imbrication n'est pas égale à 0, continue la récursion.
        if(nb_imbrication){
            #pragma omp task
            this->genererListeNombres(nb_imbrication, p_calcule, c,ch);
        }

        u_int64_t somme = getSomme(ch,p_calcule-nb_imbrication);
        //Si la somme à la puissance N est egal au nombre alors il est narcissique.
        if(ch1.compareChiffres(somme,ch) &&
                    somme >= this->min &&
                    somme <= this->max) {

            #pragma omp critical
            this->smallbrains.insert(somme);
	}
    }
}


OpenMP offre moins de possibilités avec les codes récursifs mais même si cet algorithme récursif se prête mal à la parallélisation, les résultats avec plusieurs coeurs offrent quand même un meilleur temps.

temps.png



Utilisation du programme


Pour compiler le programme :
make

Pour exécuter le programme :
./SmallBrain min max
Exemple d'utilisation
./SmallBrain 1 1000
./SmallBrain 1 9223372036854775807L


Archive du programme



Les sources et la documentation sont disponibles dans l'archive suivante :

SmallBrain.tar.gz

Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.
Étiquettes: