Discussion :

[PsychoH13]

Bonjour à tous, voilà je développe depuis quelques temps une "classe" de grands entiers en C, c'est-à-dire un type opaque et des fonctions qui permettent de gérer ce type. Il s'agit d'entier d'une taille pratiquement infinie, avec les opérations arithmétique de bases etc.
J'ai de plus développer un algorithme (avec l'aide d'autres codes) qui permet de calculer de grands factoriels "rapidement" (genre factorielle de 500.000 en 40 secondes).

Mon problème vient de l'affichage de ces très très grands nombres. En effet, je stocke mes nombres dans des structures de ce genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef struct _PSYInteger {
    size_t capacity;
    size_t length;
    bool negative;
    unsigned *datas;
} *PSYIntegerRef;

Sous forme de nombre binaire en base 2^32 et en valeur absolu. Pour afficher mon nombre, je convertis celui-ci de la base 2^32 à la base 1 milliard pour pouvoir afficher 9 chiffres à la fois. Et pour cette conversion j'utilise la division du nombre par 1 milliard, le problème c'est que ça prend beaucoup de temps, la conversion en elle-même prend jusqu'à 11 minutes pour afficher le factoriel de 500.000...

Ce que j'aimerais savoir, c'est si quelqu'un a des optimisations à apporter, ou tout au moins des pistes pour accélérer cette conversion. Merci

Voici mon code de conversion en chaîne de caractères :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
char *PSYIntegerToChar(PSYIntegerRef integer)
{
    char *result = NULL;
 
    if(PSYIntegerIsNull(integer))
    {
        result = malloc(2);
        strcpy(result, "0");
    }
    else
    {
        // Ici je crée une copie du nombre, car la boucle de division supprime ce nombre
        PSYIntegerRef a = PSYIntegerCopy(integer);
 
        // Je récupère sa taille et la double pour obtenir la taille d'une table de parties
        // Chaque partie représente 9 chiffres du nombre final
        size_t totalSize = integer->length * 2, partCount = 0;
 
        unsigned *partTable = malloc(totalSize * sizeof(unsigned));
 
        // C'est cette boucle qui prend beaucoup de temps
        while(a->length > 1 || (a->length == 1 && a->datas[0] != 0))
        {
            // Je divise à chaque tour mon nombre par 1 milliard pour obtenir chacune de ses parties
            partTable[partCount] = PSYIntegerSingleDigitDivide(a, 1000000000);
            partCount++;
        }
 
        // Ici je transforme chaque partie en texte
        char tempNumber[10] = "";
        result = malloc(partCount * 9 + 1);
 
        llong i = partCount - 1;
 
        sprintf(tempNumber, "%u", partTable[i]);
 
        // J'ai réécris strcpy() pour qu'elle me renvoie le caractère final de la chaîne copiée
        char *last = PSYstrcpy(result, tempNumber);
        i--;
 
        for(i; i >= 0; i--)
        {
            // Ici j'utilisais strcat() mais comme j'ai toujours 9 chiffres, je convertis
            // chaque partie et l'ajoute à la suite directement
            sprintf(last, "%09u", partTable[i]);
            last += 9;
        }
 
        free(partTable);
 
        char *temp = NULL;
 
        // Ça permet de supprimer les 0 qui sont devant le nombre
        temp = strpbrk(result, "123456789");
 
        size_t strSize;
 
        if(temp != result)
        {
            printf("FUCK !\n");
            char *tempResult = strdup(temp);
            free(result);
            result = tempResult;
        }
 
        strSize = strlen(result) + 1;
 
        // Gestion des nombres négatifs, ça ne nous concerne pas ici
        if(integer->negative)
        {
            strSize++;
            temp = strdup(result);
            result = realloc(result, strSize);
 
            strcpy(result, "-");
            strcat(result, temp);
            free(temp);
        }
 
        // Je libère la copie
        PSYIntegerFree(a);
    }
 
    return result;
}

De plus, voici la division que j'utilise, ça correspond à la division d'un chiffre de mes grands nombres, en considérant qu'un chiffre est un unsigned int :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
unsigned PSYIntegerSingleDigitDivide(PSYIntegerRef integer, unsigned d)
{
    if(d == 0)
    {
        printf("Error : ZERO DIVISION DUMBASS !\n");
        return 0;
    }
 
    ullong r = 0;
    size_t i = integer->length;
    unsigned *datas = integer->datas;
    while (i-- > 0)
    {
        r <<= 32;
        r |= datas[i];
        datas[i] = (unsigned)(r / d);
        r %= d;
    }
 
    // Cette fonction permet de réduire l'attribut "length"
    // pour que seul les chiffres différent de zéro devant le nombre soit pris en compte
    PSYIntegerNormalize(integer);
 
    // Je retourne le reste de la division
    return (unsigned)r;
}

Sur la salon C, on m'a dit de venir chercher de l'aide ici alors me voici.

J'ai quelques contraintes pour cette algorithme, je ne changerai pas la base du nombre en mémoire elle restera toujours stockée sous forme binaire (base 2^32). Je voudrais aussi pouvoir afficher le nombre dans d'autres bases, bien que la base hexadécimal soit simple en l'occurrence.

Voilà, donc j'attends vos commentaires, conseils, suggestions, ou insultes au choix...

[alex_pi]

Est ce que tu peux nous décrire un peu plus précisément (si possible en pseudo code plutôt qu'en C :-)) comment tu stockes tes entiers ? Ce sera plus simple pour t'aider

[PsychoH13]

Est ce que tu peux nous décrire un peu plus précisément (si possible en pseudo code plutôt qu'en C :-)) comment tu stockes tes entiers ? Ce sera plus simple pour t'aider

Alors euh... Un entier est stocké sous forme d'un tableau d'entiers de 32 bits.

La structure se forme ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef struct _PSYInteger {
    size_t capacity;
    size_t length;
    bool negative;
    unsigned *datas;
} *PSYIntegerRef;

Le premier attribut définit la capacité allouée au tableau, le deuxième définit le nombre de valeur dans le tableau qu'on utilise vraiment pour représenter le nombre, c'est-à-dire que toutes les cases du tableau dont les indices sont contenus entre "length" et "capacity - 1" ont une valeur indéfinie (en général 0, c'est pour ça qu'elles ne sont pas comptées).
Le booléen dit simplement s'il s'agit d'un nombre positif ou négatif.
Le dernier membre est une adresse vers le fameux tableau, c'est une sorte d'entier en big endian, c'est-à-dire que le "chiffre" de poids faible est à l'indice zéro, le chiffre de poids le plus fort est à l'indice length - 1.

De plus j'utilise la totalité de la capacité du nombre entier, c'est-à-dire que la valeur d'un entier d'un seul chiffre (length = 1) peut aller de -4*294*967*295 à +4*294*967*295.

Voilà déjà ce que je peux dire sur le nombre...

À part ça :

Meme les librairies genre GMP (GNU Multiple Precision) mettent du temps pour faire une conversion base 10 d'un nombre a plus de 100.000 chiffres.

Pour l'exemple, La classe BigInteger de Java:
10^50.000 -> 1.6 s
10^100.000 -> 6.7 s
10^200.000 -> 26.3 s

Je veux bien que ça prenne du temps... 26,3 secondes pour afficher un nombre de 200.000 chiffres... Mais mon factoriel de 500.000 je l'affiche pas en 26 secondes mais en 11 minutes ! Il y a quand même une différence, enfin là c'est la conversion qui prend 11 minutes, l'affichage en lui-même est beaucoup plus rapide puisqu'une fois que la chaîne de caractères est créée j'utilise la fonction standard pour afficher.

[pseudocode]

Mais mon factoriel de 500.000 je l'affiche pas en 26 secondes mais en 11 minutes !

26 seconde pour un nombre a 200.000 chiffres.

Et y a combien de chiffres dans factoriel 500.000 ? Un peu plus que 200.000 non ?

[PsychoH13]

Ah ben maintenant que tu le dis... Je viens de vérifier avec le factoriel de 100.000 qui fait 260.668 chiffres et il me l'affiche en 25 secondes...

Bon bah je vais au moins faire les bidouillages sur les pointeurs pour optimiser un peu...

[pseudocode]

Ce que j'aimerais savoir, c'est si quelqu'un a des optimisations à apporter, ou tout au moins des pistes pour accélérer cette conversion. Merci

La methode de conversion est la bonne: division successive par 10 et "empiler" les restes. On doit pouvoir un peu optimiser ta division mais je ne pense pas que ca change grand chose.

Meme les librairies genre GMP (GNU Multiple Precision) mettent du temps pour faire une conversion base 10 d'un nombre a plus de 100.000 chiffres.

Pour l'exemple, La classe BigInteger de Java:
10^50.000 -> 1.6 s
10^100.000 -> 6.7 s
10^200.000 -> 26.3 s

[souviron34]

une tite question en rapport avec ça :

ça sert à quoi ??