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;
}
Voilà, donc j'attends vos commentaires, conseils, suggestions, ou insultes au choix...

Merci beaucoup